I first asked whether there was any constraint on k (the maximum distance of an element from its sorted position), but the interviewer said there wasn’t. I initially suggested Quick Sort, after which he asked if it could be done in O(n) time. Since that isn’t possible without additional constraints(max is O n log k), we moved on to system design questions and a discussion about my projects. I answered almost all the questions except one or two.