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

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

 

[w33bo]

Originally posted by: EKKC

Originally posted by: ronin2kr6
Ironic if someone could have googled the answers before hand

maybe they allow you a laptop or pda to the interview so you can google the answers!!!

chuckle

 

[ones3k]

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]

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]

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

 

[TallBill]

Originally posted by: ones3k
TallBill, do you work at burger king? Google doesnt pay that well actually.

Im an military policeman.

 

[FreshPrince]

sometimes I wonder if companies would interview applicants with questions they themselves are trying to solve?

 

[Minjin]

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]

#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]

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]

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]

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]

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

 

[ones3k]

bump

 

[ones3k]

i edited my post with new questions

 

[Mickey Eye]

Old Google Aptitude test

Solutions to the mathematical parts.

 

[Aharami]

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

 

[loic2003]

Yeah, here are the actual papers. Not the same question IIRC, but just as nightmarish!:

one
Two
Three
Four.


Enjoy!

 

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

 

[KoolDrew]

Originally posted by: FrustratedUser
Whooops! I failed miserably.

 

[loic2003]

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.

 

[halik]

I have to say that I have absolutely no desire to work for google

 

[RagingBITCH]

dorks.

 

[fbrdphreak]

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

 

well...at least you got more interview experience!