So, I had my screening interview with the recruiter from Google yesterday. And that went well, we just kind of BS'd for a few minutes. Then we set up a technical interview over the phone for today. I'm going to give a rundown of what today's interview was like, in case anyone cares.
First Question:
Write a function (in whatever language you want) to find the next prime number after a given number. I decided to do mine in C.
So, the function declaration was something like: int nextPrime(int num);
If you want to, you should write the function, and I'll tell you how you do. This question was actually pretty cool, because I learned quite a bit in it. My interviewer (Mark) was very familiar with C, and taught me a few thing. I came up with a decent solution, then we talked about it... and made it better.
Then we talked a little bit about the representation of doubles in memory, and, if they can misrepresent an int.
Second Question:
If I gave you K sorted arrays, each of size N, how would you put them into one big array, and what would the big-O of the procedure be?
The first solution I came up with was to use a minheap.
Then we talked about what if the arrays were so big, that only 2 of them could fit in memory at one time (there is 2N available in memory). My first solution worked for this, but would have been slow b/c of harddrive accesses. So, I came up with another solution that merged 2 of them together. then merge the next 2 together...
The big-O of both of the solutions was O(KN log K). But, the second was better, because it had less disk accesses.
BSing
I asked him about his job. He loves it. Everyone there loves it. Its the best place on earth to work. He said I did pretty well in the interview. We'll see how it goes.
Funny Sidenote:
Sometime during the interview, my cell phone rang twice. Both times, it was WSU Career Services trying to reach me. They called to set Deloitte up to interview me. This would be a decent job, because I think they pay extremely well. And, I want to get a higher pay job than my roommate, because he thinks Electrical Engineering is a more valuable degree. I guess Dan and I are just competitive :)
Thanks for playing.
Thursday, October 21, 2004
Subscribe to:
Post Comments (Atom)
14 comments:
I blew my Amazon.com technical interview, I spent about 30 minutes in trying to explain what a hash table was, unfortunally I didn't get to the second lines of interviews. And for Bain, I should've done better on preparing for case study interviews.
So the run down
Me vs. Companys
0 v 1 Harris
0 v 1 Bain
0 v 1 Amazon
0 v 1 Bank of America
? v ? Computer Science Corporation
Well good luck with Google and Deloitte
-Ron
hrm... stupid IE, and double posting
Thanks Ron!
I'll keep this up-to-date with any info. Good luck with your interviews.
At least you got an interview with Amazon, they never got back to me. Bastards.
I hope you're having fun at school.
isn't the complexity for your minheap algorithm O (KN Log KN) since each insertion to the binary heap worst case is O (log KN)?
I haven't thought about this in awhile... but I think KN Log K is right. In the min-heap, you don't need to have every element, just the first element off of every array... which is K items. So, the size of the minheap is only K items.
The reason I think you need to put all the elements in the array is because
A: 2 4 5
B: 1 1 1
C: 3 6 7
First run: Min heap = 1 2 3.
RemoveMin: Min heap = 2 3
You can not do RemoveMin to get the smallest element in the heap anymore. 2 is not the smallest. B still hold the smallest element.
Second Run: Min heap = 1 2 3 4 6
RemoveMin: Min Heap = 2 3 4 6
Third Run: Min Heap = 1 2 3 4 5 6 7
So do deal with the worse case, you need all the elements to be in the Min Heap. Am I missing something?
I see what you mean. How about... everytime you pull off an element from the MinHeap, you put a new one in. And the new one that you put in is off of the array that the most recently sorted number was from.
Initial: Min heap = 1 2 3.
A: 4 5
B: 1 1
C: 6 7
RemoveMin(): Min heap = 2 3
A: 4 5
B: 1 1
C: 6 7
Add(1): Min heap = 1 2 3
A: 4 5
B: 1
C: 6 7
RemoveMin(): Min heap = 2 3
etc...
So, you're going to "re-heapify" into a MinHeap with k elements kn times... so O(KN log K)
Does that sound right? I haven't done anything like this in real life for a long time. I haven't even had a discussion about something like this since college... this is REALLY fun. I miss computer science :-(
"Everytime you pull off an element from the MinHeap, you put a new one in."
You can't do this in constant time. You got to go through and look for the smallest element. The complexity of this in O(K). Basically, You need to have all the elements in the Heap so that you don't keep rescanning the Arrays. You were close getting that job with Google. Maybe it's time for you to try again. :)
Hmm... you're right.
it'd be KN(K * log K)... which would be O(K^2 * N).
If space weren't an issue (what? it could happen), you could keep track of heap elements origin. i.e.
Initial: Min heap = 1(b) 2(a) 3(c)
A: 4 5
B: 1 1
C: 6 7
RemoveMin(): Min heap = 2(a) 3(c)
A: 4 5
B: 1 1
C: 6 7
Add(1(b)): Min heap = 1(b) 2(a) 3(c)
A: 4 5
B: 1
C: 6 7
etc...
Now you can skip the step of scanning the arrays.
I'm not sure how practical that is though. If you're payload is an int and your origin information is a pointer, the size in memory of the heap has just doubled. If your payload is something larger (like a string or something), then the pointer to the array is negligible.
It seems like maybe there could be a better way. I need more time, and a pen and paper though :-)
Here is another case
A: 1 1 1
B: 6 6 6
C: 4 4 4
worse case, you still need to scan :)
If you have the smallest element from every array in the minheap, you will always end up with a sorted array.
If you remove an element from the minheap that originated from A, and replace with the element from the front of A... you'll always have the smallest item from each array in the minheap.
No scanning involved as long as you track the element's origination array.
right? Send me an email... so you can tell me I'm an idiot out of the public view :-)
I think you redeemed your reputation. You're right and I'm wrong. I read too quickly. Good job!
You brought up very good points though. And the fact that we have to track where every element came from... makes my solution kind of hokey (although, it is O(KN Log K)).
Post a Comment