The interview questions Google asks prospective engineers are tough.
We’ve gathered a new group of questions (and answers) from MyCareerStacks.
Unlike some of the other Google interview questions you’ve seen in the past, these are more computational and logic-based.
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.
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 colouring each house in each of the colours is different.
Figure out how to colour each house so no two adjacent houses have the same colour and the total cost of colouring all the houses is as low as possible.
Convert '--------- 'my career stack' ---------' to ''--------- 'ym reerac kcats' ---------'.
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.
You can find the whole code on MyCareerStack.
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.
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).
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.
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.
You can see the full solution on MyCareerStacks.
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.
When we have a biased coin, then the probability of a head and a tail is not the same.
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.
For example, find that 'newspaper' can be made by 'news' and 'paper.'
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.
But, you find it empty for nine consecutive days in a row.
Find the probability that it will be empty on the tenth day.
It's a tricky probability question, so just go with the answer that's logical.
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.