Comment by drfuchs

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).