Interview Questions

Google Interview Questions and Answers

Posted in Interview Questions
Google Interview Questions and Answers

Table of Contents

Google needs no introduction. It is among the mightiest tech moguls, in the same league as that of Apple and Microsoft, in the world. As such, it’s only obvious that many professionals and students aspire to work at Google, be a part of the organization that is playing a vital role in powering the I.T. world today.

Now, Google is no slouch when it comes to handpicking, the most talented among the pool of the most deserving candidates. Hence, the hiring process for Google is a long, complex process that requires a thorough approach to successfully make it through. So, let’s first discuss it prior to moving on to discussing important Google interview questions.

Google Interview Process

A typical Google interview is conducted in two phases:

  • Phone/Hangouts interviews: 2 rounds
  • Onsite interviews
  • Coding: 2 to 4 rounds
  • Design: Up to 2 rounds

Now, the phone/Hangouts interviews focus mainly on assessing a candidate for basic problem-solving skills and proficiency in data structures. In order to prepare for the latter, check out these data structure interview questions.

The phone/Hangouts interview round might also aim to check a candidate for personality traits and interpersonal skills. The onsite interviews involve questions based on programming (check out this programming interview questions article), logic, algorithms, and critical thinking.

Specifically, the coding onsite interview round(s) involves whiteboarding solutions to the harder data structure, algorithms, and programming problems. The less experienced the candidate is, the more rounds they must face.

Based on the job profile for which you’re applying at Google, you might be subjected to no, 2, or an in-between number of design rounds. It involves coming up with high-level design architectures for real, practical products. Generally, the more experienced a candidate is, the more rounds they must face.

Top Google Interview Questions and Answers

So now that we’ve understood how the Google interview process works, it’s time to get into the real thing. Without any further ado, here’s our pick of the 30+ relevant Google interview questions:

Question: A party is going on with n number of attendees, with only a single person who is known to every party attendee. This person may be present at the party. However, this person doesn’t know anyone at the party, and we can only ask questions like, does A know B? How will you find the stranger with the minimum number of questions asked? Also, in how many ways can we solve this problem?

Answer: To solve the problem, we need to consider an array with N elements, representing all the party attendees. We also consider a function, are known (A, B). It will return true if A knows B, otherwise false. The problem can be solved in three ways:

  • Using Graphs (Similar to brute force search) - Model the solution using graphs and initializing indegree and outdegree of every vertex as 0. If A knows B, then draw a directed edge from A to B. Increase the in-degree of B and outdegree of A by 1.
    Next, construct all edges of the graph for every possible pair. If the person is present, then we will have a sink node with an in-degree of N-1 and an outdegree of 0, since this person doesn’t know anyone at the party.
    The total time required for finding the sink node, i.e., the person will be (N), and the overall complexity of the problem will be O(N^2).
  • Using Recursion - Recursion allows us to decompose the entire problem into a combination of smaller instances. Next, we solve the problem of the smaller instance during the divide step. When going back, we’ll find the person from the smaller instance, if present.

During the combining step, ensure (check) whether the person is known to everyone and she doesn’t know anyone. The recurrence of the recursive decomposition will be T(N) = O(N2).

  • Using Stack - Based on the elimination method, we have the following observations:
  • If A knows B, then A is not the person while B might be. Thus, discard A.
  • If A doesn’t know B, then B is not the person while A might be. So, discard B.
  • Repeat these two aforementioned steps until left with only one person.
  • Ensure that the remaining person is the person we are searching for.

For ensuring the remaining person is the one we are looking for we can use a stack as follows:

  • Step 1 - Push all the party attendees into a stack.
  • Step 2 - Pop off two persons from the stack. Based on the return status of the AreKnown(A, B) function, discard one of them and push the remaining person on the stack.
  • Step 3 - Continue repeating Step 2 until only one person remains in the stack.
  • Step 4 - Check that the remaining person doesn’t know any other party attendee.

The Areknown(A, B) function will be called 3(N-1) times, provided the person is present at the party.

Question: Manhole covers are round. Would it be ok if they were of some other shape, say rectangle or square?

