Google is legendary for their brain-teaser technical interviews that weed out anybody who is less than Mensa. Mine went extremely poorly. I don't think they're going to be calling me back. But it's too bad, because it wasn't my fault.
First of all I don't understand the logic in having a phone interview between Australia and Mountain View California USA. I guess nobody in Sydney is qualified to ask technical questions. Oh well.
But here's the first question:
Given several points in 2-d space, construct a line between them.
OK, this isn't hard, but first I have to know the goal of the line. So I ask her. What's the goal of this line? And is there a vector or direction preference?
She answers - what do you mean a 'goal'? She sounds annoyed. It's just a line. How do you construct it?
So I start probing. OK, well you can just connect the dots. I doubt that's what you're after; but at least I may be able to further ascertain the goal you have in mind. She rejects connect the dots outright - even though it satisfies the problem criteria; and without providing any more input.
So I have to answer that I cannot solve this problem. I don't have enough information. She then goes on and says OK, forget it. Now instead of points you've got lines. Same question. Construct a line between them.
I've still got the same problem. There isn't enough information. I cannot answer it. I start by finding the midpoint of the lines, maybe we should draw through them all? BZZZZT! Wrong answer. She starts to question how you would find out if two lines overlap. So clearly she has another goal in mind, but for the dickens I can't tease it out of her. It starts to look like she had a scatter plot in mind. You know - you've got a bunch of random data points, find the mean. But even here, you need a further goal. Are you going against the x or the y axis? It's still unsolvable. I'm starting to show my exhasperation - so is she.
But there's no place for me to go. No way out. Let's imagine some possibilities. Connect the dots in the Y direction. Find the mean in the Y direction. Solve for x instead. What if the points describe the circumference of a circle? Am I to draw the circle, draw a line through it, or draw something looking like the AT&T logo on these points? All of these solve the first problem. When you turn it into lines, am I finding the mean, or constructing segments? What if I've got multiple sets of parallel lines that look like the I Ching? What kind of line am I expected to draw?
But she cannot even envision these possibilities. She's looking for some simple answer to a problem that she hasn't been able to convey - and so I am unable to answer it.
Let's move on. Question two. You've got an array of integers. Sort them, in 1/n time or better. We know the min and max.
Maybe this can be done - but I'm just not seeing it. I tell her so. I also spend a few moments looking at possible ways to do it, but they all lead to dead ends. She stresses again, we know the min and max, as though to say that this is an important fact to consider. Well yeah, but it doesn't help. Best you can do is 2(1/n). But she's given up on me and the phone call is coming to an end. I am guessing she was looking for something like - construct an array with (max-min) elements. go through your original array and drop each element into its index in the second array. You're done.
But you're not. What if you've got holes in the destination array? You've got to make a second pass and prune all the holes. Or you sort into a linked list in the first place, which means that min and max aren't helping you; and this takes log time so it doesn't fit the solution set. I then turn my brain into a CPU and drop into assembly language. Let's see, take the first number and stick it into a register... load the next, branch if greater... I'm visualizing how to solve this the best way.
She's almost scolding me by now. What's a register? What does that have to do with the problem? I don't have time to explain the inner workings of a microprocessor and it wouldn't help anyway - our conversation was finished. Too bad, I thought I was getting somewhere with the assembler sort; but totally lost the train of thought when she asked me what the hell I was doing.
So anyway - for any of you thinking of joining Google, best of luck. It doesn't matter if you're clever. What would probably help is if you get an interviewer that has actually had to solve real world problems rather than theoretical questions from a cheat sheet. Or - if you're clairvoyant.