Top 3 Google Interview Questions (Practise Questions)

 

1. Count of strings that can be formed using a, b and c under given constraints.

• Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

  Input : n = 3 

   Output : 19 

   Below strings follow given constraints:

   aaa aab aac aba abc aca acb acc baa

  bac bca bcc caa cab cac cba cbc cca ccb 

  Input  : n = 4

   Output : 39 

  2. Find largest word in dictionary by deleting some characters of given string.

  • Giving a dictionary and a string ‘str’, find the longest string in dictionary which can be formed by deleting some characters of the given ‘str’.
    

    Input : dict = {"ale", "apple", "monkey", "plea"} 

            str = "abpcplea" 

     Output : apple 

    Input  : dict = {"pintu", "geeksfor", "geeksgeeks", 

                                            " forgeek"} 

             str = "geeksforgeeks"

     Output : geeksgeeks

    3. Find subarray with given sum | Set 1 (Non-negative Numbers).

    • Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

     Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33

     Ouptut: Sum found between indexes 2 and 4

     Sum of elements between indices 

     2 and 4 is 20 + 3 + 10 = 33 

    Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7 

      Ouptut: Sum found between indexes 1 and 4

     Sum of elements between indices

     1 and 4 is 4 + 0 + 0 + 3 = 7 

    Input: arr[] = {1, 4}, sum = 0 

     Output: No subarray found 

     There is no subarray with 0 sum