Job update for the day.
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.
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.
13 Comments
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?
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 :-(
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. :)
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 :-)
A: 1 1 1
B: 6 6 6
C: 4 4 4
worse case, you still need to scan :)
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 :-)
Comments are closed. This is an archived blog.