Data Structures & Algorithms Interview Questions and Answers

Big O describes how runtime or memory grows with input size, ignoring constants and lower-order terms.

From fastest to slowest:

• O(1) constant: hash lookup, array index.
• O(log n) logarithmic: binary search, balanced tree operations.
• O(n) linear: single pass over input.
• O(n log n): efficient comparison sorts (merge, heap).
• O(n^2): nested loops such as naive pair comparison.
• O(2^n) exponential: naive recursive subsets.
• O(n!) factorial: brute-force permutations.

Also cover best/average/worst cases (quicksort is O(n log n) average, O(n^2) worst), space complexity, and amortised analysis (dynamic array append is amortised O(1)).

Binary search finds a target in a sorted array by halving the search range each step, giving O(log n).

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

Pitfalls: off-by-one in the boundary update, using the wrong loop condition, integer overflow with (lo + hi) / 2, and forgetting the array must be sorted. Variants find the first/last occurrence using lower-bound and upper-bound templates.