Java Searching and sorting
The algorithms you will not implement at work but will be asked to reason about, plus the sorting API you use daily.
3 concepts · 9 interview questions
What this topic covers
Every concept in searching and sorting, and the questions each one gets asked as. Where a question links, it has a full write-up.
Binary search
Halving a sorted range. Easy to describe and famously easy to get wrong at the boundaries.
- Implement binary search, and say where the off-by-one lives.
- Find the first element greater than a target.
- How do you binary search on an answer rather than an array?
Sorting algorithms and the JDK's
Comparison sorts cost n log n. What Java actually runs depends on whether the elements are primitives or objects, and that choice is about stability.
- Which sort does Arrays.sort use, and why does it depend on the type?
- What does a stable sort guarantee, and when do you need it?
- Quick sort or merge sort?
Ordering with comparators
A comparator defines a total order, and the sort contract requires it to be consistent. An inconsistent one can throw at runtime.
- Comparable or Comparator?
- How do you sort by two fields, one descending?
- Why does sorting sometimes throw about a general contract violation?