4 ms·
The interviewer for candidate 1 isn't very technically proficient. In the "if the array was too big to fit in memory" case (where "disk" is explicitly mentioned
by drfuchs 9y ago
The interviewer for candidate 1 isn't very technically proficient. In the "if the array was too big to fit in memory" case (where "disk" is explicitly mentioned), the proposed solution starts by moving the disk head from track 1 to track N, then back to track 2, then track N-1, 3, N-2, etc., oscillating until it stops at track N/2. That takes a grand total of O(N^2) seek time. The correct solution is to do one sequential pass over the file to count the a's and b's, and then a second pass to write the proper number of a's followed by b's, which takes O(N) total head-movement time (which dominates everything else).
- pradeep_m 9y agoI think the code is written for the case where it fits in memory. For that case, the solution is O(n) in terms of time complexity. From the feedback it seems that they only spoke about the solution where the data doesn't fit in memory.
- drfuchs 9y ago"To test further, I asked her how she will approach the problem if the array was too big to fit in memory ... She then worked on adapting her original code to work with left and right batches, swapping ... back to disk." (Emphasis mine.)
- TrainedMonkey 9y agoThe problem statement did not mention anything about optimizing the real world throughput of the algorithm. For the things you are talking about to matter there would need to be a far more complete problem specification.