A recruiter contacted me. I expresed to him that I was open to a good opportunity though I was rather satisfied with my current compensation and was happy with the project I was working on.
A recruiter submitted my resume. I was asked to fill out a self-evaluation questionaire about C++, linux/Windows, boost, etc.
On the first part of the phone interview, standard programming questions were asked: difference between hashmap and binary tree, UDP vs TCP, OOP, polymorphism, etc.
On the second part of the interview, two programming questions were asked.
1) When given a stream of chars, find a frequency of each character.
I gave a standard O(NLogN) solution using a binary tree. The interviewer was satisfied.
Then, a little variation of the question was asked, when given a stream of doubles with a precision of 0.001, find a freqency of each double number. I gave an O(N) solution. You cannot beat O(N). :)
2) When given K sorted collections with each collection having N elements, create a merged sorted collection.
First, I gave a straight-forward no brainer O(KLogK*K*N) solution: KLogK for sorting K first elements and K*N total elements.
Obviously, he was not satisfied, tried to give me hints and asked me to think about efficient sorting algorithms.
While he was giving me his own clues, my mind was groping for my own solutions. Then, I found a solution that gives O(logK*K*N) solution. In my solution, sorting is done only once.
a) Pick the first element from each K collection and sort them.
b) Then pick the smallest from the collection and insert it into the output.
c) Then, pick the next element from the collection from which the smallest value element is from. And, insert it to the sorted collection of K elements.
d) Go back to b) and repeat .
I was explaining my algorithm, described a), b) ,c) steps, and said an efficent sorting algorithm effect is neglible since sorting is done only once in step a)(the one time sorting is especially neglible when N>>K, the likely scenario). But, he seemed to have his own solution in mind and cut me off saying that I will need to do sorting many times and was dismissive of my approach.
I was tempted to go ahead and finish explaining my solution, but I stopped because I didn't want to push/argue in a phone interview and the interviewer didn't impress me. I decided that the opportunity was not worth my efforts.
