Top 5 DSA Interview Questions Asked at Google

Hey guys 👋 Welcome to our another blog on Data Structures and Algorithms ! Today, we will solve the top 5 DSA interview questions asked by the tech giant Google. So without further adieu, let’s get started:

1. Flood Fill Algorithm 🎨

In MS-Paint, when we take the brush 🖌️ to a pixel and click, the color of the region of that pixel is replaced with a new selected color. Following is the problem statement to do this task.

Given a 2D screen, location of a pixel in the screen and a color, replace color of the given pixel and all adjacent same colored pixels with the given color. For example,

Question:

Solution:

Example:

Input:
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
               {1, 1, 1, 1, 1, 1, 0, 0},
               {1, 0, 0, 1, 1, 0, 1, 1},
               {1, 2, 2, 2, 2, 0, 1, 0},
               {1, 1, 1, 2, 2, 0, 1, 0},
               {1, 1, 1, 2, 2, 2, 2, 0},
               {1, 1, 1, 1, 1, 2, 1, 1},
               {1, 1, 1, 1, 1, 2, 2, 1},
               };

    x = 4, y = 4, newColor = 3
The values in the given 2D screen indicate colors of the pixels. 
x and y are coordinates of the brush, newColor is the color that should replace 
the previous color on screen[x][y] and all surrounding pixels with the same color.

Output:

Screen should be changed to following.
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
               {1, 1, 1, 1, 1, 1, 0, 0},
               {1, 0, 0, 1, 1, 0, 1, 1},
               {1, 3, 3, 3, 3, 0, 1, 0},
               {1, 1, 1, 3, 3, 0, 1, 0},
               {1, 1, 1, 3, 3, 3, 3, 0},
               {1, 1, 1, 1, 1, 3, 1, 1},
               {1, 1, 1, 1, 1, 3, 3, 1},
               };

Ans:

This question can be solved by using Recursion 🔄. The concept is simple: here we first replace the current pixel's color, then recur for four surrounding points. The following is a detailed algorithm:

Here, first change 2 to 3 and then check for surrounding pixels

• There is a recursive function to replace the previous color 'prevC' at '(x, y)' along with all the surrounding pixels of (x, y) with the new color 'newC' and floodFill(screen[M][N], x, y, prevC, newC).

• If x or y is outside the screen, then return.

• If color of screen[x][y] is not same as prevC, then return.

• Recur for north, south, east and west :

1. floodFillUtil(screen, x+1, y, prevC, newC);

2. floodFillUtil(screen, x-1, y, prevC, newC);

3. floodFillUtil(screen, x, y+1, prevC, newC);

4. floodFillUtil(screen, x, y-1, prevC, newC);

Code:

2. The Celebrity Problem 🙎‍♀️🤳

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.

We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, false otherwise. How can we solve the problem?

Example:

Input:
MATRIX = { {0, 0, 1, 0},
           {0, 0, 1, 0},
           {0, 0, 0, 0},
           {0, 0, 1, 0} }
Output:id = 2
Explanation: The person with ID 2 does not 
know anyone but everyone knows him

Input:
MATRIX = { {0, 0, 1, 0},
           {0, 0, 1, 0},
           {0, 1, 0, 0},
           {0, 0, 1, 0} }
Output: No celebrity
Explanation: There is no celebrity.

Ans:

This problem can be solved using 🔄 Recursion. If the ‘potential celebrity’ of N-1 persons is known, then the solution to N be found from it. A potential celebrity is one who is left after removing n-1 people. The n-1 people are eliminated with the strategy given below:

• If A knows B, then A cannot be a celebrity. But B could be.

• Else If B knows A, then B cannot be a celebrity. But A could be.

The approach, as mentioned above, uses Recursion to obtain the potential celebrity amongst n persons, recursively calls n-1 persons, until the base case of 0 persons is reached. For 0 persons, -1 is returned, which indicates that there are no probable celebrities as there are 0 people. In the ith stage of Recursion, the ith person and (i-1)the person are compared to check if they know the other. Using the above logic, the potential celebrity is returned to the (i+1) stage.

As soon as the recursive function returns an id, we will check if this id does not know anybody else, but all the others know this id. If this is true, then this id will be the celebrity.

Algorithm :

