Interviewed at Google, here are GOOGLE INTERVIEW QUESTIONS.

[ones3k]

honestly google

 

[doughtree]

What do people think about the blender question? I would try to swim up to the top and climb out but I am not sure if there is any liquid.

 

[ones3k]

I'll post the solution to #1 so you believe me:

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

 

[Mark R]

I'd jump out of the blender

 

[DrPizza]

Originally posted by: ones3k
I'll post the solution to #1 so you believe me:

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

That's what I've been waiting for since you originally posted this question over a week ago.

 

[ones3k]

Originally posted by: DrPizza

Originally posted by: ones3k
I'll post the solution to #1 so you believe me:

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

That's what I've been waiting for since you originally posted this question over a week ago.

Heh, these are seriously Google interview questions. I decided to post them in full once i received the rejection letter

 

[brzrkr0]

I guess they want people who are good at escaping from blenders.

On a more serious note, those questions definitely remind me of something I might see on a CS final exam. However, you'd probably have to be in a graduate-level course to see questions that difficult. A lot of those are beyond anything I had to deal with when working on my bachelor's.

How much time did you have to answer these?

 

[eLiu]

Originally posted by: brzrkr0
I guess they want people who are good at escaping from blenders.

On a more serious note, those questions definitely remind me of something I might see on a CS final exam. However, you'd probably have to be in a graduate-level course to see questions that difficult. A lot of those are beyond anything I had to deal with when working on my bachelor's.

How much time did you have to answer these?

Eh most of them aren't that bad, though I thought some were pretty challenging. I've seen some on math contests...I've gotten one or two of those & many similar (some harder to be honest) questions in my intro CS (Scheme).

I've heard the gas station one before...haha

 

[itachi]

Originally posted by: ones3k
I'll post the solution to #1 so you believe me:

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

sounds a lot more like a binary heap than a binary tree. with a binary heap, you're guaranteed a O(log K) access time since it's essentially a complete binary tree.. and since it's complete, you can allocate the heap as an array in contiguous memory (accesses to 2 different nodes won't be at different locations in memory).

edit:
if you insert all the values into a binary tree so that they're leaves and you take the smallest one as you go up, what're you gonna do if a sub-tree has 2 children (occurs after the 2nd level)? if it has 2 children, then whatever node is merged with it won't have anywhere to go. another problem comes up with keeping the tree sorted. if you insert them in the order you got them, if you only do merges with limited visibility you're running the risk that the tree has an odd order.. or if you do sort them before u insert them, then you'll produce a worst-case tree with a height of O(K).
also.. how would your algorithm handle the streams when log2(K) isn't an integer (results in a level without a pair)?

 

[ones3k]

if you insert all the values into a binary tree so that they're leaves and you take the smallest one as you go up, what're you gonna do if a sub-tree has 2 children (occurs after the 2nd level)? if it has 2 children, then whatever node is merged with it won't have anywhere to go. another problem comes up with keeping the tree sorted. if you insert them in the order you got them, if you only do merges with limited visibility you're running the risk that the tree has an odd order.. or if you do sort them before u insert them, then you'll produce a worst-case tree with a height of O(K).
also.. how would your algorithm handle the streams when log2(K) isn't an integer (results in a level without a pair)?

I don't really understand your argument, but my the tree i described has (worst case) has ceiling(log(k)) depth. The reason is as follows:

let k be # of leaves (# of streams). then if K is even, the next level will have k/2 nodes. If k is Odd the next level will have (k-1)/2 nodes with 1 carry. Each "carry" node will be connected to the tree eventually, worst case it will be connected at the end. But these nodes dont increase the depth at all. Here is a picture

go here <a <href="http://img522.imageshack.us/my.php?image=untitled6xf.jpg" target="_blank"><img src="http://img522.imageshack.us/img522/8936/untitled6xf.th.jpg" border="0" alt="Free Image Hosting at www.ImageShack.us" /></a>

those carry nodes are guaranteed to get hooked into the tree eventually, but these nodes could skip many levels of the tree. For instance, if K = 2^i + 1 for some i. Then the figure will look like a full tree of depth i hooked in with 1 node from the top of the tree. The result would be depth i +1 which is equal to ceiling log(2^i + 1);

 

[itachi]

err nm.. i was wrong about the sorted being O(K), but it still seems like it'd cause problems.

construct your tree with 1 2 3 4 5 as keys
if you 'push' each key down as you construct it without any reordering or reattaching (assuming you pair from left to right), the tree that results is
n 2 n 4 n n n n
n 3 n n
n 5
1

3 is seperated from 1 by 1 empty node.. 2 is seperated from 1 by 2 empty nodes.. 4 is a child of 3.

or let's say that if it has only 1 non-null child, it pulls that up.. if it has 2, it pulls up the smaller one.. construct the tree with 1 3 2 5 4
under the same scenario, you'll get
n n n n n n n n
3 5 n n
2 4
1

mm.. is that what u intended on?

 

[DrPizza]

Incidentally, the answer to the blender question...

IT'S EMPTY!
I'd crouch on the bottom, off to the side, away from the blade. Not much of a difference from standing near a helicopter.


Alternate solution: Since my mass is proportionately small, I could use my clothing as a sort of parachute; when the blades started, the airflow would possibly be sufficient to propel me upward and out of the blender. I would not fear falling to the floor.

alternate alternate solution: What do you mean? Because of the physiology of humans, we cannot be scaled down to that size and survive. An immediate death by being chopped by the blender may be more comfortable than the slow agonizing death as our body's systems failed.

 

[DrPizza]

