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

Page 5 - Seeking answers? Join the AnandTech community: where nearly half-a-million members share solutions and discuss the latest tech.

mugs

Lifer
Apr 29, 2003
48,920
46
91
Originally posted by: TuxDave
Originally posted by: mugs
Originally posted by: ones3k
=========================================================
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

This is a basic algorithm I came up with, in English.

Start by ordering the k streams by the value of their first item. Pick the first item off the first stream (because you know it's the smallest). Compare the new first item in the first stream to the second. If the item in the first stream is bigger than the item in the second stream, iterate through the streams until you find the first stream's new correct spot, and move it there. Pick the first item off the new first stream. Repeat.

I kinda had the same idea. Sort the k streams by the first element. Take one off the top stream and look at the next element. I know that when you move this stream down to the correct sorted location every first element of the stream it passes goes directly into the final stream without needing to look at it. I just can't figure out the last optimization.

I'm not sure if I'm understanding you correctly... are you saying that as you move the "old" first stream down to its correct position, you'd take the first element off each stream it passes and put it directly into your result stream? That's not necessarily true.

Take this example:

Stream 1 = 1, 15, 16, 17
Stream 2 = 2, 3, 4, 5, 8, 10
Stream 3 = 6, 9, 11
Stream 4 = 16, 20, 60

After you pop the 1 off stream 1, it goes down between streams 3 and 4, but if you take the 2 off stream 2 and the 6 off stream 3, you've put the 6 before the 3, 4 and 5 of stream 2.

If that's not what you were saying, disregard. :)
 

ones3k

Banned
Aug 21, 2005
444
0
0
Originally posted by: mugs
Originally posted by: TuxDave
Originally posted by: mugs
Originally posted by: ones3k
=========================================================
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

This is a basic algorithm I came up with, in English.

Start by ordering the k streams by the value of their first item. Pick the first item off the first stream (because you know it's the smallest). Compare the new first item in the first stream to the second. If the item in the first stream is bigger than the item in the second stream, iterate through the streams until you find the first stream's new correct spot, and move it there. Pick the first item off the new first stream. Repeat.

I kinda had the same idea. Sort the k streams by the first element. Take one off the top stream and look at the next element. I know that when you move this stream down to the correct sorted location every first element of the stream it passes goes directly into the final stream without needing to look at it. I just can't figure out the last optimization.

I'm not sure if I'm understanding you correctly... are you saying that as you move the "old" first stream down to its correct position, you'd take the first element off each stream it passes and put it directly into your result stream? That's not necessarily true.

Take this example:

Stream 1 = 1, 15, 16, 17
Stream 2 = 2, 3, 4, 5, 8, 10
Stream 3 = 6, 9, 11
Stream 4 = 16, 20, 60

After you pop the 1 off stream 1, it goes down between streams 3 and 4, but if you take the 2 off stream 2 and the 6 off stream 3, you've put the 6 before the 3, 4 and 5 of stream 2.

If that's not what you were saying, disregard. :)


try drawing a upsidedown tree where all the nodes represent the streams.
 

kyparrish

Diamond Member
Nov 6, 2003
5,935
1
0
Hmm, doesn't sound like a job where you can just BS around the water cooler, laughing at your superior's dumb jokes to get by.
 

mugs

Lifer
Apr 29, 2003
48,920
46
91
Originally posted by: ones3k

try drawing a upsidedown tree where all the nodes represent the streams.

Yeah, that didn't help at all. ;) That would look like... a funnel, and my first inclination would be to just iterate through and pop off the lowest one on each iteration, but that's a pretty inefficient algorithm
 

FreshPrince

Diamond Member
Dec 6, 2001
8,361
1
0
sometimes I wonder if companies would interview applicants with questions they themselves are trying to solve?
 

Minjin

Platinum Member
Jan 18, 2003
2,208
1
81
Originally posted by: ones3k
Even if you were the second coming of Einstein, you'd have no chance unless you had a degree from either MIT or CMU.

Says the fox about the grapes... ;)

Mark
 

statik213

Golden Member
Oct 31, 2004
1,654
0
0
#1)
Since all the streams are sorted the (next) smallest value is always at the top of one of the streams. Just keep picking the smallest value over and over again. here's some pseudocode:

While(Streams.size() > 0)

Stream streamWithSmallestElem = Streams[0]
For j = 1 to Streams.size()
If(streamWithSmallestElem.peek() < streams[j].peek())
streamWithSmallestElem = streams[j]
End If
End
outStream.put(streamWithSmallestElem.pop())
if(streamWithSmallestElem.remaingElements() == 0)
Streams.remove(streamWithSmallestElem)
End if
End
 

hypn0tik

Diamond Member
Jul 5, 2005
5,866
2
0
Originally posted by: ones3k
post solutions for everyone to see


Solution for 6 as requested.

Consider a square with it's corners at (1/2, 1/2), (1/2, -1/2) (-1/2, -1/2) and (-1/2, 1/2)

Now, we only need to consider the first quadrant, and we can find the others using symmetry (i.e. reflecting about the axes and origin).

Now, any point can be represented as (x,y) and it's distance from the centre is sqrt (x^2 + y^2).

From that point, the distance to the egde is min (1/2 - x, 1/2 - y).

If you draw a diagonal from the centre of the square to it's vertex in the first quadrant, you'll have split it along the line y = x. Above that line, y > x and below it, x > y.

Now, consider the part above. Clearly, 1/2 - y will be smaller than 1/2 - x since y is bigger. Now, we only need to worry about the boundary condition.

-> 1/2 - y = sqrt (x^2 + y^2)
1/4 - y + y^2 = x^2 + y^2
--> y = 1/4 - x^2
Which is a parabola.

Considering the bottom half, we get a similar result of:
x = 1/4 - y^2, again a parabola.

Draw these 2 out in the first quadrant and then reflect them along the axes and the origin and you have your locus. This sort of looks like a flower, with a little stretch of your imagination.
 

TuxDave

Lifer
Oct 8, 2002
10,571
3
71
Originally posted by: mugs
Originally posted by: TuxDave
Originally posted by: mugs
Originally posted by: ones3k
=========================================================
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

This is a basic algorithm I came up with, in English.

Start by ordering the k streams by the value of their first item. Pick the first item off the first stream (because you know it's the smallest). Compare the new first item in the first stream to the second. If the item in the first stream is bigger than the item in the second stream, iterate through the streams until you find the first stream's new correct spot, and move it there. Pick the first item off the new first stream. Repeat.

I kinda had the same idea. Sort the k streams by the first element. Take one off the top stream and look at the next element. I know that when you move this stream down to the correct sorted location every first element of the stream it passes goes directly into the final stream without needing to look at it. I just can't figure out the last optimization.

I'm not sure if I'm understanding you correctly... are you saying that as you move the "old" first stream down to its correct position, you'd take the first element off each stream it passes and put it directly into your result stream? That's not necessarily true.

Take this example:

Stream 1 = 1, 15, 16, 17
Stream 2 = 2, 3, 4, 5, 8, 10
Stream 3 = 6, 9, 11
Stream 4 = 16, 20, 60

After you pop the 1 off stream 1, it goes down between streams 3 and 4, but if you take the 2 off stream 2 and the 6 off stream 3, you've put the 6 before the 3, 4 and 5 of stream 2.

If that's not what you were saying, disregard. :)

QED. You are correct.
 

5150Joker

Diamond Member
Feb 6, 2002
5,549
0
71
www.techinferno.com
Well those questions were alll greek to me. They could've given me a year to answer them and the paper would still be blank. I'd rather become a nurse or something.
 

KEV1N

Platinum Member
Jan 15, 2000
2,932
1
0
Those questions are pretty difficult for me. I received my BS in Computer Science in 2003. They seem more like midterm questions, which is not what I'd expect at a job interview. In my opinion, your score on something like this has little relevance to your performance at work... or maybe I'm just bitter :)
 

Aharami

Lifer
Aug 31, 2001
21,205
165
106
Originally posted by: hypn0tik
Originally posted by: ones3k
post solutions for everyone to see


Solution for 6 as requested.

Consider a square with it's corners at (1/2, 1/2), (1/2, -1/2) (-1/2, -1/2) and (-1/2, 1/2)

Now, we only need to consider the first quadrant, and we can find the others using symmetry (i.e. reflecting about the axes and origin).

Now, any point can be represented as (x,y) and it's distance from the centre is sqrt (x^2 + y^2).

From that point, the distance to the egde is min (1/2 - x, 1/2 - y).

If you draw a diagonal from the centre of the square to it's vertex in the first quadrant, you'll have split it along the line y = x. Above that line, y > x and below it, x > y.

Now, consider the part above. Clearly, 1/2 - y will be smaller than 1/2 - x since y is bigger. Now, we only need to worry about the boundary condition.

-> 1/2 - y = sqrt (x^2 + y^2)
1/4 - y + y^2 = x^2 + y^2
--> y = 1/4 - x^2
Which is a parabola.

Considering the bottom half, we get a similar result of:
x = 1/4 - y^2, again a parabola.

Draw these 2 out in the first quadrant and then reflect them along the axes and the origin and you have your locus. This sort of looks like a flower, with a little stretch of your imagination.

good stuff.
i like this thread
 

Mickey Eye

Senior member
Apr 14, 2005
763
0
76
Originally posted by: loic2003
Yeah, here are the actual papers. Not the same question IIRC, but just as nightmarish!:

one
Two
Three
Four.


Enjoy!

Same as what I posted only mine was a bigger image. Did you actually do the test or was it something you found online. Having now seen the answers I know that I am truelly not destined for greatness.
 

loic2003

Diamond Member
Sep 14, 2003
3,844
0
0
Originally posted by: Mickey Eye
Originally posted by: loic2003
Yeah, here are the actual papers. Not the same question IIRC, but just as nightmarish!:

one
Two
Three
Four.


Enjoy!

Same as what I posted only mine was a bigger image. Did you actually do the test or was it something you found online. Having now seen the answers I know that I am truelly not destined for greatness.


Found online. I really don't have the best head for heavy maths despite having a degree in AI. I have a close friend who's going for a job at google in maybe 10 months time, and I have a feeling he'll get it.
 

fbrdphreak

Lifer
Apr 17, 2004
17,555
1
0
Originally posted by: shilala
If they asked me those questions I'd have to give them a dazed look and a spin-kick to the head.
Then I'd ask if I could have the office by the bathroom.
Seriously.

I actually know some of the terminology in those questions 'cuz in Comp Engineering they make us take some programming (i'm in data structures now, *shudder*), but gawddamn I don't understand that ****** and I don't care for it.

Have fun playing with all those numbers and billions of lines of code ;)