Answer: No. Manhole covers must be round to avoid them falling inside the manholes. Only a circular shaped manhole cover won’t fall through the manhole. If it were of some other shape say rectangle or square, then the manhole cover can easily fall into the manhole.

Question: Which of the following sets doesn’t belong to the series:

  • [a, b, c, d]
  • [a, f, b, g]
  • [h, i, a, b]
  • [j, k, l, m]

Answer: The [j, k, l, m] doesn’t belong to the series. The three remaining sets are part of the series because all of them have the [a, b] subset in common.

Question: What is DEADBEEF?

Answer: DEADBEEF corresponds to the hexadecimal representation of the 32-bit number, 3735928559. It was used as a magic debug value during the assembly/mainframe times. The DEADBEEF makes it easy to identify while finding and marking specific memory in pages of hex dumps.

Question: Explain the two sum problem. In how many ways can we solve it?

Answer: The two sum problem is a variation of the subset sum problem. The problem involves finding all the pairs of two integers from an unsorted array that adds up to give a sum S.

For instance, if the unsorted array is [22, 24, 36, -3, 5, -17, 14] and the sum (S) is 19, then the program must return [22, -3], [36, -17], [5, 14].

Solution 1 (Normal): The simple solution to this problem is to loop through the entire array and then loop again through the array, but this time looking for a pair that totals to the sum S. The total running time for this solution will be O(N^2).

Solution 2 (Faster): This approach makes use of hash tables. While passing through each element of the array, the method checks whether S - the current element exists in the hash table or not. Hence, we need to loop through the array only once. So, the running time for this solution is O(N).

Question: Explain the algorithm for finding the power set of a given set.

Answer: The power set of a given set is a set that contains all the possible combinations of the elements, i.e., all the subsets of a given set, and an empty set and the given set itself. For example, if S = [0, 1, 2, 3] is the given set, then its power set will be:

P[S] = [[], [0], [1], [2], [3], [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]].

Algorithm for finding the power set of a given set - For a set with N elements, the total subsets will be 2N. Therefore, the algorithm for finding the power set of a given set contains the following steps:

  • Step 1: Loop from 0 to 2N.
  • Step 2: For each number, get the binary representation. For example, four is represented as 0100 in binary.
  • Step 3: Use the binary representation to check whether to include a number from the set or not, e.g., 0100 = [exclude, include, exclude, exclude]

Question: Is it possible that five minus two equals 4? If yes, how?

Answer: Yes, if we remove two alphabets, i.e., f and e from five, we get iv. It is the Roman numeral representing 4.

Question: Suppose you have an input string 1??0, where ? is a wildcard. Explain the algorithm to find all possible combinations of the string.

Answer: The input string is 1??0. Now, the first and the last number will be fixed. The middle two are wildcards, which means they can be either 0 or 1.

Algorithm (general) for finding all the possible combinations of the given string:

  • Step 1: Start by calling the function with the string and an empty set (where we will push 0s and 1s).
  • Step 2: Once the control reaches a? make a copy of each string set, and add 0 for half and 1 for the other half.
  • Step 3: Continue recursively calling the function with a smaller string until the string runs empty.

For the 1??0 Input string, the algorithm works like this:

Initial set = [] (The empty set called in Step 1)

1st character = 1, so set = [1]

2nd character = ?, so a copy of each string set will be made i.e. [1], [1]. Next, 0 is added to one half of the sets and 1 to the other half. Hence, the set = [1, 0], [1, 1]

3rd character = ?, so once again a copy of each string set will be made i.e. [1,0], [1,0], [1, 1], [1,1]. Next, 0 is added to half of the string sets and 1 to the other remaining half. Hence, the set = [1, 0, 0], [1, 1, 0], [1, 0, 1], [1, 1, 1]

4th character = 0, so the final set is [1, 0, 0, 0], [1,0, 1, 0], [1, 1, 0, 0], [1, 1, 1, 0].

Question: How would you explain programming and programming languages to a 10-year old?

Answer: Programming allows us to teach computers to do specific things. A programming language is like a language that is understandable by computers.

Question: Write code to search whether an array has a majority element. If yes, then print it.

Answer: The following C++ program searches for the majority element in an array [10, 22, 22, 21, 22, 23, 22] and then prints it:

