Coding

Binary Search & Sorting Questions

Q: How do I know which binary search template to use?

Template 1 (left<=right, return mid): when element is guaranteed to exist. Template 2 (left<right, right=mid, return left): 'find first true' or minimum satisfying a condition. Template 3 (left+1<right, post-loop check): when you need both neighbors. Template 2 is the most versatile for real interview problems.

Q: What is binary search on the answer space?

Instead of searching for a value in an array, binary search over all possible answers. Ask: 'Is answer X feasible?' If the feasibility check is monotone (false for small X, true for large X or vice versa), binary search finds the minimum X in O(log(range) × check time). Classic: Koko Eating Bananas, Minimum Days to Make Bouquets, Ship Packages.

Q: When does greedy work for interval scheduling?

Greedy works when: sorting by end time and always taking the interval that ends soonest (for maximizing non-overlapping intervals). It fails when you need to consider weights/values — then use DP. Greedy correctness usually proven by exchange argument: any optimal solution can be transformed to the greedy solution without getting worse.

Q: What sorting algorithms should I know for interviews?

Know conceptually: Merge Sort (O(n log n), stable, good for linked lists), Quick Sort (O(n log n) average, O(n²) worst, in-place), Heap Sort (O(n log n), in-place, not stable), Counting/Radix Sort (O(n) for small integer ranges). In practice: languages provide optimized built-in sort (typically Timsort). Interviewers care that you know trade-offs.

Binary search and sorting appear in problems far beyond simple search. Learn to apply binary search on the answer space and master sorting-based greedy problems.

Practice with AI Feedback — Free AI Mock Interview

Sample Questions & Strong Answers

Binary Search — find a target in a sorted array.

Standard: left=0, right=n−1. While left<=right: mid=(left+right)>>1. If nums[mid]===target return mid. If nums[mid]<target: left=mid+1, else right=mid−1. Return −1. Time O(log n), Space O(1).

💡

Pro tip: Use (left+right)>>1 instead of (left+right)/2 to avoid integer overflow. Know both inclusive and exclusive boundary variants.

First Bad Version — find first bad version with minimal API calls.

Binary search: if isBadVersion(mid) is true, answer could be mid or earlier → right=mid. If false, answer is after mid → left=mid+1. Return left when converged. Time O(log n), Space O(1).

💡

Pro tip: Use left < right (not <=) and set right=mid (not mid−1) to avoid infinite loop. Meta, Amazon — template for 'find first true' binary search.

Kth Largest Element in Array — without full sorting.

QuickSelect: partition array around a pivot. If pivot index is n−k, found it. If index < n−k, search right. If index > n−k, search left. Average O(n), worst O(n²). Alternatively, use a min-heap of size k: O(n log k).

💡

Pro tip: QuickSelect is optimal average-case and expected in top-company interviews. Min-heap is O(n log k) and more predictable. Amazon, Meta, Google.

Merge Intervals — merge all overlapping intervals.

Sort by start time. Iterate: if current interval overlaps last merged (current.start <= last.end), merge by updating last.end = max(last.end, current.end). Otherwise, append current. Time O(n log n), Space O(n).

💡

Pro tip: Sort first — this problem cannot be solved efficiently without sorting. Update end with max(), not just current.end. Amazon, Google, Meta, Microsoft.

Meeting Rooms II — minimum conference rooms required.

Separate start and end times, sort both. Two-pointer sweep: if next start < earliest end, need new room (rooms++). Else, free a room (end pointer++). Always advance start pointer. Time O(n log n), Space O(n).

💡

Pro tip: The two-sorted-arrays sweep is elegant and O(n log n). Min-heap on end times also works. Amazon, Meta, Google — medium.

Find Peak Element — find any peak (greater than its neighbors).

Binary search: if nums[mid] < nums[mid+1], peak is in right half (left=mid+1). Else, peak is in left half including mid (right=mid). Return left when converged. Time O(log n), Space O(1).

💡

Pro tip: Peaks are guaranteed to exist (treat out-of-bounds as −∞). Move toward the higher neighbor — peak must exist in that direction. Google, Microsoft.

Search a 2D Matrix — search a value where each row and column is sorted.

Treat the matrix as a flattened sorted array. mid index → row = mid/cols, col = mid%cols. Standard binary search. Time O(log(m×n)), Space O(1). For the 'partially sorted' variant: start top-right, move left if too large, down if too small.

💡

Pro tip: Know both variants: fully sorted (binary search) and rows/columns individually sorted (top-right corner approach). Amazon, Microsoft.

Non-overlapping Intervals — remove minimum intervals to make rest non-overlapping.

Sort by end time. Greedy: keep interval with earliest end time. For each next interval: if it overlaps (start < prevEnd), remove it (count++). Else, update prevEnd. Time O(n log n), Space O(1).

💡

Pro tip: Sort by end time (not start) for the greedy to work — earliest end maximizes room for future intervals. Google, Amazon.

Task Scheduler — least intervals needed to complete tasks with cooldown n.

Count frequencies. Most frequent task determines structure: idle time = (maxFreq−1) × (n+1) + count of tasks with maxFreq. Total = max(this value, total tasks). Time O(n), Space O(1) (26 task types).

💡

Pro tip: The formula is derived from fitting tasks into 'frames' of size n+1. If total tasks > idle formula, tasks themselves fill all slots. Amazon, Google.

Sort Colors (Dutch National Flag) — sort array of 0s, 1s, and 2s in-place.

Three pointers: low=0, mid=0, high=n−1. If arr[mid]===0: swap(low,mid), low++, mid++. If arr[mid]===1: mid++. If arr[mid]===2: swap(mid,high), high-- (don't increment mid). Time O(n), Space O(1).

💡

Pro tip: Don't advance mid after swapping with high — the swapped element (previously at high) hasn't been evaluated yet. Amazon, Microsoft, Meta.

Expert tips

Binary search on the answer space: when brute-force means trying all possible answers, binary search the answer and check feasibility.

Many sorting problems have a greedy component — sort first, then apply greedy logic.

QuickSelect > full sort when you only need the kth element — average O(n) vs O(n log n).

Interval problems almost always require sorting by start or end time first.