Google interview questions - fun brain teasers

http://jhorna.wordpress.com/2007/09/08/google-interview-questions-fun-brain-teasers/

by dangoldin • 18 years ago

31 54 18 years ago

jhorna.wordpress.com

sysop0732• 18 years ago

I don't get questions like "How many golf balls can fit in a school bus?" or "How many piano tuners are there in the entire world?". What is the point of that? To see if you're good at estimating ridiculously large numbers?

dangoldin3• 18 years ago

Just to see your thought process. That's why they recommend to think out loud so the interviewer gets a sense of how you think.

felideon3• 18 years ago

Exactly. If you just stare and be like "I dunno" you may be a bad candidate. If you try to resolve it, even though you are way off with the answer, it means you may be a good candidate.

http://www.joelonsoftware.com/articles/fog0000000073.html

(Ctrl-F impossible question)

nostrademons• 18 years ago

In my physics courses, they used to call these "Fermi estimates" because apparently Enrico Fermi was really, really good at them.

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.

YuriNiyazov5• 18 years ago

How much would you charge to wash all the windows in Seattle: "$100 per window"

YuriNiyazov5• 18 years ago

You are thrown into an empty glass blender, the blades start moving in 60 seconds. What do you do? "Stand under the blades"

felideon3• 18 years ago

Forever?

I would think start running around in circles until the blender turns over. Heh.

DocSavage• 18 years ago

I'd tell jokes, stories, tap dance, something to entertain whoever threw me in, because frankly, if you've been shrunk to a nickle, picked up by some entity, and thrown into a blender, you've got more than just some blender blade to worry about. You need a champion among the big ones.

MaysonL• 18 years ago

Jump out!

YuriNiyazov5• 18 years ago

What happens when the queen says "At least one man has cheated" - "Every woman immediately kills her husband".

tlrobinson6• 18 years ago

Are you sure?

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?

mstoehr• 18 years ago

The solution uses something called common knowledge, which is that everyone knows that everyone knows that every one knows, ad infinitum. Before the queen makes the announcement they may all know that the other husbands are cheating but they don't know if everybody else knows. To see the difference consider the case where there are only two husbands (H1, H2) and two wives (W1,W2). So, every man has cheated on his wife, and when the queen announces that a man has been unfaithful, then consider the situation from W1's perspective. She knows that H2 has cheated on W2, she doesn't know that H1 has cheated on her, and she can't talk to W2 about it. With the announcement, from her perspective, there are two possibilities (both H1 and H2 are cheaters), or (just H2 is a cheater). Now, to continue we need to think about what W1 will think about these two possibilities given her incomplete information: If it were possible world where (just H2 is a cheater) and H1 is honest, then since W2 would know that H1 hasn't cheated then W2 would conclude that (just H2 is a cheater) since at least one husband had cheated. Thus, by the laws of the island W2 would kill H2 the day of the announcement.

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.

YuriNiyazov5• 18 years ago

I took the following assumptions:

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.

globalrev3• 18 years ago

Hmm I am not sure about this one.

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.

jcl5• 18 years ago

It does indeed extend to three or more, as others have outlined above. For three couples:

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.

lfasonar• 18 years ago

Not true. After 99 days, every woman kills her husband.

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.

timcederman• 18 years ago

These aren't Google interview questions.

aasarava• 18 years ago

No, they sound an awful lot like old Microsoft interview questions -- in particular, ones collected in a book called How Would You Move Mount Fuji? I wrote an article about the book for Wired News back in 2003...: http://www.wired.com/culture/lifestyle/news/2003/06/59366

nickb• 18 years ago

By the way, MS improved their interview process and are not asking these stupid questions anymore... well, not putting a lot of focus on them anyway. These types of interviews have been a mixed bag for them.

dhotson2• 18 years ago

A real Google interview question I got asked: "What's 2 to the power of 64?"

.. I wasn't expecting it and it totally threw me. I worked it out though.

