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 sequen…
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.
"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.)