#include <iostream>
using namespace std;
void findMajorityElement(int arr[], int n)
{
   int maxCount = 0;  
   int index = -1;
   for(int i = 0; i < n; i++) 
   { 
       int count = 0; 
       for(int j = 0; j < n; j++) 
       { 
           if(arr[i] == arr[j]) 
           count++; 
       }
       if(count > maxCount) 
       { 
           maxCount = count; 
           index = i; 
       } 
   }
   if (maxCount > n/2) 
      cout << arr[index] << endl;
   else
       cout << "No Majority Element Exists in the Array" << endl; 
}
int main()
{
   int arr[] = {10, 22, 22, 21, 22, 23, 22};
   int n = sizeof(arr) / sizeof(arr[0]);
   findMajorityElement(arr, n);
   return 0; 
}

Output:

22

Question: Use the mathematical operations +, -, *, and / on 3, 3, 7, 7 to get 24.

Answer: Divide three by seven and then add 3 to it. Multiply the result with 7 to get 24 i.e.

7 x ((3/7) + 3) = 24

Question: For the given list of location coordinates, [[1, 3], [2, 5], [5, 7]], is the interval (3, 7) covered? What about the same interval in the list [[2, 3], [3, 4], [5, 6], [6, 7]]?

Answer: Point 3 to 7 are covered in the list [[1, 3], [2, 5], [5, 7]] because 2 to 5 and 5 to 7 are covered. However, points 3 to 7 aren’t covered in the list [[2, 3], [3, 4], [5, 6], [6, 7]] because the distance between 4 to 5 is not covered here.

Question: Suppose you have six glasses lined up in a row with the first three filled with juice and the last three empty. How will you arrange the glasses in an alternative pattern, i.e., one glass with juice followed by one empty glass by swapping only once?

Answer: Let us represent the glasses filled with juice by J and empty glasses by E, then we have:

J J J E E E

Now, we wish to have:

J E J E J E

OR

E J E J E J

For the E J E J E J pattern, we need to swap at least twice, i.e., replace 4th with 1st and 5th with 2nd glass. Hence, it is not the solution we seek. To achieve the J E J E J E pattern, we need only one swap, which is replacing 2nd with 5th.

Question: In how many ways can you find all the triplets in a given array of n distinct elements with a sum equal to 0?

Answer: Following are the various ways to find all the triplets with sum zero in a given array of distinct elements:

Approach 1 (Naive Approach): Run three separate loops and check one by one that the sum of the three elements is zero or not. Print all the triplets whose sum equals 0, otherwise print not found.

Auxiliary Space: O(1)

Time Complexity: O(n3)

Approach 2 (Hashing): In this approach, we iterate through every element. For each element arr[i], we need to find a pair with 0 - arr[i]. This approach involves following steps:

  • Run a loop from i = 0 to i = n - 2
  • Create an empty hash table
  • Run inner loop from j = i + 1 to j = n -1
  • If - (arr[i] + arr[j]) is present in the hash table then print arr[i], arr[j] and -(arr[i]+arr[j])
    Else insert arr[j] in the hash table

Auxiliary Space: O(n)

Time Complexity: O(n2)

Approach 3 (Sorting) - Another approach that we can use for finding all the triplets among an array of n distinct elements whose sum equal to 0 is based on sorting. It involves the following steps:

  • Sort the array
  • Run a loop from i = 0 to i = n - 2 and initialize two index variables, l = i + 1 and r = n - 1
  • While (l < r):
    Check whether the sum of arr[i], arr[l], arr[r] is zero or not.
  • In sum:
  • is 0, then print the triplet and do l++ and r--
  • is less than 0, then l++
  • is greater than 0, then r--
  • doesn’t exist in the array, then print not found

Auxiliary Space: O(1)

Time Complexity: O(n2)

Question: How many months have 28 or 29 days?

Answer: All 12 months have 28 or 29 days.

Question: How many times the hands of a clock, minute, and hour hands, overlap one another in a single day, i.e., 24 hours? Explain mathematically. Also, mention the time when they will do so.

Answer: For T hours:

  • Total laps completed by the minute hand = T
  • Total laps completed by the hour hand = T/12

