I think you guys might be talking past each other a bit. A good candidate should be able to O(n log n) time pretty easily, but getting O(n) off the bat would

I think you guys might be talking past each other a bit. A good candidate should be able to O(n log n) time pretty easily, but getting O(n) off the bat would suggest prior knowledge of the problem.