Google Questions Flashcards
What is your favorite Google product, and how would you improve it?
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.
Briefly explain the difference between coding and programming.
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.
Google Behavioral Interview Questions
How do you stay accountable?
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.
Tell me about a time when you set and achieved a goal?
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.
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?
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.
First Solution - Brute Force Search Method
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).
Second Solution - Using Recursion
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).
Third Solution - 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 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.
Could manhole covers be any shape other than round, like a rectangle?
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.
Which of the following sets do not belong?
[a, b, c, d]
[a, f, b, g]
[h, i, a, b]
[j, k, l, m]
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.
What is DEADBEEF?
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.
Explain the two-sum problem. In how many ways can we solve it?
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).
Explain the algorithm for finding the power set of a given set.
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].
Is it possible that five minus two equals 4? If yes, how?
Yes, if we remove two alphabets, i.e., f and e from five, we get IV. IV is the Roman numeral representing 4.
Suppose you have an input string 1??0, where ? is a wildcard. Explain the algorithm to find all possible string combinations
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].