gas station question: estimate the gas stations in your area, estimate the number of stations per 1000 people.
Population of the U.S. is roughly 300 million; multiply your answer by 300,000
(I'm estimating less than 1 per 1000, more like 1/4 station per 1000 people. )
So, my estimate would be around 75,000

 

[Matthias99]

Originally posted by: itachi
err nm.. i was wrong about the sorted being O(K), but it still seems like it'd cause problems.

construct your tree with 1 2 3 4 5 as keys
if you 'push' each key down as you construct it without any reordering or reattaching (assuming you pair from left to right), the tree that results is
n 2 n 4 n n n n
n 3 n n
n 5
1

3 is seperated from 1 by 1 empty node.. 2 is seperated from 1 by 2 empty nodes.. 4 is a child of 3.

or let's say that if it has only 1 non-null child, it pulls that up.. if it has 2, it pulls up the smaller one.. construct the tree with 1 3 2 5 4
under the same scenario, you'll get
n n n n n n n n
3 5 n n
2 4
1

mm.. is that what u intended on?

These sorts of scenarios are easily handled by something like a red-black tree (which prevents it from growing unbalanced at the cost of a little extra overhead, but maintains the same asymptotic complexity). It's a pretty basic data structures problem.

 

[mrgq912]

I would love to work at Google. It just seems like a place with intelligent/creative people, all working in relaxed environment, with amazing benifits, and having fun at the same time.

You think they would employ some one with a

BS in Molecular Biology and Biochemistry
MS in Biomedical Sciences
and a MD

 

[itachi]

Originally posted by: Matthias99
These sorts of scenarios are easily handled by something like a red-black tree (which prevents it from growing unbalanced at the cost of a little extra overhead, but maintains the same asymptotic complexity). It's a pretty basic data structures problem.

yea.. that's the direction that i was trying to go in. his solution lacked an ordering property.

 

[ones3k]

Originally posted by: itachi
err nm.. i was wrong about the sorted being O(K), but it still seems like it'd cause problems.

construct your tree with 1 2 3 4 5 as keys
if you 'push' each key down as you construct it without any reordering or reattaching (assuming you pair from left to right), the tree that results is
n 2 n 4 n n n n
n 3 n n
n 5
1

3 is seperated from 1 by 1 empty node.. 2 is seperated from 1 by 2 empty nodes.. 4 is a child of 3.

or let's say that if it has only 1 non-null child, it pulls that up.. if it has 2, it pulls up the smaller one.. construct the tree with 1 3 2 5 4
under the same scenario, you'll get
n n n n n n n n
3 5 n n
2 4
1

mm.. is that what u intended on?

I havre absolutely no idea about your notation. What do you mean by a "key" ?

Look, the solution is simple. You start with K nodes (the leaves). Each node has an integer. Then you construct a Tournament tree by selecting the winner between pairs of nodes. If you notice, this procedure results in a tree of Depth O(k)

Now that we have a tree with depth O(K) we do NOT need to change the tree structure. The tree is static at this point. S T A T I C

What we do (and what i said in my initial post) is we select the winner of the tournament (which is the min out of all the streams, and this also the ROOT node) Now we go back to the leaf node corresponding to our winner and replace the value with the the next stream value. In other words, we INCREMENT the stream. Now we update the tourament tree by going along the path directly to the root. There is absolutely NO reason to use any type of balancing sscheme, and you have misunderstood my solution. I told you to draw this out, you'll realize whats going on.

The tree is STATIC

 

[The Boston Dangler]

These are the kind of questions you're entitled to ask when your stocks are heading towards $500 per share.

 

[itachi]

Originally posted by: ones3k
I havre absolutely no idea about your notation. What do you mean by a "key" ?

the key is what you search/compare by. the values of the streams or a string in a tree of strings.

What we do (and what i said in my initial post) is we select the winner of the tournament (which is the min out of all the streams, and this also the ROOT node) Now we go back to the leaf node corresponding to our winner and replace the value with the the next stream value. In other words, we INCREMENT the stream. Now we update the tourament tree by going along the path directly to the root. There is absolutely NO reason to use any type of balancing sscheme, and you have misunderstood my solution. I told you to draw this out, you'll realize whats going on.

The tree is STATIC

yea, you should really specify that the tree is filled as it goes along. from what you said, i assumed you filled the tree before u started reading.

 

[statik213]

Originally posted by: ones3k
I'll post the solution to #1 so you believe me:

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

there's a standard ADT called a heap AKA priority queue. The recursive definition of a heap is that the value of the root node in a subtree is smaller than every node below it in the sub-tree...
so you form a heap with all the streams keyed by the 'top' value, so you print out the root value in O(1) and upating the heap with the new root value takes O(lok n) time.

 

[ones3k]

Search "google interview questions" on google, this post is on the first page! WOOT

 

[ones3k]

http://forums.anandtech.com/messageview...&STARTPAGE=3&FTVAR_FORUMVIEWTMP=Linear

 

[Calin]

Originally posted by: hypn0tik
I can do 5 and 6 and pretty sure can do 4. The others look pretty difficult.

Edit: Actually, I can't do 4. I underestimated the problem.

Just number represented in base 26 (in base two you have 0 and 1, in base 10 you have 0, 1, ..., 9, A, ..., F). In that base 26 you have 0, a, b, ..., z.
Not really so hard, a means 1, then z means 26 (probably), aa means 27 (26 * 1 + 1) and so on. You should add a 0 to the numbering system to ease working

 

[BlueFlamme]

Just be glad they didn't slip in any NP-complete problems :evil:


The rest of the problems were readily covered in my one graduate level algorithms course, though I would have to study up to do it on the fly (I promptly forgot it when I got a network engineering job).

 

[sdifox]

Ah, NP and P. I have to say that is the course (computability and complexity) that I remember the most.