I interviewed at Google, here are the GOOGLE INTERVIEW QUESTIONS!

[ones3k]

Originally posted by: JayHu

Originally posted by: ones3k

Originally posted by: DrPizza
I posted this in Highly Technical as well:

Something smells fishy...

ones3k keeps bumping this thread.
Over a week ago, he asked the same question in highly technical as question #1
People immediately suspected it was a request for homework help. He never responded to that accusation.
Now, that same question has been posed, along with other questions, along with the source of the questions: a Google interview.

Anyone think it's odd he didn't mention the interview a week ago?
Nor has he posted a complete correct solution to any of the problems.
Furthermore, he's asked that we post complete solutions for any of the problems for everyone else to see.

ones3k, maybe you're being honest about this, and if so, I apologize.
However, I still smell a plea for homework help.

I'll post the solution to #1:

here it goes:

My solution is to create a binary tree with each leaf representing a stream. We construct the tree from the leaves up. Each node in the tree will contain an integer.

First we insert all K leaves and their corresponding integers (which will be the current element in each stream). From here we construct a "tournament" tree by pairing up nodes at each level and taking the smallest. At the root of the tree we will have the smallest item. Before we move on, please draw this incase im being confusing.

Next, notice that the smallest item (root), must of been compared against the second smallest.

So we increment the stream corresponding to our winning element and update our tree by pushing the new element through the same path as the old element. This is a log(k) operation and we are guaranteed to get the smallest every time because the smallest element beat the second smallest.

so its O(k) to set up the tree and access the first element and O(log(k)) for each stream access thereafter

The structure you're describing is similar to a binary heap.
Except data is stored at all nodes, not just at the leaves. This could be what you're actually thinking of, but your description is less than perfect.

Well yes, data IS stored at every node, just like i said. Every node stores an integer. The solution works 100%

 

[ones3k]

bitches

 

[ones3k]

I am known for bumping my own posts.

 

[manohartvs]

Me fail English?? That is UNPOSSIBLE!

 

[sjgmoney]

From one UMass grad (me) to another (you, hopefully): what did you answer to the blender question?

 

[MaxDepth]

When did they ask you what your top UT2K score was?

 

[ones3k]

Originally posted by: mjrpes3
The big thing I'm curious about is how they let you go about these problems. Was is a verbal interview, and you had to come up with solutions at the top of your head and explain things immediately. Was it a paper test? How much time did they give you to solve these problems.

They explained everything verbally, and we pretty much were expected to get an answer within 10 minutes i would imagine.

 

[ones3k]

Originally posted by: sjgmoney
From one UMass grad (me) to another (you, hopefully): what did you answer to the blender question?

I actually didn't get that question. I added a bunch of questions that others got. And how did you know i go to UMass ?

 

[yllus]

Originally posted by: sygyzy
Have not read replies. Gas station question is an infamous Microsoft interview question. It's the same one I ask people that I interview. I have never had anyone even attempt to answer it. Most of them just laugh and ask if I am serious. The rest just throw out a number "uh 2000?". The point of MS questions is to see how you think.

Here is the answer, if you are interested. Of course there is a real exact answer but nobody is interested in that.

There are 350M people in the United States. Probably half are either children (minors) or senior citizens that can't drive. So now we have about 175M people. We can reduce that a bit further in case there are peopole who carpool, bike, etc. 150M is nice and round.

Most people fill up once every 10 days. That's 3 times a month. Each gas station has on average 6 pumps (personal observation). If it takes 4 minutes to fill up, in one hour a single gas station can service 90 cars per hour (60 mins / 4 mins per car = 15 cars per pump per hour x 6 pumps = 90 cars). Most stations are open 8 hours a day (though there are some that are 24 hours, but of course they service a lot less during off hours. The numbers even out if 15 cars per hour seems high to you). So in a day, a station can service 720 cars.

There have to be at least as many stations as is demand. 150M cars filling up 3 times a month is 450M worth of fillups. In a day a single station can service 720 cars. 720 cars x 30 days is 2160 cars a month per station. 450M fillups / 2160 fillups per station = 208,333 stations.

You can of course modify this as you see fit. You can even do the math in your head by choosing easier numbers. And it could just be an estimated answer (not precise). All are acceptable. But like I said, not a single person ever even *tried* to answer it for me.

Haha, that's interesting. Having read this thread a day or two ago, I've been talking to a couple of friends and even my boss just 10 minutes ago about my approach - which is nearly identical to yours.

I figured on 100 million cars, 4 pumps per station, 5 minutes to fill up. That means that 12 times an hour a single station can service 4 cars, or 48 cars an hour / 384 cars a workday / 2688 cars a week.

A car needs a fillup about once a week, or 100 million visits to a gas pump each week. To meet that demand, we're talking about 100 million visitors per week / 2688 visit capacity per week = 37,202 gas stations to meet the demand.

I got to figuring out 48 cars per hour in my head and had to write the rest down - of which I probably got some logic incorrect. Pretty weird that nobody even attempted the question, though - is this a tech job? Almost everyone I know was up to the task.

 

[five40]

