Menu
CoddyTech
Start learning
Learn Python step by stepOnline Python compiler

Sorting and Searching Interview Questions

Sorting trade-offs, binary search and its variants, and selecting the k-th element.

By Kevin Spektor, Co-founder & CTO

10 questions

  1. Compare the common sorting algorithms by time, space and stability.

    Merge and heap sort are O(n log n) always, quick sort on average, the simple sorts O(n²):

    • Insertion, and bubble with an early exit: O(1) space, stable, O(n) on sorted input.
    • Selection: O(1) space, not stable.
    • Merge: O(n) space, stable.
    • Quick: O(n²) worst, O(log n) stack on average, not stable.
    • Heap: O(1) space, not stable.
    • Counting: O(n + k), stable.

    Watch bubble sort make its passes.

  2. How do you implement binary search, and what are the common bugs?

    Keep a range [lo, hi] that holds the target if it exists, check the middle, and discard the half that cannot hold it. O(log n) on a sorted array.

    Python
    def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7), binary_search(nums, 4))

    Watch for while lo < hi on a closed range (skips the last candidate), lo = mid (loops forever), and in Java or C++ (lo + hi) / 2 overflowing. Watch binary search halve the range.

    Practice it: Binary Search, Square Root (Integer)

  3. What is the difference between merge sort and quick sort?

    Both are divide and conquer. Merge sort works while merging: O(n log n) always, stable, O(n) extra space, good for linked lists. Quick sort works while partitioning around a pivot: O(n²) at worst (rare with a random pivot), not stable, O(log n) stack on average, and usually faster on arrays.

    Python
    def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= keeps it stable
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

    See merge sort split and merge.

    Practice it: Merge Sorted Array

  4. How does quick sort's partition work, and how do you avoid the O(n²) worst case?

    Partition picks a pivot and moves smaller values before it and the rest after, leaving the pivot in its final place. Lomuto does it in one pass:

    Python
    import random

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    p = random.randint(lo, hi)          # random pivot
    a[p], a[hi] = a[hi], a[p]
    pivot, boundary = a[hi], lo
    for i in range(lo, hi):
        if a[i] < pivot:
            a[i], a[boundary] = a[boundary], a[i]
            boundary += 1
    a[boundary], a[hi] = a[hi], a[boundary]
    quick_sort(a, lo, boundary - 1)
    quick_sort(a, boundary + 1, hi)
    return a

print(quick_sort([5, 2, 9, 1, 5, 6, 3]))

    Pivots that split badly every time, like the last element of a sorted array, give O(n²); a random pivot avoids it. See quick sort partition an array.

    Practice it: Sort Colors

  5. Does Python's sorted() keep people with the same age in their input order?

    Python
    people = [("Asha", 25), ("Ravi", 30), ("Neha", 25), ("John", 30)]
print([name for name, age in sorted(people, key=lambda p: p[1])])

    Python's sort is guaranteed stable: items with equal keys keep their input order, so Asha stays before Neha and Ravi before John. To break ties by name in one call, use key=lambda p: (p[1], p[0]).

  6. How do you search in a rotated sorted array in O(log n)?

    Binary search, using the fact that one half of [lo, hi] is always sorted. Compare nums[lo] with nums[mid] to find that half, search it if the target is in its range, otherwise search the other.

    Python
    def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                 # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                     # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0), search_rotated(nums, 3))

    With duplicates like [1, 1, 1, 3, 1] the worst case becomes O(n).

    Practice it: Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array

  7. What is binary search on the answer?

    When you need the smallest or largest value meeting a monotonic condition (if speed k works, every faster speed works), binary search over possible answers. With an O(n) check, O(n log range).

    Python
    def min_eating_speed(piles, hours):
    def can_finish(speed):
        return sum((p + speed - 1) // speed for p in piles) <= hours

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid          # mid works, try smaller
        else:
            lo = mid + 1
    return lo

print(min_eating_speed([3, 6, 7, 11], 8))

    Look for "minimum capacity" or "minimize the largest sum" with large limits, and argue the check is monotonic.

    Practice it: Koko Eating Bananas, Split Array Largest Sum

  8. How do you find the k-th largest element, and which approach is fastest?

    Sort in O(n log n), keep a min heap of size k in O(n log k), or run quickselect in O(n) average, O(n²) worst. The heap wins when data streams in or k is small.

    Python
    import heapq

def kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]

print(kth_largest([3, 2, 1, 5, 6, 4], 2))
print(heapq.nlargest(2, [3, 2, 1, 5, 6, 4]))

    Quickselect partitions like quick sort but recurses into one side: n + n/2 + n/4 and so on, O(n).

    Practice it: Kth Largest Element in an Array, Top K Frequent Elements

  9. Why can't a comparison sort be faster than O(n log n)?

    A comparison sort must tell apart all n! orderings, and each comparison has two outcomes, so it needs at least log₂(n!) comparisons, which grows like n log n. Counting and radix sort beat it by using values as indexes, which needs integer keys in a limited range. See counting sort place values by index.

  10. How do you find the first and last position of a target in a sorted array?

    Run binary search twice: once for the first index whose value is >= target, once for the first index whose value is > target, and step back one. O(log n), while finding one copy and walking outward is O(n) when the target repeats.

    Python
    def lower_bound(nums, target):
    lo, hi = 0, len(nums)          # half-open range [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def search_range(nums, target):
    first = lower_bound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, lower_bound(nums, target + 1) - 1]   # integers only

print(search_range([5, 7, 7, 8, 8, 10], 8))
print(search_range([5, 7, 7, 8, 8, 10], 6))

    It prints [3, 4] and [-1, -1]. Python's bisect_left and bisect_right are these two searches, and the number of copies is last - first + 1.

    Practice it: Find First and Last Position of Element in Sorted Array, Binary Search

Coddy programming languages illustration

Learn to code with Coddy

Get started