Re:Show HN: Anonymous interview evals of strong software/ML ...
by drfuchs on Monday July 31, 2017 @06:24PM
(#14896413)
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).
[ Parent
| on HN ]
Re:Show HN: Anonymous interview evals of strong software/ML ...
by pradeep_m on Monday July 31, 2017 @06:52PM
(#14896561)
I 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.
Re:Show HN: Anonymous interview evals of strong software/ML ...
by drfuchs on Monday July 31, 2017 @07:22PM
(#14896725)
"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.)
Re:Show HN: Anonymous interview evals of strong software/ML ...
by TrainedMonkey on Monday July 31, 2017 @06:54PM
(#14896572)
The 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.