The very first time in the day when the minute and hour hands overlap after 12 am, the former will have completed one more lap than the latter. Hence, for one overlap, the time period T will be:

T = T/12 + 1                                              - (i)

Solving it for T we get,

T = (12+T)/12

12T = 12 + T

12T - T = 12

11T = 12

T = 12/11

So,

T = (12/11) * 60 = 65, which is 1:05 am

65 minutes is also the gap between each successive overlap. Now, the second time the hour and minute hands overlap one another; the minute hand will have completed 2 more laps than the hour hand. So, applying the same logic for N overlaps we get:

T = T/12 + N                                               - (ii)

We have 24 hours in a day, i.e., T = 24. Therefore, solving (ii) will get the total number the hour and minute hands will overlap one another in a day:

24 = 24/12 + N

24 = 2 + N

N = 24 -2

N = 22

So, the minute and hours hand will overlap one another 22 times a day at:

12:00 am, 01:05 am, 02:10 am, 03:15 am, 04:20 am, 05:25 am, 06:30 am, 07:35 am, 08:40 am, 09:45 am, 10:50 am, 12:00 pm, 01:05 pm, 02:10 pm, 03:15 pm, 04:20 pm, 05:25 pm, 06:30 pm, 07:35 pm, 08:40 pm, 09:45 pm, and 10:50 pm.

Question: An airplane crashed, resulting in injuring every single person on the plane except two. Is it possible?

Answer: This is possible because the two persons were married and not single like others on the airplane. So, they also got injured but not as single people.

Question: What will be the next number in the following series: 10, 9, 60, 90, 70, 66?

Answer: If we spell the numbers, then we observe that each successive number has one more alphabet than the one preceding it:

10 - ten (3 alphabets)

9 - nine (4 alphabets)

60 - sixty (5 alphabets)

90 - ninety (6 alphabets)

70 - seventy (7 alphabets)

66 - sixty-six (8 alphabets)

Hence, the number following 66 will be a number with 9 alphabets, like 91 (ninety-one) or 92 (ninety-two).

Question: If the day before yesterday is three days after Saturday, what day is it today?

Answer: Three days after Saturday is Tuesday. So, the day before yesterday is Tuesday. So:

  • The day before yesterday was Wednesday, and
  • Yesterday was Thursday

So, today is Friday.

Question: Garry is four times older than his younger brother James. Find out the age of Garry when he will be twice as old as James. Garry is 16 years old.

Answer: Garry is 16 years old, four times the age of his younger brother James. So, the present age of James is:

16/4 = 4 years

This means that Garry is 16 - 4 = 12 years older than James. Now, let us suppose that Garry is x years old when he is twice the age of his younger brother. Let us represent the age of James at that time by y years. Now, as Garry will be twice the age of James, we get:

x = 2y                                                      -  (I)

But also,

x = 12 + y (Since Garry will always be 12 years older to James)  - (II)

x = 2y = 12 + y

2y - y = 12

y = 12

So, James will be 12 years old when his brother will be twice his age. Hence, the age of Garry at that time will be = 2 x 12 = 24 years.

Question: How will you get 10000 by adding only 8?

Answer: To get 10000 only by adding 8, we must add 8 three times, 88, and 888, i.e.:

8 + 8 + 8 + 88 + 888 = 10000

Question: Suppose you have 8 balls, out of which 7 weigh equal while the remaining one is slightly heavier. How will you find the heavier one by comparing weights only twice?

Answer: Out of the 8 balls, take 6. Now, divide them into triplets and place them on either side of a weighing machine. If they are equal then, the heavier ball must be one of the remaining 2 balls. Otherwise, the side that weighs heavier will have the heavier ball.

If the ball is in the remaining two balls then:

  • Simply place each of them on either side of the weighing machine to find the heavier ball.

Otherwise:

  • Out of the triplets, take 2 balls and place each one of them on either side of the weighing machine. If they weigh equal, then the remaining ball is the heavier one; otherwise, the heavier side will have the heavier ball.

Question: In the series 0, 1, 1, 2, 3, 4, 5, 8, 13, 21, which number doesn’t belong to it?