• Write a recursive function that takes an integer n.

• Check the base case; if value of n is 0, then return -1.

• Call the recursive function and get the ID of potential celebrity from the first n-1 elements.

• If the id is -1, then allot n as the possible celebrity and return the value.

• If the possible celebrity of the first n-1 elements knows n-1, then return n-1 (0 based indexing).

• If the celebrity of the first n-1 elements does not know n-1, then return id of the celebrity of n-1 elements (0 based indexing).

• If not, then return -1.

• Then create a wrapper function to check whether the id returned by the function is the celebrity or not.

Code:

3. Unbounded Knapsack 💰 (Repetition of items allowed)

Given a knapsack weight W and a set of n items with certain value

val[i]

and weight

wt[i]

we need to calculate the maximum amount that could make up this quantity exactly ⚖️. This is different from the classical Knapsack problem, here we are allowed to use an unlimited number of instances of an item.

Example:

Input : W = 100
       val[]  = {1, 30}
       wt[] = {1, 50}
Output : 100

There are many ways to fill knapsack.
1) 2 instances of 50 unit weight item.
2) 100 instances of 1 unit weight item.
3) 1 instance of 50 unit weight item and 50
   instances of 1 unit weight items.
We get maximum value with option 2.


Input : W = 8
       val[] = {10, 40, 50, 70}
       wt[]  = {1, 3, 4, 5}       
Output : 110 
We get maximum value with one unit of weight 5 and one unit of weight 3.

Ans:

It is an unbounded knapsack problem as 1 or more instances of any resource can be used. We will use a simple 1D array, say dp[W+1] such that dp[i] will store the maximum value which can be achieved using all the items and the i capacity of knapsack. Note that 1D array is used here which differs from the classical knapsack where we use 2D array. Here, the number of items never changes. We will always have all items available.

We can recursively compute dp[] using below formula:

dp[i] = 0 dp[i] = max(dp[i], dp[i-wt[j]] + val[j] where j varies from 0 to n-1 such that: wt[j] <= i result = d[W]

Code:

4. Meta Strings (Check if two strings can become same after a swap 🔂 in one string)

Given two strings, the task is to check ✅ whether these strings are meta strings or not. Meta strings are the strings which can be made equal by exactly one swap 🔂 in any of the strings. Equal strings are not considered here as Meta strings.

Example:

Input : str1 = "geeks" 
        str2 = "keegs"
Output : Yes
By just swapping 'k' and 'g' in any of string, 
both will become the same.

Input : str1 = "rsting"
        str2 = "string
Output : No

Input :  str1 = "Converse"
         str2 = "Conserve"

Ans:

• First, check if both the strings are equal in length or not, if not then return false.

• Otherwise, start comparing both the strings and count the number of unmatched characters. Also store the index of unmatched characters.

• If unmatched characters are greater than 2 then return false.

• Otherwise check if swapping any of these two characters in any string would make the string equal or not.

• If yes then return true. Otherwise return false.

Code:

5. Print all Jumping Numbers smaller than or equal to a given value

A number is called a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

Given a positive number x, print all Jumping Numbers smaller than or equal to x. The numbers can be printed in any order.

Example:

Input: x = 20
Output:  0 1 2 3 4 5 6 7 8 9 10 12


Input: x = 105
Output:  0 1 2 3 4 5 6 7 8 9 10 12
         21 23 32 34 43 45 54 56 65
         67 76 78 87 89 98 101

Note: Order of output doesn't matter, 
i.e. numbers can be printed in any order

Ans:

A straightforward solution is to traverse all the numbers from 0 to x. For each traversed number, check if it is a jumping number. If it is a jumping number, then print it. Otherwise, ignore it. The time complexity of this solution is O(x).

A better and efficient solution is to solve this problem in O(k) time, where k is the number of jumping numbers smaller than or equal to x. The approach is to use BFS or DFS . Assume that we have a graph where the starting node is 0, and we need to traverse it from the start node to all the reachable nodes.

Code:

So we have completed the 5 Data Structures and Algorithms questions that are repeatedly asked in Google interviews. If you liked today’s blog, please share it with your friends as well!

Learn Data Structure & Algorithms with Python course for beginners

For more such cool blogs and projects, check out our YouTube channel