Top 7 Sorting Interview Questions
Browse 7 real-world technical and behavioral interview questions about Sorting. Review scenarios, edge cases, and architectural best practices.
Shipping packages within D days minimises a maximum. Now place m sensors at fixed positions so the closest pair is as far apart as possible. What changes in the binary search?
It is still binary search on the answer, over the gap rather than the positions, but the predicate flips. A gap that works means every smaller gap works, so you want the last feasible value, which needs lo = mid with a ceiling midpoint. Sort first, check each gap greedily, and the cost is O(n log n + n log R).
Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?
Russian doll envelopes reduce to a longest increasing subsequence. Sort by width ascending, break width ties by height descending, then run the O(n log n) tails search on heights. The descending tie-break stops equal widths from chaining, since a strictly increasing run then takes at most one per width.
Sorting a list throws IllegalArgumentException saying the comparison method violates its general contract. What did the comparator get wrong?
The sort detected that your comparator contradicted itself partway through a merge. The usual causes are a subtraction that overflows, an ordering that is not transitive, and a sort key that changes while the sort is running. Use this collections answer to show the decision, trade-off, and evidence rather than a memorised definition. It also connects sorting to the point an interviewer is testing.
Merge a list of overlapping intervals, and justify the key you sorted by
Sorting by start time is what reduces the merge to a single scan carrying one scalar, the end of the open block; sorting by end breaks it, and sorting by end is instead correct for maximum non-overlapping selection. Both run in O(n log n), and equal timestamps decide the answer.
Given a list of meetings with start and end times, tell me the minimum number of rooms needed to hold all of them.
The answer is the maximum number of meetings running at once, found by sweeping the start and end times in sorted order and tracking a running count. The starts and ends can be sorted independently of each other, and a meeting ending exactly when another begins must free its room or you will overcount.
Given a list of meetings with start and end times, pick the largest set of them that do not overlap.
Sort by finishing time and take every meeting that starts no earlier than the last one you took. Earliest start and shortest duration both look reasonable and both give provably smaller answers, and the exchange argument for earliest finish is what the question is really asking for.
Return every distinct triplet in the array that sums to zero.
Sort the array, fix each element as an anchor, then converge two pointers inwards from both ends of the remaining range. The sort is asymptotically free against the O of n squared scan, and it is what lets you skip duplicate values positionally instead of deduplicating a set of results afterwards. It also connects sorting to the point an interviewer is testing.