8 Brain-Busting Interview Questions Google Asks Its Engineers

8 Brain-Busting Interview Questions Google Asks Its Engineers

If you want to prepare for an interview at Google, or just see if you have what it takes, you should test yourself with these questions. They will probably pop up in some form during the recruiting process.

Q1. There are a bunch of houses in a row...
We'll say there are "N" houses, where N is some integer. Each house can be painted in either Red, Green or Blue. The cost of coloring each house in each of the colors is different.

Figure out how to color each house so no two adjacent houses have the same color and the total cost of coloring all the houses is as low as possible.

A. It's actually a programming problem.

This problem can be modeled as a "Dynamic Programming" problem, a method for efficiently solving a broad range of search and optimization problems.

Here's the line of code you'd use to answer it:

C[i][c] = H[c] + min(C[i-1][x]) x belongs to {Red, Blue, Green} x belongs to c

This function is the cost of painting the row of houses ending at the "ith" house so that house is painted in a color "c." (i is a placeholder for a number that goes up as the function computes.)

"c" is chosen such that the previous house is not in the same color.

Q2. Reverse characters of each word in a sentence
Convert "--------- "my career stack" ---------" to ""--------- "ym reerac kcats" ---------".

A. There's a more clever way to do it than just flipping each character.
You can solve the problem iteratively — by basically plowing through each character and moving it — but there's a clever way to solve it using something called recursion.

This is basically what Google typically wants: Engineers who find the smartest solution, not just a correct solution.

That breaks the problem into smaller problems of reversing each word and then recombining them into a statement.

Q3. Find the best times to buy and sell a stock.
You have an array for which the ith element is the price of a given stock on day "i".If you are only allowed to buy one share of the stock and sell one share of the stock, make an algorithm to find the best times to buy and sell.

A. There's a hidden restriction!

Remember: You have to buy a stock before you can sell it.

This little restriction actually completely changes the outcome of the problem. So now you have to track the minimum value's index. Here's the whole solution:

To solve this problem efficiently, you would need to track the minimum value's index. As you traverse, update the minimum value's index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

 

Q4. There are n coins in a line...

Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Would you rather go first or second? Does it matter?

Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

A: Yes, you want to go first!

Going first puts you in a position where you can make better choices and it will guarantee a win. 

Think in terms of picking odd or even numbered coins. By following this strategy, you will at the very least guarantee a tie:

·         If there are more odd coins than even coins, take the left-most coin in the line, and take all the odd-numbered coins.

·         If there are more even coins than odd coins, then take the right-most, and pick all the even coins.

·         If there are the same number, you guarantee a tie by picking only odd or only even coins.

But what about getting the maximum outcome?

It turns out this is another "dynamic programming" problem — you won't always get the right answer by following the strategy above.

Q5. What are dangling pointers?

Simple enough, right?

A. They're catastrophic bugs.

A dangling pointer is a pointer to storage that is no longer allocated.

But there's a catch — they are catastrophic bugs that don't crash the program until a long time after they are created.

They work on small inputs, but are likely to fail on large or complex inputs. That makes them very tough to find.

Every engineer has to know about these problems, because they can end up killing some of the biggest and most complex parts of a service.

Q6. Find an unbiased decision from a biased coin.

When we have a biased coin, then the probability of a head and a tail is not the same.
 

A. Throw the biased coin twice.

There are four "events" that can occur.

You want to ignore when you have two "heads" results and two "tails" results in a row.

The events left over are a heads-tails combination and a tails-heads combination. Both of these have the same probability of happening — hence it's an unbiased result. 

Q7. Find if a word can be formed by two words in a dictionary.

For example, find that "newspaper" can be made by "news" and "paper."

A. Divide the word into two halves.

Say you have the word "newspaper." You want to split the word in half, which would give you "newsp" and "aper."

Then, check the dictionary. If there's no result, you decrease the length of one of the words and increase the length of the other.

When you do that to "newsp" and "aper," you get "news" and "paper" — which end up in a dictionary.

Q8. A parking spot is unoccupied 1/3 of the time.
But, you find it empty for nine consecutive days in a row.

Find the probability that it will be empty on the tenth day.

A. The answer is still 2/3!

In probability, if an event has already happened, it can't have any effect on the probability of a future event happening.

Even if the parking spot has been empty for nine days, it has no bearing on whether it will be empty on the 10th day.