Tuesday, February 13, 2007

No hope for this google interview

Just done with the google interview. I believe this this the worst case I've ever done.
It's so bad. The interviewee is a Chinese, but we still talk in English.

First question ask me to write a SQL query. I haven't touch database for a long time. So after 10 mins, I still can't come up with a good answer.

Second question: how to implement a merge sort? write the pseudo code. Then, I ask him whether or not I can use recursion. He questioned: without recursion, how do you do that? (Stupid, why not just give the answer with recursion). What's the time complexity and space complexity. I know time complexity is O(nlgn) but space complexity is not sure. I finally figure out the correct solution should be O(n). I guess he already kicked me out of his candidate list based on my performance.

3rd question: 10G large array data, 2G RAM, how do you sort them? I know this question should be merge sort? But how many data should you load each time into the memory?
I answered you can split an array of size n into 2 parts, 3 parts or even more, and then do a combination. So for 2 parts, you need a working memory of (n/2), 3 parts, you need a working memory of (n/3). but what should be the optimal number? No idea.

Too nervous, cannot think any more. And he mentioned we were out of time several times.

4. it's about the project. How to solve their problem.

He asked me if I have any questions, but I already gave up. So just ask him some normal questions.

Really need to know the algorithm and structure book well. But too busy to prepare the interview. Really shame on myself.

No comments: