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;
    	}
    }
    

  • 3
    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!

  • 0
    P
    import string
    def decompress(s):
        # a3[b2[c1[d]]]e -> abcdcdbcdcdbcdcde
        if not s:
            return ''
        elif s[0] in string.ascii_letters:
            return s[0] + decompress(s[1:])
        elif s[0] in string.digits:
            i = 0
            while s[i] in string.digits:
                i += 1
            last_bracket = s.rfind(']')
            return int(s[:i]) * decompress(s[i + 1:last_bracket]) + decompress(s[last_bracket + 1:])
    

  • 0
    R

    Code for question 2 (in python)

    
    import re
    def deCompress(text):
        st = re.findall('\d\[[a-z]+\]',text)
        if(len(st) == 0):
            return text
        st = st[0]
        num = int(re.findall('\d+',st)[0])
        ch =  str(re.findall('[a-z]+',st)[0])
        repCh = ""
        for i in range(0,num):
            repCh = repCh + ch
        
        text = text.replace(st,repCh)  
        return deCompress(text)
    
    

  • 1
    K
    
    """
    Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.
    eg: 11122333 : Missing number 2
    11122233344455666 Missing number 5
    """
    
    
    def missing_number(num):
        dict ={}
        
        while num>0:
            rem = num%10
            
            if rem not in dict:
                dict[rem] = 1
            else:
                dict[rem] = dict.get(rem) + 1
            
            num = num//10
        
        for key, val in dict.items():
            if val == 2:
                print (key)
                
    
    missing_number(1112233344)
    

  • 0
    Z

    solution of the second problem:

    def decStr(str,idx=0):
        rs,i='',idx
        while i<len(str):
            if str[i]=='[':
                ct=int(str[i-1])
                dstr,i=decStr(str,i+1)
                rs+=ct*dstr
                continue
            if str[i]==']':
                return rs,i+1
            if not str[i].isdigit():
                rs+=str[i]
            i+=1
        return rs
    

  • 0
    Z

    @ra2630 Small optimization:

    import re
    def deCompress(text):
        st = re.findall('\d\[[a-z]+\]',text)
        if(len(st) == 0):
            return text
        st = st[0]
        num = int(re.findall('\d+',st)[0])
        ch =  str(re.findall('[a-z]+',st)[0])
        text = text.replace(st,ch *num )  
        return deCompress(text)
    

  • 0

    Thanks for your question! Just curious would it be OK if we code in python instead of C++/Java in the interview?


  • 0
    M

    #1 answer, I made it generic so that it should work for any number of repetition including 3. simple binary search algorithm with some modification.

    public static int Missingnum(int[] array, int rep)
    {
      int low =0;
      int high = array.Length-1;
      while (low < high)
      {
       int mid = (low+high)/2;
       int lastendindex = (mid/rep)*rep -1;
    
       //check if missing on left
       if ( lastendindex >= low && array[lastendindex] > (lastendindex+1)/rep)
       {
         high = lastendindex;
       } else if (high < lastendindex + rep || array[lastendindex + rep] > (lastendindex+rep+1)/rep)
       {
          return array[lastendindex+1];
       } else
       {
         low = lastendindex+rep+1;
       }
    
     }
      return -1;
    }
    
    

  • 1

    @BryanBo.Cao

    Yes. Feel free to use Python.


  • 0
    A

    My Solution to Q1

    private static int missingNum(String a) {
    		int len = a.length();
    		int pair = len/3;
    		int res = (pair +1) * (pair +2)/2;
    		int sum = 0;
    		for(int i =0;i<a.length();i++){
    			sum += Integer.parseInt(String.valueOf(a.charAt(i)));
    		}
    		int missingnum = (res * 3)-sum;
    		return missingnum;
    	}

  • 0
    R

    @nidhi32 counter = int(mystack.pop()) assumes that the number is a single digit. It can be 99[a]. You have to keep going until all digits are extracted.


  • 0
    B
     static int idx = 0;
         static String gets(String s, int num){
             String ret = "";
             for(int i=0;i<num;i++){
                 ret+=s;
             }
             return ret;
         }
         
         //a3[b2[c1[d]]]e
        static String parse(String str){
             
             
             char c ;//= str.charAt(idx);
             int num = 0;
             String cur = "";
             
             while(idx<str.length()){
                // System.out.println(idx);
                 c = str.charAt(idx);
                 if(c == ']'){ idx++; return cur;}
                 
                 if(c>='a'&&c<='z'){
                     cur += c;
                     idx++;
                     continue;
                  
                 }
                
                 num = 0;
                     while(c >= '0' && c<='9'){
                         num = num*10 + (c-'0');
                         idx++;
                         c = str.charAt(idx);
                     }
                 //}
                 
                 idx++;
                 
                 
                 cur += gets(parse(str),num);
             
            
             }
            
             return cur;
         }
    

Log in to reply
 

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