Google interview questions - fun brain teasers
jhorna.wordpress.com
jhorna.wordpress.com
1. The Fibonnacci sequence starts with 0, 1, 1 and each subsequent term is the sum of the preceding terms. Write out the rest of the sequence. You have 30 seconds.
2. The problem with American democracy is that the qualities tested for during the election process (charisma, fundraising ability) are unrelated to the qualities necessary to be a good leader and policy maker (integrity, sound judgement). Briefly outline a better system of government that is equally fair.
3. How many golf balls will fit in the average blender? Will they blend?
4. Observe that 8 = 5 + 3, 10 = 3 + 7, 12 = 5 + 7; show that all even numbers can be expressed as the sum of two primes.
5. Imagine you are shrunk to the height of a nickel and your mass is proportionally reduced so that your density is the same. Now, how much would you charge to wash all the windows in Seattle? (Note, you can't hire anyone to do it for you, they'll just squish you and keep all the money)
6. Consider the set of all sets which do not contain themselves. Does this set contain itself? Answer yes or no.
7. Using only three sentences, explain to an eight-year-old why she cannot have a puppy. (Cue entrance of crying child)
The point of them is to show you can creatively use what you know to come up with a very quick ballpark figure. This sort of estimation comes up surprisingly often in real life:
1. In physics labs, it was often useful to do a quick estimate of roughly what the answer should be and the likely direction of the error. That way, if we got something way off, we could check the equipment immediately and rerun the experiment if necessary, instead of going home, analyzing everything, finding out we were way off, and having to go back to the lab and collect everything again.
2. When selecting an algorithm, it's good to be able to estimate roughly what the input size will be, so you know if say an N^4 or N! algorithm will work, or if you really need to get it down to linear or N log N.
3. When selecting a startup to work at, it's useful to do a back-of-the-envelope estimate of its market size, to give you an idea of what the startup may sell or IPO for and hence how much you can make off stock options.
4. When founding a startup, it's good to do a back-of-the-envelope estimate of your costs and potential revenues, to make sure that you're not totally uneconomical. (This sort of estimation could probably have prevented debacles like AllAdvantage or Pets.com.)
5. When investing in growth stocks, you can get a good sanity check by estimating their potential market size. For example, in 2002 Akamai was trading at a total market cap of $150M. I did a quick calculation based on the number of computers on the Internet, and figured that the only way they could conceivably be worth $150M or less was if they went bankrupt. Then the question becomes the strength of their product offering and their capital structure, and both of these had fairly easy answers.
http://www.joelonsoftware.com/articles/fog0000000073.html
(Ctrl-F impossible question)
Regarding not recognizing your own ignorance, I think you definitely have to mention in your answer that really you are making up all the numbers and just tackling it in the first logical way you came up with.
Here's one way in C...
void stacktest(void *pa) {
int b;
void *pb = &b;
printf("grows %s\n", (pb < pa) ? "down" : "up");
}
void main() {
int a;
stacktest(&a);
}Also, the same answer basically works to implement "sizeof" for ints.
char a;
long b;
char c;
short d;
The function call is the only reliable way I can think of. Any others?
alloca()
Also, for the two-variable approach something like this should force the compiler to allocate variables in a required order:
int main()
{
int foo;
{
int bar;
...
}
...
}in main: int x; int *p = &x; start writing random data to p, p-1, p-2, etc etc return; if nothing bad happens the stack grows up?
Is this a trick question? The answer is a definite no right? Or is there some tricky detail that I am missing? If the answer is no what is the question for? To see that the candidate can think clearly and don't try to come up with "smart" solutions when not needed?
Now, if the bet were "I win $x if any two people at the party have the same birthday, you win $x if none do" then that is exactly the birthday paradox. If there are 23 or more people at the party then the probability is greater than 50% and you should take the bet.
So unless I'm missing something it's either a stupid question or a trick question.
Some of the questions they did ask however included one about polymorphism, and how C++ deals with constructors and deconstructors of a class and its child class. And one where they asked to write a function that flips the bits inside a byte (either in C++ or Java) while saying out loud your thought process. And one where they asked to write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.
I would think start running around in circles until the blender turns over. Heh.
Take (any) 6 of the balls, and divide into 2 groups of 3. Weigh the groups of 3 against each other on the balance.
If one group is heavier: The heavier ball is in that group of 3. So take (any) 2 of the 3 balls in that group, and weigh them. If either is heavier, you've found the heavy ball. If those two weigh the same, the 3rd ball is the heavy one
If both groups weigh the same: The heavy ball is one of the remaining 2 balls. Weigh those two to see which is heavier.
Given n weighings you can actually identify the heavy ball out of a group of upto 3^n balls.
If you remove the condition that one of the balls is heavier and just say that one of the balls weighs differently, instead of slightly more, you can no longer solve it in 2 weightings.
In an interview, you can follow up the listed question with this one to see the response.
If, as the problem is usually posed, all pirates get to vote on a division of loot, then the lead pirate can indeed get away with the hinted 98 coins.
But the article says that "the other pirates get to vote on his plan and if fewer than half agree with him...", implying that the lead pirate does not get to vote. The solution requires different logic -- I think the best the lead pirate can do in this case is 97 coins.
.. I wasn't expecting it and it totally threw me. I worked it out though.
... in binary.
Seriously though, I think a lot of times questions like that are trick questions. Unless it's something totally idiotic, it probably can't hurt to give the simple answer first before working out the more complicated answer, especially if you make it clear you know it's the simpler of two answers.
To work it out in your head (in decimal you cheater! :D ) you need to know a bit about dealing with powers of two.
<Spoiler alert!>
So for example, if you happen to know that 2^32 is roughly 4 billion, then you can figure out that 2^64 is 2^32 squared.
4 billion is 4x10^9 .. so 2^64 is roughly 16x10^18.
http://www.google.com/search?q=There%27s+a+black+widow+at+th...
What do you see? My stupid comment. WTF? Obviously, ynews is rated extremely high by google.com. This seems like a design flaw, since any idiot [1] can post here. The quote comes from a very funny sequence [2] in the simpsons when homer subscribed to a questionaire-only magazine:
http://www.snpp.com/episodes/BABF16
[1] eg: me, drunk off my ass
[2] The sequence was funny, the episode was stupid
If all 100 men have cheated then every woman already knows that 99 men have cheated, and the queen's announcement doesn't add any new information.
Now, if the women can tell each other that they know 99 men cheated, then all women will instantly know their husbands cheated and must kill them (even before the queen makes her announcement). If they can't communicate, they have no way of knowing their own husband cheated (even after the queen makes her announcement, the "at least 1 husband" could have been any of the other 99, or hers, but she can't prove that).
Or am I missing something?
Since W1 considers it a possibility that her husband, H1, was faithful, she won't do anything the first day; instead she'll just wait to see whether W2 kills H2.
By symmetry W2 will go through the same line of reasoning about W1. Thus, both will do nothing the first day. So then on the second day, W1 will realize that (just H2 is a cheater) must be false, since W2 didn't kill H2. So, she'll go ahead and kill W1. (Apply the same reason symmetrically to W2). Therefore, they'll both kill their husbands on the second day.
The rest of the details are pretty easy to establish. The point is that 99 days later all the men are killed.
If all 100 men have cheated then there's no "asymmetry", so which wife kills her husband first? Wouldn't they have to kill all the husbands at the same time or not at all?
1) The women can't tell each other anything
2) Every woman knows the following fact: "every woman knows when a husband other than her own cheated".
Now, let's simplify the problem and say that there are only 3 women as opposed to 100, and assign numbers to them and their respective husbands.
Woman #3 thinks "I know that husband #1 and husband #2 cheated. Woman #2 knows that husband #1 cheated. Woman #1 sees that woman #2 and I (woman #3) are not killing our husbands, which logically would mean that her husband is the cheater. However, she (Woman #1) is capable of going through this thought process, and is yet not killing her husband. That means that she is thinking of either husband #2 or my husband (#3) as the cheater. Yet, woman #2 is capable of going through this thought process as well, and if my (#3) husband was not a cheater, then woman #2 would've killed her husband. Yet she hasn't, which means that my husband (#3) is the cheater. So, I have to go kill him".
Now, there was nothing special about woman #3 - every woman goes through this thought process simultaneously, and all arrive at the same conclusion. Now, expand to 100.
Maybe my explanation is a little muddy, and I am not giving enough justification to the last step of "simultaneous thought process", but I am pretty sure that this is the right method for solving the problem.
Since a woman can't be sure that any other woman is planning a killing until the next day, the massacre takes place on the 100th day, not immediately.
Consider the case with two couples, (1) and (2). (1) knows that (2) cheats, so when the queen says that at least one man has cheated, (1) knows of two possibilities: either [a] only (2) has cheated or [b] both (1) and (2) have cheated. If [a] is true, then (2) will immediately know (2) cheated, since she knows that (1) has not cheated. Thus, if by the end of the first day, (2) has not killed her husband, (1) knows that [b] must be true. The numbering is arbitrary, so every woman kills her husband after one day.
Now consider the case of 3 couples (1), (2), and (3). From the point of view of (1), (2) and (3) have cheated. (1) also knows that (2) knows whether (1) has cheated or not, so (1) considers what (2) is thinking: "(2) either sees that [a] (1) and (3) have cheated or [b] that only (3) has cheated. If [b] is true, then (2) will be able to figure out whether (2) has cheated like this: since [b] is true, (3) will kill her husband on day 1 if (2) has not cheated. If she has not, then (2) must have cheated. If however, [a] is true, no one will have killed their husband after 2 days" Therefore (1) waits 2 days and kills her husband.
With 2 couples it goes:
Both women know that the other man has cheated but they don't know if their own has. So when the queen says one has cheated at first they don't kill their husbands becuase it could be the other one. But if the other woman didn't know the others man had cheated the cheater had to be their own but since she didn't she must know the other has cheated. So they will both kill their husband after figuring that out.
But i am not sure this is the same for 3 and more couples. Can they make the same deduction? If the queen said that 99 other men had cheated, yes, but 1? I don't see it.
On the first day, nothing happens, which surprises no one, since all the wives know there are multiple guilty parties.
On the second day, nothing happens again. A wife reasons: "If my husband were innocent, then the other two wives would see only each other's husbands as cheaters, which is the same situation as if me and my husband were not on the island at all. By the logic of the two-cheating-couple case, they should then have killed their husbands today. Since they did not, my husband must have cheated, too."
Thus, all the wives kill their husbands on the third day.
The logic extends easily to more couples.
Perhaps the kind of solution they're looking for is something along the lines of "Only if I knew that seven of the other people's birthdays matched mine." Or maybe this is simply one of those "impossible" questions designed to test your creativity.
The same way you impress your clients you have to impress the people interviewing you.
Also, these are fun to do and give your brain a slight workout.