tlrobinson6• 18 years ago

10000000000000000000000000000000000000000000000000000000000000000

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

dhotson2• 18 years ago

Actually, it's a pretty good test I think.

To work it out in your head (in decimal you cheater! :D ) you need to know a bit about dealing with powers of two.

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.

jalammar• 18 years ago

I interviewed for Google and they didn't ask any of those.

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.

globalrev3• 18 years ago

14. You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

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?

tlrobinson6• 18 years ago

At first glance this seemed like it might have something to do with the birthday paradox (http://en.wikipedia.org/wiki/Birthday_paradox) but that only says something about the probability that a pair of people out of a group has the same birthday, not the probability that a single person has the same birthday as someone in the group.

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.

tlrobinson6• 18 years ago

I think questions like the golf ball and blender ones are silly, but I like questions like "How would you find out if a machine’s stack grows up or down in memory?".

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);
    }

aston4• 18 years ago

We just talked about this problem in the office yesterday. My officemate got asked this for the job he got at Google, and solved it the same way. His boss pointed out only after he accepted the offer that there's no need to make a function call--just allocate two local vars in main...

Also, the same answer basically works to implement "sizeof" for ints.

pfedor• 18 years ago

Ummmm I may be way off base here but I remember hearing that some implementations (*BSD??) randomly reorder the local variables on stack to make exploiting buffer overruns more difficult. So if it's true then you do need to make a function call.

huhtenberg3• 18 years ago

It is an obvious simplification, but his boss is wrong. The order of uninitialized variables can be changed by the compiler. For example to better package the variables due to an alignment requirements. E.g. allocating

  char a;
  long b;
  char c;
  short d;

on a RISC-style platform as "a,c,d,b" requires 8 bytes, while as a,b,c,d - 12. This may not matter in a majority of cases, but it some it does.

tlrobinson6• 18 years ago

I was actually asked this problem on a job interview (not Google) and gave the answer your boss pointed out, but the interviewer then pointed out that local variables aren't necessarily laid out in memory in the order they're declared.

The function call is the only reliable way I can think of. Any others?

aneesh• 18 years ago

> 16. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

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.

dangoldin3• 18 years ago

I like this question because of you word it slightly differently, you get an entirely different answer.

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.

jcl5• 18 years ago

By the same token, the pirate question in the article is worded incorrectly for its proposed solution.

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.

agranig• 18 years ago

For most of the questions, I as an entrepreneur would answer like "does this really matter?". You normally have other problems than that...

dangoldin3• 18 years ago

Well it's a matter of sales - you have to sell yourself and if that's what they are looking for, you might as well do it.

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.

mynameishere2• 18 years ago

There's a black widow at the door, a rattlesnake in the window, and a scorpion on the phone. Do you: (A) None of the below...

YuriNiyazov5• 18 years ago

Climb out through the chimney?

mynameishere2• 18 years ago

ADDENDUM: My comment is a joke that refers to a simpsons episode. I have the bulk of the series completely memorized, and so I can summon up an appropriate quote for almost any situation. Since most people don't know what I'm talking about, they are likely to pull a quick google:

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

imgabe• 18 years ago

If using ambiguous questions and brainteasers gets Google good employees, then surely using even more ambiguous questions and even harder brainteasers will get a company great employees, right? I propose the following interview questions:

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)

flipbrad• 18 years ago

is the "birthday paradox"-like one there to catch out those that have been training for these questions, spot a birthday question, immediately calculate for 10*9 pairs rather than just 9?

jcl5• 18 years ago

It certainly seems to be some sort of trick question, but it couldn't be to catch the mistake you mention: The bet is a losing proposition even if you win $1 for each person sharing any other's birthday, not just your own. It remains a losing proposition even if you bring the number of people up above 23 (the birthday paradox number) and reverse the 1:2 payoff and assume the bettor has no special information.

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.

Google interview questions - fun brain teasers

Related Stories