Google Questions Flashcards

1
Q

What is your favorite Google product, and how would you improve it?

A

My favorite Google product is Google Maps. It’s helped me find my way when I’ve been lost either in town or on my travels, and I love how it shows me where there’s traffic or other potential sources of delays. To improve it, I would offer customers a paid, live map version that doesn’t require data to see paths to certain areas. This will help people traveling in remote communities, without access to data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Briefly explain the difference between coding and programming.

A

Coding strictly refers to writing code for implementing a solution to a problem. Programming, although wrongly used interchangeably with coding, is a wider process that involves coding as well as coming up with an approach for solving a particular problem and other program development tasks like testing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Google Behavioral Interview Questions
How do you stay accountable?

A

I have a few tools that help me stay accountable, apart from my own integrity. I love using calendar apps and project management tools like Asana to track my deliverables and make sure I keep track of my due dates. I set aside time to complete each task in advance, and communicate with my superiors and colleagues if I need more time in an extreme situation. I also make sure I schedule meetings with stakeholders or team members well in advance of a project due date to ensure we’re on the same page for a project.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Tell me about a time when you set and achieved a goal?

A

In my last position as X, my supervisor told us that we couldn’t meet our quota due to being short-staffed. While the reduced workload was appreciated by me and my colleagues, I thought that we would be better off meeting our original goal despite being short a team member. I organized a meeting with my colleagues and made an argument for pushing our workloads to meet our originally intended goal. I tried my best to encourage their participation so that we could work as a team to get it done. With enhanced communication and extra effort in coordinating extra tasks, we met our end-of-year quota and kept our original commitment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Technical Questions for Coding, Engineering, Logic, and Data

How can you learn the identity of a person under these circumstances with the minimum number of questions asked? How many ways can we solve this problem?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

First Solution - Brute Force Search Method

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Second Solution - Using Recursion

A

Recursion allows us to decompose the entire problem into a combination of smaller instances. Here, 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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Third Solution - Using Stack

A

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 you’re left with only one person.
Ensure that the remaining person is the person we are searching for.
To ensure 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 Are Known (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 attendees.
The Areknown (A, B) function will be called 3(N-1) times, provided the person is present at the party.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Could manhole covers be any shape other than round, like a rectangle?

A

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 the cover were a rectangle or square, then it could easily fall in.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Which of the following sets do not belong?

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is DEADBEEF?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

We can solve this problem in two ways. 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 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 twice, with the second 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 uses 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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

The power set of a given set contains all the possible combinations of the elements, i.e., all the subsets of a given set, 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]].

Here’s the 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, find 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].

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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.

Here’s a general algorithm to find 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].

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

Programming allows us to teach computers to do specific things. A programming language is like a language that we speak, except computers speak it.

17
Q

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

A

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

18
Q

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

A

Divide three by seven and then add 3 to the result. After, multiply the result with 7 to get 24:

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

19
Q

Is the interval (3, 7) covered for these location coordinates, [[1, 3], [2, 5], [5, 7]]? Is it covered in this list [[2, 3], [3, 4], [5, 6], [6, 7]]?

A

Points 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.

20
Q

Suppose you have six glasses lined up in a row with the first three filled with juice and the last three empty. How can you arrange the glasses in an alternating pattern by only swapping once?

A

Let us represent the glasses filled with juice by J and empty glasses by E:

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, by replacing the fourth glass with the first, and the fifth with the second.

To achieve the J E J E J E pattern, we need only one swap, which is replacing the 2nd glass with the 5th.

21
Q

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

A

Here are three 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 the 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): We can use sorting to find the triplets with a sum equal to zero. 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.
If the sum is 0, then print the triplet and do l++ and r–.
If the sum is less than 0, then l++.
If the sum is greater than 0, then r–.
If the sum doesn’t exist in the array, then print not found.
Auxiliary Space: O(1)

Time Complexity: O(n2)

22
Q

How many months have 28 or 29 days?

A

All 12 months have 28 or 29 days.

23
Q

When, and how many times do a clock’s minute and hour hands overlap in one day? Explain mathematically.

A

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 is 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 two 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 give us 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 a.m.
01:05 a.m.
02:10 a.m.
03:15 a.m.
04:20 a.m.
05:25 a.m.
06:30 a.m.
07:35 a.m.
08:40 a.m.
09:45 a.m.
10:50 a.m.
12:00 p.m.
01:05 p.m.
02:10 p.m.
03:15 p.m.
04:20 p.m.
05:25 p.m.
06:30 p.m.
07:35 p.m.
08:40 p.m.
09:45 p.m.
10:50 p.m.

24
Q

What’s the next number in this series: 10, 9, 60, 90, 70, 66

A

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

10: ten (3 letters)

9 : nine (4 letters)

60: sixty (5 letters)

90: ninety (6 letters)

70: seventy (7 letters)

66: sixty-six (8 letters)

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

25
Q

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

A

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

The day before yesterday was Wednesday, and
yesterday was Thursday.
Therefore, today is Friday.

26
Q

Garry is 16 years old, and four times older than his younger brother James. How old will Garry be when he’s twice the age of James?

A

Garry is 16 years old, four times the age of his younger brother James. So, James is 4 years old, or 16/4.

This means that Garry, at 16 years of age, is 12 years older than James.

Let’s 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)

Also:

x = 12 + y - (II)

x = 2y = 12 + y

2y - y = 12

y = 12

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

27
Q

How can you get a sum of 10000 by adding only 8?

A

To get 10000 only by adding 8, we must add 8 three times, then 88, and 888:

8 + 8 + 8 + 88 + 888 = 10000

28
Q

Suppose you have 8 balls. 7 weigh the same, while the 8th is slightly heavier. How can you find the heavier ball by comparing the balls only twice?

A

Out of the 8 balls, take 6 of them. Now, divide them into triplets and place them on either side of a weighing machine. If the weights are equal, 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 among the remaining two balls then:

Place each of them on either side of the weighing machine to find the heavier ball.

If the ball is among one of the triplets:

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.

29
Q

Which number doesn’t belong in this series: 0, 1, 1, 2, 3, 4, 5, 8, 13, 21

A

This series represents numbers that are the sum of the previous two numbers. The number 4 doesn’t belong to the series, as the 3 and 2 do not add up to equal 4. The correct sequence would be:, 0, 1, 1, 2, 3, 5, 8, 13, 21.

30
Q

Reviewing Google interview questions and answers is a great start for your interview prep. Here are some other helpful tips to prepare

A

Research the latest about Google in the news, including new developments and products, expansions, legal issues, and anything else relevant.
Review the job position specifications in great detail before your interview.
Talk to your network and see if anyone has gone through the Google interview process, and ask them for any tips.
Prepare early.
Get a good night’s rest and get to your interview early.

31
Q

At the end of your interview(s) with Google, the interviewer might ask you if you have any questions for them. The worst thing you can do here is say “no.” Show your interest, commitment, and engagement by presenting them with some thoughtful questions.

A

What does an average day look like for someone in my role?
How would you measure success in the position I’m interviewing for?
What’s your favorite part about working for Google?
What’s the most challenging part about this position?