I agree that it isn't the sole reason why I didn't get the job. If I did great on the other 5 interviews, then my O(n log n) solution probably would have been f

I agree that it isn't the sole reason why I didn't get the job. If I did great on the other 5 interviews, then my O(n log n) solution probably would have been fine. However, not getting the optimal solution didn't help.