Answer: The Fibonacci series represent numbers that are the sum of the previous two numbers. The number 4 doesn’t belong to the series as the remaining is the Fibonacci sequence, i.e., 0, 1, 1, 2, 3, 5, 8, 13, 21.

Question: A person wants to climb a staircase of N steps. On each step, there are two climbing choices; either take 1 step or 2 steps. Find out the total number of ways to climb the staircase. What would the programming concept(s) be required to implement a solution to the problem for finding out the various ways in which the staircase can be climbed?

Answer: Let’s observe the solution of the problem starting from the smallest number of stairs, i.e., 1 up to 5 stairs. Let’s represent the total number of solutions with S.

When N = 1, S = 1

When N = 2, S = 2 , The person can:

  • Either take 1 steps twice, or
  • 2 steps once

When N = 3, S = 3, The person can:

  • Either take 1 steps thrice, or
  • 2 steps first and then 1 step, or
  • 1 step first and 2 steps thereafter

When N = 4, S = 5, The person can:

  • Either take 1 step four times, or
  • 2 steps two times, or
  • 1 step first and 2 steps then and 1 step again, or
  • 2 steps first followed by 1 step twice, or
  • 1 step twice and 2 steps thereafter

When N = 5, S = 8, The person can:

  • Either take 1 step five times, or
  • 2 steps twice and 1 step, or
  • 1 step then 2 steps twice, or
  • 1 step followed by 2 steps and then 1 step twice, or
  • 2 steps first followed by 1 step followed by 2 steps
  • 2 steps first and then 1 step thrice, or
  • 1 step thrice followed by 2 steps, or
  • 1 step twice then 2 steps and then 1 step

If we observe the solutions for N = 1 to N = 5, we can see that the total solutions available for N are equal to the total number of solutions for N - 1 and N - 2. Let’s check this:

For N = 3, S = S(3 - 1) + S(3 - 2) = S(2) + S(1) = 2 + 1 = 3

For N = 4, S = S(4 - 1) + S(4 - 2) = S(3) + S(2) = 3 +  2 = 5

For N = 5, S = S(5 - 1) + S(5 - 2) = S(4) + S(3) = 5 + 3 = 8

To find out the total solutions for N, we must be aware of the solutions for the previous two values of N, i.e., N - 1, and N - 2. Hence, for implementing a program to find out the various possible ways to climb a staircase with N ladders, we must use recursion.

Question: How will you predict the score of a football match before it begins and turns out to be true every single time?

Answer: Say 0-0 when the match begins. It will be true for every football match as it will be the opening condition of every match.

Question: What will be the next number in the series 5, 10, 19, 32, 49, 70, 95?

Answer: Subtracting each preceding value from the successive value, we get:

10 - 5 = 5

19 - 10 = 9

32 - 19 = 13

49 - 32 = 17

70 - 49 = 21

95 - 70 = 25

We can observe that each successive difference increases by 4. Therefore, the number after 95 will be 29 more than 95 i.e. 95 + 29 = 124.

Question: Briefly explain the difference between coding and programming.

Answer: Coding strictly refers to writing code for implementing a solution to a problem. Programming, although used interchangeably with coding, is a wider process that involves coding as well as the approach for solving a particular problem and doing other important things related to program development, such as testing.

Know in detail about Coding vs. Programming.

Question: How will you calculate the cube root of a number, upto 6 digits, faster than the traditional approach of mathematically calculating the cube root?

Answer: We can implement this by using table lookups and a trick (mathematical pattern-based shortcut). The algorithm for finding the cube root of a number of max. 6 digits is:

  • Step 1 - Store the first 10 cube roots, their cubes, and the last digit of their cubes in a lookup table.
  • Step 2 - Ignore the last three digits of the number and compare the remaining number (at max 3 digits) with the cubes in the lookup table. Note down the cube root of the cube that is less than or equal to the first three digits.
  • Step 3 - Loop through the table for the last three digits of the number to get the ith index, when i = the last digit of the number. Note down the corresponding the last digit of the cube from the lookup table.
  • Step 4 - Combine numbers from Step 2 and Step 3 to get the answer.