I didn't read the whole thread but those look like college homework questions. Most of the questions aren't "real world" usable. It seems like Google would ask more specific questions related to stuff they need to get done.

 

[wkinney]

Anyone have an answer for the blender question?

 

[Fritzo]

Whoa. I would read that, look up, and say something like "MMMmmmmm.....potato chips....."

 

[sygyzy]

Originally posted by: yllus
Almost everyone I know was up to the task.

Who knows, the situation might be different if your friends were being interviewed. Yes, it is a tech job.

 

[cchen]

Originally posted by: sygyzy
Have not read replies. Gas station question is an infamous Microsoft interview question. It's the same one I ask people that I interview. I have never had anyone even attempt to answer it. Most of them just laugh and ask if I am serious. The rest just throw out a number "uh 2000?". The point of MS questions is to see how you think.

Here is the answer, if you are interested. Of course there is a real exact answer but nobody is interested in that.

There are 350M people in the United States. Probably half are either children (minors) or senior citizens that can't drive. So now we have about 175M people. We can reduce that a bit further in case there are peopole who carpool, bike, etc. 150M is nice and round.

Most people fill up once every 10 days. That's 3 times a month. Each gas station has on average 6 pumps (personal observation). If it takes 4 minutes to fill up, in one hour a single gas station can service 90 cars per hour (60 mins / 4 mins per car = 15 cars per pump per hour x 6 pumps = 90 cars). Most stations are open 8 hours a day (though there are some that are 24 hours, but of course they service a lot less during off hours. The numbers even out if 15 cars per hour seems high to you). So in a day, a station can service 720 cars.

There have to be at least as many stations as is demand. 150M cars filling up 3 times a month is 450M worth of fillups. In a day a single station can service 720 cars. 720 cars x 30 days is 2160 cars a month per station. 450M fillups / 2160 fillups per station = 208,333 stations.

You can of course modify this as you see fit. You can even do the math in your head by choosing easier numbers. And it could just be an estimated answer (not precise). All are acceptable. But like I said, not a single person ever even *tried* to answer it for me.

Seems like a typical consulting question, but for a consulting interview, the interviewee would have to estimate all the numbers

 

[sygyzy]

cchen - In ANY interview, you would be expected to estimate. I don't expect the interviewees to actually give me an exact answer.

 

[statik213]

Originally posted by: Beattie

Originally posted by: statik213

Question #6) Given a square with side length = 1, describe all points inside square that are closer to the center of the square than to the edge of the square.

Why is everyone overthinking this question?
Isn't it simply all the points within the square with side lenght 1/2 centered at the same point as the bigger square?

Short answer, no.

Long answer, Do the math.

Simple explanation. Think of a corner of the small square. Lets say the upper right one. It would be how far from the side of the larger square? 1/4. how far is that point from the center? well, it's the hypotenuse of the triangle formed by lines from the center straight to that right edge, and the line from then center of that right edge to the upper right corner. The hypotenuse of a triangle with sides equal 1/4 is going to be longer than 1/4, right?

ok

 

[mugs]

Originally posted by: statik213
ok

See the pictures I posted and DrPizza's explanation.

 

[cchen]

Originally posted by: sygyzy
cchen - In ANY interview, you would be expected to estimate. I don't expect the interviewees to actually give me an exact answer.

whoops! i thought you said that was what was given

 

[statik213]

Originally posted by: wkinney
Anyone have an answer for the blender question?

just move to the center of the blender? the blades are gonna pass over ur head.... less airflow in the middle of the blender (eye of the hurricane?)... wait it out?

 

[ones3k]

Originally posted by: wkinney
Anyone have an answer for the blender question?

Jump into the moving blades

 

[wkinney]

Originally posted by: ones3k

Originally posted by: wkinney
Anyone have an answer for the blender question?

Jump into the moving blades

ohhhhhhhhhhhhh

 

[ones3k]

bump

 

[simms]

Originally posted by: statik213

Originally posted by: wkinney
Anyone have an answer for the blender question?

just move to the center of the blender? the blades are gonna pass over ur head.... less airflow in the middle of the blender (eye of the hurricane?)... wait it out?

In the middle is a good answer. The blades won't get you, but the material being mixed will. Unless it's just YOU in an empty bowl, middle would probably be the right answer.

edit: It DOES say empty. But it is a BLENDER... not a mixer like we're thinking.

It's THIS: http://www.lightner.net/ybdb/images/blender/blend-dh.jpg

Not THIS: http://www.otal.umd.edu/~vg/images/mixer1.gif

 

[simms]

What is probably right is to lie on the bottom of the glass blender, so the blades rotate above you. Given that if you are the size of a nickel, you probably weigh MUCH less than a nickel! Probably a few grams, so let's hope the air flow isn't too turbulent or you just might fly up and out

 

[ones3k]

Originally posted by: simms
What is probably right is to lie on the bottom of the glass blender, so the blades rotate above you. Given that if you are the size of a nickel, you probably weigh MUCH less than a nickel! Probably a few grams, so let's hope the air flow isn't too turbulent or you just might fly up and out

Exactly, thats why i say throw yourself into the blades and end it all