Google onsite interview questions


  • 0
    W

    @Ellest s may be a number


  • 0
    R

    @rajaditya
    Try for this case as well : [1,1,1,3,3,9,9,9], I think you would have to add one more case check in which all bits at some index i are 1.


  • 0

    The example for #3 seems problematic that I don't understand. Could anyone make a modification or give an explanation?


  • 0
    A

    For Question1, finding the missing number.
    As it appears to me, more a puzzle, than a programmatic question, a cheat way of doing this could be...

    S= sum of all given number.
    Just iterate through all of the given sequence and keep adding.

    Now, supposing that THERE WAS NO NUMBER MISSING,
    then the sum of the series be P_sum. Therefore,

    P_sum = (n/2)(firstterm + lastterm) [A general formula of a mathematical AP, where n is the number of terms]

    As each number actually repeats 3 times,
    Therefore, the total (When NO number is missing) will be thrice of P_sum
    T = 3 * [P_sum]

    Now, the missing number has to be the difference of these two., i.e

    MissingNumber = T - S


  • 0
    A

    Solution for Question.2 in Java

    import java.util.ArrayList;
    import java.util.List;
    
    public class DeCompressString {
    
    	private static String result="";
    	
    	public static void main(String[] args) {
    		String arg = "a3[b2[c1[d]]]e";
    		Decompress(arg, 1);
    		System.out.println(result);
    	}
    	
    	private static void Decompress(String str, int times){
    		List<Character> list = new ArrayList<Character>();
    		list.add('1');list.add('2');list.add('3');list.add('4');list.add('5');list.add('6');list.add('7');list.add('8');list.add('9');
    		while(times>0){
    			times--;
    			
    			for(int i=0; i<str.length(); i++){
    				char temp= str.charAt(i);
    				
    				if(list.contains(temp)){
    					
    					int endOffset = bracketSize(str, i+1);
    					Decompress(str.substring(i+1, endOffset), Character.getNumericValue(temp));
    					
    					// Update i here to avoid reprocessing of the valueinside []
    					// -1 is done as endoffset brings us to the value next to ']'
    					i = endOffset-1; 
    
    				} else if(str.charAt(i)=='[' || str.charAt(i)==']'){
    					// do nothing
    				} else{
    					result = result + str.charAt(i);
    				}
    			}
    			
    			
    		}
    	}
    	
    	// Function to calculate the offset at which the bracket closes ']'
    	private static int bracketSize(String str, int offset){
    		
    		int ctr=0;
    		char ch = str.charAt(offset);
    		
    		while(!(ch==']' && ctr==0)){
    			ch = str.charAt(offset);
    			if(ch == '['){
    				ctr++;
    			} else if(ch == ']'){
    				ctr--;
    			} 
    			offset++;
    		}
    
    		return offset;
    	}
    }
    
    

  • 0
    A

    For Question.4 Toeplitz Matrix
    Toeplitz Matrix: a matrix in which the diagonal elements are equal
    i.e 0_1503381413389_e830cefe-b7cd-4a27-9b2a-b1b0847743f9-image.png

    Solution with JAVA

    import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Scanner;
    
    public class ToeplitzMatrix {
    
    	private static int N; // columns size of large matirx
    	static BufferedReader bufferreader;
    	
    	public ToeplitzMatrix() throws FileNotFoundException {
    		// reading the file which has matrix data over here
    		bufferreader = new BufferedReader(new FileReader("FileLocation"));
    	}
    	
    	public static void main(String[] args) {
    		/* matrix of size M x N
    		 * We need 2 arrays of size N 
    		 * a GET function which reads a new row from the file and puts it to an array
    		 * Also it is given we can read all the columns 
    		 * */
    		int[] array1 = getNewRow();
    //		int[] array2 = getNewRow();
    		
    		boolean result=true;
    		
    		while(true){
    			int[] array2 = getNewRow();
    			
    			if(array2==null){
    				break;
    			}
    			
    			boolean isValidComparison = compareToeplitzRows(array1, array2);
    			
    			if(!isValidComparison){
    				result= false;
    				break;
    			}
    			
    			// replacing array1 values with array2, so that in new iteration, the new row added is compared to the row above it
    			array1= array2; 
    		}
    		System.out.println("Array Toelitz? =" + result);
    	}
    	
    	//This function should read new matrix row from file and save it to array
    	private static int[] getNewRow(){
    		int[] newRow = new int[N]; 
    		int ctr=0;
    		try {
    			String line = bufferreader.readLine();
    			Scanner sc = new Scanner(line);
    			
    			while(sc.hasNextInt()){
    				newRow[ctr] = sc.nextInt();
    				ctr++;
    			}
    		} catch (IOException e) {
    			// TODO Auto-generated catch block
    			e.printStackTrace();
    		}
    		
    		return newRow;
    	}
    	
    	
    	// The array1 data from 0 to (n-1) should exactly match the array2 data from 1 to n
    	// i.e array1[0]==array2[1] ; array1[1]==array2[2]; ..... array1[k]==array2[k+1]
    	private static boolean compareToeplitzRows(int[] arr1, int[] arr2){
    		for(int i=0; i<arr1.length-1; i++ ){
    			if(arr1[i] != arr2[i+1]){
    				return false;
    			}
    		}
    		return true;
    	}
    }
    

  • 1
    L

    Question 1: O(lg(n)) running time with binary search:

        int missingNumber(vector<int>& nums) {
            
            int lo = 0, hi = nums.size()-1;
            
            while (lo < hi) {
                int mid = (lo+hi)/2;
                
                // We are left with 2 elements:
                if (hi - lo + 1 < 3) break;
                            
                // Move mid to last element of same number:
                while (mid+1 <= hi && nums[mid] == nums[mid+1]) mid++;
                
                // If mid is at the end of the array we need to move it to the left:
                if (mid == hi) {
                    while (nums[mid] == nums[mid-1]) mid--;
                    mid--;
                }
                
                // Recurse on half that doesn't have 3 * number of elements:
                if ((mid-lo+1)% 3 == 0) {
                    // Right:
                    lo = mid+1;
                } else {
                    // Left:
                    hi = mid;
                }
            }
            
            return nums[lo];
        }
    

  • 0
    S
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.