For example, let’s find out the cube root of 912673 using the aforementioned algorithm.

Step 1 - Generating the lookup table:

Number Cube Last digit of the cube
0 0 0
1 1 1
2 8 8
3 27 7
4 64 4
5 125 5
6 216 6
7 343 3
8 512 2
9 729 9

Step 2 - Ignoring the last three digits, we get 912. Comparing it with the cube roots in the lookup table, we get 729<912. So note 9.

Step 3 - The last digit of the remaining three digits, i.e., 673, is 3. Looking for the number in the last digit of the cube column in the lookup table, we get 7.

Step 4 - The cube root of 912673 is 97.

Note: The number supplied to the program must have a perfect cube root.

Question: A casino has 4 gates, namely Gate 1, Gate 2, Gate 3, and Gate 4. There are three conditions here:

  • Entering the casino each time deducts $5
  • Exiting the casino each time deducts $5
  • Entering the casino will double the amount.

A person enters the casino from Gate A and makes an exit via Gate B. The person goes inside the casino again via Gate C and comes out from Gate D. The person is left with no money. Find out the amount of money the person had initially while entering the casino the first time.

Answer: Let us assume the money that the person had while first entering the casino is x. Now:

  • After entering via Gate A the total amount of money the person has = 2(x - 5)
  • Money left with the person while exiting the casino from Gate B = 2(x - 5) - 5 = 2x - 15
  • Total amount the person has while entering the casino again from Gate C = 2(2x - 15) - 5) = 4x - 40
  • Total money the person has while leaving the casino again from Gate D = 4x - 40 - 5 = 4x - 45

Now, we know that the person is left with no money while exiting from Gate D. Therefore, we have:

4x - 45 = 0
4x = 45
x = 45/4
x = 11.25

The person had $11.25 when entering the casino for the very first time.

Question: There is a committee of 10 members. An old member of the committee is now replaced with a younger member. However, the average age for a member of the committee 4 years ago is the same as that of the average member age today. Find out how much younger the new member is from the member he replaced.

Answer: Let’s make the following assumptions:

  • Age of the older/replaced member 4 years ago = o
  • Sum of the ages of the remaining 9 committee members 4 years ago = x
  • Average age of committee members 4 years ago = aold = (o + x)/10
  • Age of the younger member = y
  • Sum of the ages of the remaining 9 members now = z
  • Average age of committee members at present = anew = (y + z)/10

As both the averages are equal i.e. aold = anew, we get:

aold = (o + x)/10 = anew =(z + y)/10

 o + x = z + y                                                                    - (I)

Now, z is the sum of the present ages of the 9 committee members who are all the same. As each of them would be 4 years older now, we get:

z =  x + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4
z = x + 36

Replacing for z in equation (I), we get:

o + x = x + 36 + y
o = y + 36

Therefore, the replaced member is 36 years older than the new member.

Question: A car is driving at 100 mph on a highway. What will be the speed of each of its wheels when they touch the ground? What will be the same when the car is traveling at 120 mph?

Answer: No matter the speed of the car, the wheels will have 0 mph speed at any time while touching the ground. This is because while rolling, the wheel moves in two ways:

  • Rotationally, around its center, and
  • Horizontally, in the direction of the moving car.

At the point of the contact, both motions of the wheels cancel out one another. This results in a net speed of 0 mph with respect to the road.

Conclusion

These questions are only good to give you an idea about how Google interviews are conducted. That means there is a very slim chance of any of these questions asked during your interview, especially the ones that require critical thinking. Anything, however, is possible, and you might get one or many of these questions or similar ones asked during your interview round.

Google holds a repute for asking brain-teasing questions. So, you should always be on your toes and must expect the unexpected. Remember, “if one man can do it, another can do.” Good luck!

P.S. - Check out these best programming tutorials recommended by the hackr.io community.

People are also reading:

Akhil Bhadwal

Akhil Bhadwal

A Computer Science graduate interested in mixing up imagination and knowledge into enticing words. Been in the big bad world of content writing since 2014. In his free time, Akhil likes to play cards, do guitar jam, and write weird fiction. View all posts by the Author

Leave a comment

Your email will not be published
Cancel