Data Structures & Algorithms interview questions & answers

1. 1.What is Big-O notation, and how do you work out the time complexity of a piece of code?easy

   Big-O describes how an algorithm's running time (or memory) grows as the input size n grows. It is an upper bound on the growth rate, so we drop constants and lower-order terms: 3n² + 5n + 2 is O(n²).

   To analyze code, I count how many times the dominant operation runs as a function of n:

   • Sequential blocks add: O(n) + O(n²) is O(n²)
   • Nested loops multiply: a loop over n inside a loop over n is O(n²)
   • Halving or doubling the problem each step gives O(log n)
   • Recursion: write a recurrence, or draw the recursion tree and sum the work per level
   • Separate inputs keep separate variables: O(a + b) or O(a · b), not O(n²)

   I also watch for hidden linear costs inside a single line, such as x in some_list, slicing, or copying a list.

   The common classes, fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).

   What interviewers listen for

   • Upper bound on growth as input size grows
   • Drop constants and lower-order terms
   • Sequential steps add; nested loops multiply
   • Halving the input each step gives O(log n)
   • Watch hidden costs like in on a list

   Likely follow-up: What is the complexity of a loop where j doubles each step, nested inside a loop over n? · How do you analyze the complexity of a recursive function?

   answer it out loud →
2. 2.Given an array of integers and a target, return the indices of two numbers that add up to the target (Two Sum). What is your approach?easy

   The brute force checks every pair: O(n²) time, O(1) space. That is my baseline, but the bottleneck is the inner search for the complement, so I replace it with a hash map.

   I walk the array once. For each x at index i, the number I need is target - x. If it is already in the map, I have my pair; otherwise I store x -> i and move on. Checking before inserting means an element is never paired with itself, and duplicates like [3, 3] with target 6 still work.

   That is O(n) time and O(n) extra space, relying on average-case O(1) hash lookups.

   If the array were already sorted, I would use two pointers from both ends instead: O(n) time and O(1) space. Sorting first costs O(n log n) and loses the original indices unless I sort (value, index) pairs.

   def two_sum(nums, target):
       seen = {}                     # value -> index
       for i, x in enumerate(nums):
           if target - x in seen:
               return [seen[target - x], i]
           seen[x] = i               # insert after checking
       return []

   What interviewers listen for

   • Brute force over all pairs is O(n²)
   • Hash map from value to index, single pass
   • Check for the complement before inserting
   • O(n) time, O(n) space on average
   • Sorted input: two pointers with O(1) space

   Likely follow-up: How would you solve 3Sum? · What changes if you must return all unique pairs?

   answer it out loud →
3. 3.What are the differences between an array and a linked list, and when would you choose each?easy

   An array stores elements in one contiguous block, so index access is O(1) by address arithmetic and iteration is very cache-friendly. The cost is that inserting or deleting in the middle shifts elements, O(n), and a fixed-size array must be reallocated to grow (dynamic arrays hide this behind amortized O(1) appends).

   A linked list stores nodes scattered in memory, each pointing to the next (and to the previous, if doubly linked). Accessing the i-th element or searching is O(n), but once you hold a reference to a node, inserting or removing next to it is O(1) with no shifting. Each node carries pointer overhead, and traversal has poor cache locality.

   In practice I default to a dynamic array (Python list, Java ArrayList) because locality usually wins. I pick a linked list when I need O(1) insert and remove at positions I already hold, like the doubly linked list inside an LRU cache, or when splicing lists together.

   What interviewers listen for

   • Array: contiguous, O(1) index access, cache-friendly
   • Array middle insert/delete is O(n) from shifting
   • Linked list: O(n) access, O(1) insert at a known node
   • Linked lists pay pointer overhead and poor locality
   • Default to dynamic arrays; lists for LRU-style splicing

   Likely follow-up: Why is linked-list insertion "O(1)" often misleading in practice? · How would you find the middle of a linked list in one pass?

   answer it out loud →
4. 4.How does a hash table work, and why are its lookups O(1) on average?easy

   A hash table stores key-value pairs in an array of buckets. To insert or find a key, it runs the key through a hash function to get an integer, then maps that to a bucket index, typically hash(key) % capacity. Jumping straight to the bucket instead of scanning is what makes it fast.

   Two keys can land in the same bucket, a collision, handled by chaining (each bucket holds a small list) or open addressing (probe for another free slot). The table tracks its load factor, entries divided by buckets, and past a threshold it allocates a bigger array and rehashes everything. That resize is O(n) but rare, so inserts stay amortized O(1).

   With a good hash function and a bounded load factor, buckets stay small on average, so get, put and delete are O(1) average. The worst case is O(n) when many keys collide.

   Keys must be hashable and stable: equal keys need equal hashes, and mutating a key after inserting it breaks lookups.

   What interviewers listen for

   • Hash function maps a key to a bucket index
   • Collisions: chaining or open addressing
   • Resize and rehash when the load factor passes a threshold
   • O(1) average, O(n) worst case
   • Equal keys must produce equal hashes

   Likely follow-up: What is the difference between chaining and open addressing? · Why shouldn't you use a mutable object as a dictionary key?

   answer it out loud →
5. 5.Walk me through how you approach a coding problem in an interview.easy

   I follow the same loop every time and talk through each step:

   • Clarify: restate the problem; ask about input size, value ranges, duplicates, negatives, empty input, and what to return when there is no answer.
   • Examples: work one normal case and a couple of edge cases by hand, which often reveals the pattern.
   • Brute force: state the obvious solution and its complexity, so there is a correct baseline.
   • Optimize: find the bottleneck and reach for a pattern: hash map, sorting, two pointers, sliding window, heap, BFS/DFS, binary search or DP. Constraints hint at the target: n around 10⁵ usually needs O(n log n) or better, while n ≤ 20 allows exponential search.
   • Code: write clean code with clear names, narrating the key decisions.
   • Test: dry-run my example, then edge cases, and fix bugs calmly.
   • Complexity: state the final time and space, plus trade-offs or what I would improve with more time.

   What interviewers listen for

   • Clarify inputs, constraints and edge cases first
   • Brute force with its complexity as a baseline
   • Optimize by finding the bottleneck and a pattern
   • Use constraints to infer the target complexity
   • Dry-run tests, then state time and space

   Likely follow-up: What do you do if you get stuck on the optimization step? · How do you choose which edge cases to test?

   answer it out loud →
6. 6.How do you reverse a singly linked list? Can you do it both iteratively and recursively?easy

   Iteratively, I walk the list with three references: prev (the already-reversed part, starting at None), curr, and a saved nxt. For each node I save curr.next, point curr.next back at prev, then advance both. When curr is None, prev is the new head. That is O(n) time and O(1) extra space. The classic bug is overwriting curr.next before saving it, which loses the rest of the list.

   Recursively, I first reverse everything after the head, which returns the new head (the old tail). Now head.next is the last node of the reversed part, so head.next.next = head appends the current node, and head.next = None cuts the old link. It is also O(n) time but uses O(n) call-stack space, so a long list can hit Python's recursion limit. I prefer the iterative version in real code.

   def reverse_list(head):
       prev, curr = None, head
       while curr:
           nxt = curr.next          # save the rest first
           curr.next = prev         # flip the pointer
           prev, curr = curr, nxt
       return prev                  # new head
   
   def reverse_rec(head):
       if head is None or head.next is None: return head
       new_head = reverse_rec(head.next)
       head.next.next = head        # hang head after its old successor
       head.next = None
       return new_head

   What interviewers listen for

   • Track prev and curr; save next before relinking
   • Iterative: O(n) time, O(1) space
   • Recursive: head.next.next = head, then head.next = None
   • Recursive version uses O(n) stack space
   • Handle empty and single-node lists

   Likely follow-up: How would you reverse only the nodes between positions m and n? · How would you reverse a list in groups of k?

   answer it out loud →
7. 7.Given a string of brackets like "([]{})", how do you check whether it is valid?easy

   Brackets must close in the reverse order they opened, which is exactly last-in, first-out, so I use a stack.

   I scan left to right and push every opening bracket. For a closing bracket, the stack must be non-empty and its top must be the matching opener; if so I pop it, otherwise the string is invalid right away. At the end the string is valid only if the stack is empty, because any leftover openers were never closed.

   A map from each closer to its opener keeps the code short. It is O(n) time and O(n) space in the worst case, such as a string of only opening brackets.

   Edge cases I test: the empty string (valid), a lone closer ")", interleaving like "([)]" (invalid) and "((" (invalid). With only one bracket type, a counter that never goes negative and ends at zero is enough, in O(1) space.

   def is_valid(s):
       pairs = {')': '(', ']': '[', '}': '{'}
       stack = []
       for ch in s:
           if ch in pairs:                       # closing bracket
               if not stack or stack.pop() != pairs[ch]:
                   return False
           else:
               stack.append(ch)                  # opening bracket
       return not stack                          # nothing left unclosed

   What interviewers listen for

   • Last-opened must close first, so use a stack
   • Push openers; a closer must match and pop the top
   • Valid only if the stack ends empty
   • O(n) time, O(n) space
   • One bracket type: a counter is enough

   Likely follow-up: How would you find the longest valid parentheses substring? · How would you generate all valid combinations of n pairs?

   answer it out loud →
8. 8.What is the difference between a stack, a queue and a deque, and how would you implement each in Python?easy

   A stack is last-in, first-out: you push and pop at the same end. It models function calls, undo, DFS and bracket matching. A Python list works well, since append and pop() at the end are amortized O(1).

   A queue is first-in, first-out: you add at the back and remove from the front. It models scheduling, buffering and BFS. I use collections.deque with append and popleft, both O(1). I avoid list.pop(0) because it shifts every remaining element, which is O(n).

   A deque (double-ended queue) supports O(1) insert and remove at both ends, so it can act as either. It is the tool behind sliding-window maximum and 0-1 BFS.

   For thread-safe producer-consumer queues Python has queue.Queue. A priority queue is a different structure again, usually a binary heap via heapq.

   What interviewers listen for

   • Stack is LIFO: list.append and list.pop()
   • Queue is FIFO: deque.append and deque.popleft()
   • list.pop(0) is O(n); avoid it for queues
   • Deque: O(1) operations at both ends
   • Stacks drive DFS; queues drive BFS

   Likely follow-up: How would you implement a queue using two stacks? · How would you design a stack that returns its minimum in O(1)?

   answer it out loud →
9. 9.What is the difference between BFS and DFS, and when would you use each?easy

   Both visit every reachable vertex and edge once, so both are O(V + E) time with an adjacency list. They differ in the order they explore.

   BFS (breadth-first search) uses a queue and explores level by level: every node at distance 1, then distance 2, and so on. That makes it the right choice for the shortest path in an unweighted graph, the minimum number of moves, and level-order tree traversal. Its memory grows with the widest frontier.

   DFS (depth-first search) uses a stack or recursion and goes as deep as possible before backtracking. It suits exhaustive exploration: connected components, cycle detection, topological sort, path finding and backtracking. Its memory grows with the depth, and deep recursion can overflow the call stack, so for very deep graphs I use an explicit stack.

   In both, I mark a node visited when I first discover it (for BFS, when I enqueue it) so it is never processed twice.

   What interviewers listen for

   • Both O(V + E) with an adjacency list
   • BFS: queue, level by level, unweighted shortest paths
   • DFS: stack or recursion, goes deep, then backtracks
   • DFS suits cycle detection, topo sort, components
   • Mark visited on discovery to avoid repeats

   Likely follow-up: Why does BFS give shortest paths only when edges are unweighted? · How would you run BFS on a grid with obstacles?

   answer it out loud →
10. 10.How do you detect whether a linked list has a cycle, ideally in O(1) extra space?easy

    The simple approach stores every visited node in a hash set and reports a cycle when it sees a node twice: O(n) time but also O(n) space.

    For O(1) space I use Floyd's tortoise and hare. Two pointers start at the head; slow moves one step and fast moves two. Without a cycle, fast reaches the end. With a cycle, both end up circling it, and each step the gap between them shrinks by one, so fast must land on slow within about one lap. It is O(n) time.

    The loop condition fast and fast.next protects both hops of the fast pointer. I compare nodes by identity (is), not by value, since values can repeat.

    To find where the cycle starts, after they meet I move one pointer back to the head and advance both one step at a time; they meet again at the cycle's entry node.

    def has_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:          # compare nodes, not values
                return True
        return False

    What interviewers listen for

    • A hash set works but costs O(n) space
    • Slow moves one step, fast moves two
    • They meet if and only if there is a cycle
    • Guard the loop with fast and fast.next
    • Reset one pointer to head to find the entry

    Likely follow-up: Why does resetting one pointer to the head find the cycle start? · How would you compute the length of the cycle?

    answer it out loud →
11. 11.How does binary search work, and what are the common bugs when implementing it?easy

    Binary search finds a target in a sorted array by repeatedly halving the search range. I keep lo and hi bounds, look at the middle element, and discard the half that cannot contain the target. Each step halves the range, so it runs in O(log n) time and O(1) space when written iteratively.

    The common bugs:

    • Off-by-one boundaries: decide whether hi is inclusive (len - 1, loop while lo <= hi) or exclusive (len, loop while lo < hi), and keep every update consistent with that choice.
    • Infinite loops: writing lo = mid where mid + 1 is needed can stop the range from shrinking.
    • Overflow: in Java or C++, (lo + hi) / 2 can overflow for large indices; lo + (hi - lo) / 2 avoids it. Python integers never overflow.
    • Broken precondition: the input must be sorted, or more generally the yes/no condition must be monotonic.

    In Python I would also mention bisect_left and bisect_right from the standard library.

    def binary_search(a, target):
        lo, hi = 0, len(a) - 1              # inclusive bounds
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if a[mid] == target:
                return mid
            if a[mid] < target:
                lo = mid + 1                # discard the left half
            else:
                hi = mid - 1                # discard the right half
        return -1

    What interviewers listen for

    • Requires sorted input or a monotonic condition
    • Halves the range each step: O(log n)
    • Pick inclusive or exclusive hi and stay consistent
    • Use mid + 1 / mid - 1 so the range shrinks
    • lo + (hi - lo) / 2 avoids overflow in Java/C++

    Likely follow-up: How would you find the first occurrence of a duplicated value? · How would you search a rotated sorted array?

    answer it out loud →
12. 12.Compare quicksort and mergesort. Which would you choose, and why?mid

    Both are divide-and-conquer O(n log n) sorts, but they split the work differently.

    Quicksort picks a pivot, partitions the array in place into smaller and larger elements, then recurses on each side. It averages O(n log n), but consistently bad pivots (for example, always the first element on already-sorted input) give O(n²). Random or median-of-three pivots make that very unlikely. It needs only O(log n) expected stack space, has excellent cache behavior, and is not stable.

    Mergesort splits in half, sorts both halves, and merges them. It is O(n log n) in every case and stable, but merging arrays needs O(n) extra space. It is the natural choice for linked lists (no random access needed) and for external sorting of data that does not fit in memory.

    Real libraries blend ideas: Python's sorted and Java's object sorts use Timsort, a stable merge/insertion hybrid, while C++ std::sort is typically introsort, a quicksort that falls back to heapsort.

    What interviewers listen for

    • Both O(n log n) on average
    • Quicksort worst case O(n²); random pivots mitigate it
    • Quicksort: in place, cache-friendly, not stable
    • Mergesort: always O(n log n), stable, O(n) extra
    • Mergesort suits linked lists and external sorting

    Likely follow-up: How does pivot choice affect quicksort? · How would you sort a linked list in O(n log n)?

    answer it out loud →
13. 13.How would you find the kth largest element in an unsorted array?mid

    There are three standard options:

    • Sort and index: O(n log n) time. Simple, and fine as a first answer.
    • Min-heap of size k: push each element and pop whenever the heap grows past k. The heap always holds the k largest values seen so far, so its root is the kth largest. That is O(n log k) time and O(k) space, and it also works on a stream.
    • Quickselect: partition like quicksort, but recurse only into the side that contains the target index. It averages O(n), with an O(n²) worst case made unlikely by a random pivot. It works in place but reorders the input.

    In an interview I present the heap as the robust default, mention quickselect for the best average time, and note that heapq.nlargest(k, nums)[-1] does the heap approach in one line.

    I also clarify that duplicates count: in [3, 3, 2] the 2nd largest is 3.

    import heapq
    
    def kth_largest(nums, k):
        heap = []                        # min-heap of the k largest so far
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)      # drop the smallest of them
        return heap[0]                   # root = kth largest

    What interviewers listen for

    • Sorting works in O(n log n)
    • Min-heap of size k: O(n log k) time, O(k) space
    • The heap root is the kth largest
    • Quickselect: average O(n), worst O(n²)
    • The heap approach also works on streams

    Likely follow-up: How does quickselect differ from quicksort? · How would you track the kth largest value in a stream?

    answer it out loud →
14. 14.Find the length of the longest substring without repeating characters. How do you get it to O(n)?mid

    Brute force checks every substring for duplicates, which is O(n²) substrings with extra work each. The optimization is a sliding window: keep a window [start, i] that never contains a repeat, and extend it one character at a time.

    I store the last index where each character was seen. When the current character already appears inside the window (its last index is at least start), I move start to just past that previous copy. Then I record the current index and update the best length, i - start + 1.

    The >= start check matters: a character last seen before the window began is not a conflict. In "abba", when the final a arrives, its old index 0 is already outside the window, so start must not move backwards.

    Each character is handled once: O(n) time, and O(min(n, alphabet size)) space for the map. Quick tests: "" gives 0, "bbbb" gives 1, "pwwkew" gives 3.

    def length_of_longest_substring(s):
        last = {}                        # char -> last index seen
        start = best = 0
        for i, ch in enumerate(s):
            if last.get(ch, -1) >= start:     # repeat inside the window
                start = last[ch] + 1          # jump past the old copy
            last[ch] = i
            best = max(best, i - start + 1)
        return best

    What interviewers listen for

    • Sliding window that never contains a repeat
    • Map each character to its last index
    • Move start only if the repeat is inside the window
    • O(n) time, O(min(n, alphabet)) space
    • Test "abba" to catch the backwards-jump bug

    Likely follow-up: How would you solve it if up to k distinct characters were allowed? · How would you return the substring itself?

    answer it out loud →
15. 15.Given a list of intervals, merge all overlapping intervals. Walk me through your approach.mid

    The key step is to sort by start. Once sorted, any interval that overlaps the current merged block must come right after it, so one pass is enough.

    I keep a result list. For each interval, if the result is empty or the interval starts after the last merged block ends, it opens a new block. Otherwise it overlaps, so I extend the last block's end to max(last_end, end). The max matters because an interval can sit entirely inside the previous one, like [1, 10] followed by [2, 3].

    I clarify whether touching intervals such as [1, 2] and [2, 3] count as overlapping; using <= merges them, < keeps them apart.

    Sorting dominates: O(n log n) time, plus O(n) space for the output and the sorted copy. I use sorted() rather than intervals.sort() so the caller's list is not mutated.

    def merge(intervals):
        merged = []
        for start, end in sorted(intervals, key=lambda iv: iv[0]):
            if merged and start <= merged[-1][1]:        # overlaps last block
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged

    What interviewers listen for

    • Sort intervals by start first
    • Overlap when start is at most the last end
    • Extend with max to handle containment
    • Clarify whether touching intervals merge
    • O(n log n) time, O(n) space

    Likely follow-up: How would you insert a new interval into a sorted, non-overlapping list? · What is the minimum number of meeting rooms these intervals need?

    answer it out loud →
16. 16.What is dynamic programming, and what is the difference between memoization and tabulation?mid

    Dynamic programming solves a problem by combining answers to smaller subproblems. It applies when two properties hold: optimal substructure (the best answer is built from best answers to subproblems) and overlapping subproblems (the same subproblems recur, so caching them pays off). Naive recursive Fibonacci is the classic sign: fib(n - 2) is recomputed again and again, giving exponential time.

    • Memoization is top-down: write the natural recursion and cache each result, for example with functools.cache. It computes only the states actually reached and is easy to derive, but it pays call overhead and can hit the recursion limit.
    • Tabulation is bottom-up: fill a table in an order where every dependency is already computed. It uses plain loops and often allows space savings, like keeping only the previous row.

    Both have the same time complexity: number of states times work per state. My recipe: define the state, write the recurrence, set base cases, choose the evaluation order, then optimize space.

    What interviewers listen for

    • Needs optimal substructure and overlapping subproblems
    • Memoization: top-down recursion plus a cache
    • Tabulation: bottom-up loops in dependency order
    • Time = number of states times work per state
    • Tabulation enables rolling-array space savings

    Likely follow-up: How do you recognize that a problem needs DP? · When would you prefer memoization over tabulation?

    answer it out loud →
17. 17.Design an LRU cache that supports get and put in O(1) time.mid

    An LRU cache evicts the least recently used entry when it is full. To make both operations O(1) I combine two structures:

    • A hash map from key to node, for O(1) lookup.
    • A doubly linked list ordered by recency, most recent at one end. With the node in hand, unlinking and re-inserting it is O(1).

    get looks up the key, moves its node to the most-recent end, and returns the value (or -1). put updates or inserts the node at the most-recent end; if the size now exceeds capacity, it removes the node at the least-recent end and deletes its key from the map, which is why each node also stores its key. Sentinel head and tail nodes remove empty-list edge cases.

    In Python, OrderedDict already is this combination, as shown. Interviewers often ask for the hand-built version too. In Java, a LinkedHashMap in access order that overrides removeEldestEntry does the same.

    from collections import OrderedDict
    class LRUCache:
        def __init__(self, capacity):
            self.cap, self.data = capacity, OrderedDict()
        def get(self, key):
            if key not in self.data:
                return -1
            self.data.move_to_end(key)           # now most recent
            return self.data[key]
        def put(self, key, value):
            self.data[key] = value
            self.data.move_to_end(key)
            if len(self.data) > self.cap:
                self.data.popitem(last=False)    # evict least recent

    What interviewers listen for

    • Hash map gives O(1) key lookup
    • Doubly linked list keeps recency order
    • Every access moves the node to the recent end
    • Evict from the old end; nodes store their keys
    • Sentinel nodes avoid null edge cases

    Likely follow-up: How would you make the cache thread-safe? · How would you design an LFU cache instead?

    answer it out loud →
18. 18.Explain in-order, pre-order, post-order and level-order traversal of a binary tree, and when you would use each.easy

    The three depth-first orders differ only in when the node is visited relative to its subtrees:

    • Pre-order (node, left, right): parents before children. Useful for copying or serializing a tree.
    • In-order (left, node, right): on a BST it yields values in sorted order, so it powers validation and kth-smallest.
    • Post-order (left, right, node): children before parents. Useful for deleting a tree or computing heights and subtree sizes.
    • Level-order (breadth-first): a queue visits the tree level by level. Useful for per-level answers, the right-side view, or minimum depth.

    All four are O(n) time. The depth-first orders use O(h) stack space, where h is the height: O(log n) for a balanced tree but O(n) for a skewed one. Level-order uses space for the widest level, which can be about n / 2 in a complete tree. Any recursive version can be rewritten with an explicit stack.

    from collections import deque
    def inorder(node, out):
        if node:
            inorder(node.left, out)     # pre-order: append before this line
            out.append(node.val)
            inorder(node.right, out)    # post-order: append after this line
    
    def level_order(root):
        out, q = [], deque([root] if root else [])
        while q:
            node = q.popleft()
            out.append(node.val)
            q.extend(c for c in (node.left, node.right) if c)
        return out

    What interviewers listen for

    • Pre: node first; in: middle; post: last
    • In-order of a BST is sorted
    • Level-order uses a queue
    • All four are O(n) time
    • DFS space is O(h); BFS space is the widest level

    Likely follow-up: Write an iterative in-order traversal with an explicit stack. · How would you rebuild a tree from its pre-order and in-order traversals?

    answer it out loud →
19. 19.What is a binary search tree, and how would you check whether a binary tree is a valid BST?mid

    A BST keeps every value in a node's left subtree smaller than the node and every value in its right subtree larger. That ordering makes search, insert and delete O(h) for height h: O(log n) when balanced, but O(n) if it degenerates into a chain, for example after inserting keys in sorted order.

    The common wrong answer compares each node only with its direct children. That misses a root 5 whose left child 3 has a right child 6: every parent-child pair looks fine, but 6 sits in the left subtree of 5.

    The fix is to pass down the valid range. The root may hold anything; going left tightens the upper bound to the node's value, going right tightens the lower bound, and every node must fall strictly inside its range. That is O(n) time and O(h) stack space.

    An alternative is an in-order traversal that checks the values are strictly increasing. I also clarify how duplicates should be treated.

    def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
        if node is None:
            return True
        if not (lo < node.val < hi):          # must fit the inherited range
            return False
        return (is_valid_bst(node.left, lo, node.val) and
                is_valid_bst(node.right, node.val, hi))

    What interviewers listen for

    • Left subtree smaller, right subtree larger, recursively
    • Operations are O(h); a degenerate tree is O(n)
    • Checking only direct children is wrong
    • Pass down min and max bounds
    • Or: in-order values must be strictly increasing

    Likely follow-up: How would you find the kth smallest element in a BST? · How would you find the lowest common ancestor of two nodes in a BST?

    answer it out loud →
20. 20.How do you analyze space complexity? Does the recursion stack count?easy

    Space complexity measures the memory an algorithm needs as a function of input size. I usually report auxiliary space, the memory beyond the input itself, and I say so explicitly, because some people count the input too.

    I add up:

    • Data structures I allocate: a hash map with n entries is O(n), while a fixed 26-letter count array is O(1).
    • The recursion stack: yes, it counts. Each active call holds a frame, so the cost is proportional to the maximum recursion depth, not the total number of calls. Recursive DFS on a balanced tree is O(log n); on a skewed tree it is O(n). Memoized Fibonacci uses O(n) for the cache plus O(n) of stack.
    • Hidden copies: slicing, sorted(), string building and list comprehensions all allocate.

    The output is usually excluded unless the question says otherwise. Replacing recursion with a loop, or keeping only the previous DP row, are the usual ways to cut space.

    What interviewers listen for

    • Report auxiliary space, and say so
    • The recursion stack counts, by maximum depth
    • Balanced-tree DFS O(log n); skewed O(n)
    • Watch hidden copies: slicing, sorted()
    • Output is usually excluded from the count

    Likely follow-up: What is the space complexity of merge sort on an array? · How would you reduce a 2D DP table to a single row?

    answer it out loud →
21. 21.What is a heap, and how is it used to implement a priority queue?easy

    A binary heap is a complete binary tree with the heap property: in a min-heap every parent is less than or equal to its children, so the minimum sits at the root. A max-heap is the mirror image. Beyond that it is not sorted; siblings have no order.

    Because the tree is complete, it lives compactly in an array: the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i - 1) // 2.

    • Peek: O(1), the root is a[0].
    • Push: append, then sift up, O(log n).
    • Pop: move the last element to the root, then sift down, O(log n).
    • Build from n items: O(n) with bottom-up heapify.

    A priority queue is the abstract "give me the highest-priority item" interface, and a heap is its usual implementation. Python's heapq is a min-heap over a list; for a max-heap, push negated keys. Heaps power Dijkstra, top-k, merging sorted lists and schedulers.

    What interviewers listen for

    • Complete binary tree; parent at most its children
    • Array layout: children at 2i+1 and 2i+2
    • Peek O(1); push and pop O(log n)
    • Bottom-up heapify builds a heap in O(n)
    • heapq is a min-heap; negate keys for max

    Likely follow-up: Why is building a heap O(n) rather than O(n log n)? · How would you merge k sorted lists with a heap?

    answer it out loud →
22. 22.Given an array, return the k most frequent elements. Can you beat O(n log n)?mid

    First I count frequencies with a hash map (Counter), which is O(n). Then I need the k keys with the highest counts, among m distinct values:

    • Sort the distinct values by count: O(m log m), the O(n log n) baseline.
    • Min-heap of size k keyed by count: O(m log k). heapq.nlargest(k, count, key=count.get) does it in one line.
    • Bucket sort: every frequency lies between 1 and n, so I create n + 1 buckets where bucket c holds the values seen exactly c times, then walk from the highest bucket down until I have k values. That is O(n) time and O(n) space.

    I mention Counter.most_common(k) as the idiomatic library call, then write the bucket version when asked to beat O(n log n). I also clarify ties: when several values share the cut-off frequency, any of them is usually acceptable.

    from collections import Counter
    
    def top_k_frequent(nums, k):
        count = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]    # index = frequency
        for x, c in count.items():
            buckets[c].append(x)
        out = []
        for c in range(len(nums), 0, -1):               # highest frequency first
            for x in buckets[c]:
                out.append(x)
                if len(out) == k:
                    return out
        return out

    What interviewers listen for

    • Count frequencies first in O(n)
    • Heap of size k: O(m log k)
    • Frequencies are at most n, so bucket them
    • Bucket sort gives O(n) time and space
    • Clarify tie-breaking at the cut-off

    Likely follow-up: How would you handle a stream too large to fit in memory? · How would you return the k most frequent words, alphabetical on ties?

    answer it out loud →
23. 23.What is the two-pointer technique, and what kinds of problems does it solve?easy

    Two pointers means walking an array or string with two indices instead of nested loops, moving them by a rule so the total work is O(n) rather than O(n²). There are two main shapes:

    • Opposite ends: one pointer at each end, moving inward. On a sorted array, pair sum works this way: if a[lo] + a[hi] is too small, move lo right; if too large, move hi left. Each move safely discards candidates, giving O(n) time and O(1) space. Palindrome checks, in-place reversal and container-with-most-water fit here too.
    • Same direction (read and write pointers): a fast pointer scans while a slow one marks where to write. Removing duplicates from a sorted array in place, moving zeros to the end, and merging two sorted arrays work this way.

    3Sum combines both: sort, fix one element, then run the opposite-ends search on the rest, for O(n²) overall.

    Signals to reach for it: sorted input, pairs or triples, in-place rewriting, or a symmetric check.

    What interviewers listen for

    • Coordinated indices replace nested loops
    • Opposite ends on sorted input: O(n), O(1) space
    • Same direction: read/write pointers for in-place edits
    • Each move must safely discard candidates
    • 3Sum: sort plus two pointers, O(n²)

    Likely follow-up: Why is it safe to move the shorter side in container-with-most-water? · How do you skip duplicate triplets in 3Sum?

    answer it out loud →
24. 24.You can climb 1 or 2 steps at a time. How many distinct ways are there to reach step n?easy

    To land on step n, the last move was either a 1-step from n - 1 or a 2-step from n - 2. Those groups do not overlap and together cover every path, so ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1. That is the Fibonacci recurrence.

    Plain recursion is exponential, roughly O(1.6ⁿ), because the same values are recomputed many times. That repeated work is the overlapping subproblems signal for DP.

    • Memoization: cache the recursive function so each n is computed once: O(n) time, O(n) space for the cache and the stack.
    • Tabulation: loop upward keeping only the last two values: O(n) time, O(1) space.

    I present the bottom-up version as the final answer. Variations interviewers like: steps of 1, 2 or 3 (sum the last three), an arbitrary set of step sizes (a coin-change style loop), or a cost per step (min-cost climbing stairs).

    from functools import cache
    
    @cache
    def climb_memo(n):
        return 1 if n <= 1 else climb_memo(n - 1) + climb_memo(n - 2)
    
    def climb(n):                     # bottom-up, O(1) space
        a, b = 1, 1                   # ways(0), ways(1)
        for _ in range(n - 1):
            a, b = b, a + b
        return b

    What interviewers listen for

    • Last move was 1 or 2 steps: f(n) = f(n-1) + f(n-2)
    • Base cases f(0) = f(1) = 1
    • Naive recursion is exponential
    • Memoized: O(n) time and space
    • Bottom-up with two variables: O(1) space

    Likely follow-up: What if you could take 1, 2 or 3 steps? · How would you handle a cost for landing on each step?

    answer it out loud →
25. 25.Given coin denominations and an amount, find the minimum number of coins needed. Why does a greedy approach fail?mid

    Greedy (always take the largest coin that fits) works for coin systems like 1, 5, 10, 25, but not in general. With coins [1, 3, 4] and amount 6, greedy picks 4 + 1 + 1 (3 coins), while 3 + 3 needs only 2.

    So I use DP. Let dp[a] be the fewest coins that make amount a. The last coin used is some c, leaving a - c, so dp[a] = 1 + min(dp[a - c]) over coins c <= a, with dp[0] = 0. Amounts that cannot be made stay at infinity, and I return -1 for them.

    It is O(amount × number of coins) time and O(amount) space. That is pseudo-polynomial: polynomial in the numeric value of amount, not in the number of digits needed to write it.

    The sibling problem, counting the number of ways to make the amount, puts coins in the outer loop so each combination is counted once rather than once per ordering.

    def coin_change(coins, amount):
        INF = float('inf')
        dp = [0] + [INF] * amount           # dp[a] = fewest coins for a
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] + 1 < dp[a]:
                    dp[a] = dp[a - c] + 1
        return dp[amount] if dp[amount] != INF else -1

    What interviewers listen for

    • Greedy fails: coins [1, 3, 4], amount 6
    • dp[a] = 1 + min(dp[a - c]), with dp[0] = 0
    • Unreachable amounts stay infinite; return -1
    • O(amount × coins) time, O(amount) space
    • Counting combinations: coins in the outer loop

    Likely follow-up: How would you count the number of combinations instead? · Could you solve it with BFS instead of DP?

    answer it out loud →
26. 26.What are the trade-offs between recursion and iteration? Can every recursive solution be made iterative?easy

    Recursion expresses a problem in terms of smaller copies of itself, with a base case that stops it. It is the natural fit for trees, divide and conquer, backtracking and DFS, and the code often mirrors the recurrence directly.

    The costs: each call pushes a stack frame, so space is O(depth), and deep recursion can overflow the stack. Python's default recursion limit is 1000 and it has no tail-call optimization, so recursing down a 100,000-node linked list fails. Calls also add constant-factor overhead.

    Iteration uses loops and explicit state. It avoids stack overflow, is usually faster, and makes memory use obvious.

    Yes, every recursion can be converted: the call stack is just a stack, so you can manage one yourself, as in iterative DFS or iterative in-order traversal. Tail-recursive and simple linear recursions become plain loops.

    My rule: use recursion when it is clearer and the depth is bounded, such as O(log n) on a balanced tree, and switch to iteration when depth can grow with n.

    What interviewers listen for

    • Recursion needs a base case and shrinking input
    • Each call costs a frame: O(depth) space
    • Python: default limit 1000, no tail-call optimization
    • Any recursion converts to a loop plus explicit stack
    • Prefer iteration when depth grows with n

    Likely follow-up: Convert a recursive pre-order traversal into an iterative one. · What is tail recursion, and why does it matter?

    answer it out loud →
27. 27.What is amortized analysis? Explain why appending to a dynamic array is O(1) amortized.mid

    Amortized analysis bounds the total cost of a sequence of operations and divides by the number of operations. It is a worst-case guarantee on the average over the sequence, which is different from average-case analysis: no probability or random inputs are involved.

    A dynamic array (Python list, Java ArrayList) keeps spare capacity. Most appends just write into the next free slot, O(1). When it is full, it allocates a bigger block and copies every element, O(n) for that one append.

    If capacity doubles, the copies across n appends total 1 + 2 + 4 + ... up to n, a geometric series below 2n. So n appends cost O(n) overall, O(1) amortized each. What matters is geometric growth: any constant factor above 1 works (Java's ArrayList grows by about 1.5x, and CPython over-allocates by a smaller fraction). Growing by a fixed number of slots instead makes the sequence O(n²).

    The formal tools are the aggregate method (used above), the accounting method and the potential method.

    What interviewers listen for

    • Total cost of a sequence divided by its length
    • Not average case: no probability involved
    • Rare O(n) resize, otherwise O(1) writes
    • Geometric growth keeps total copying under 2n
    • Fixed-size growth degrades to O(n²) total

    Likely follow-up: Why do some implementations grow by 1.5x rather than 2x? · What goes wrong if you halve the array whenever it becomes half empty?

    answer it out loud →
28. 28.What is the difference between Big-O, Big-Θ and Big-Ω? Is Big-O the same as the worst case?mid

    All three bound how a function grows, for large enough n and up to a constant factor:

    • Big-O is an upper bound: f(n) = O(g(n)) if f(n) ≤ c · g(n) for some constant c and every n past some n₀.
    • Big-Ω is a lower bound: eventually f(n) ≥ c · g(n).
    • Big-Θ is a tight bound: both at once, so f grows like g.

    So 3n² + n is Θ(n²). It is also technically O(n³), true but uninformative. In interviews people say Big-O but usually mean the tight bound.

    And no, Big-O is not "the worst case". Best, average and worst case choose which inputs you analyze; O, Ω and Θ describe what kind of bound you state about that cost. Insertion sort is Θ(n²) in the worst case and Θ(n) in the best case, on already-sorted input. The comparison-sort lower bound is an Ω statement: any comparison sort needs Ω(n log n) comparisons in the worst case.

    What interviewers listen for

    • O is upper, Ω is lower, Θ is tight
    • Holds up to a constant, for large n
    • Interview "Big-O" usually means the tight bound
    • Cases pick inputs; notations describe bounds
    • Insertion sort: worst Θ(n²), best Θ(n)

    Likely follow-up: Is 2ⁿ⁺¹ in O(2ⁿ)? What about 2²ⁿ? · What is the average-case complexity of quicksort, and why?

    answer it out loud →
29. 29.How do you implement a queue using two stacks, and what does each operation cost?mid

    I use an inbox stack for pushes and an outbox stack for pops.

    • Push: append to the inbox, O(1).
    • Pop or peek: if the outbox is empty, pop everything off the inbox onto the outbox. That reverses the order, so the oldest element ends up on top. Then pop from the outbox.

    The key detail is to transfer only when the outbox is empty. Transferring while it still holds items would put newer elements above older ones and break FIFO order.

    A single pop can cost O(n) when it triggers a transfer, but each element is pushed onto the inbox once, moved once, and popped from the outbox once. So n operations cost O(n) in total, which makes every operation amortized O(1), with O(n) space.

    The reverse puzzle, a stack built from queues, also works, but then push or pop costs O(n) every time rather than amortized.

    class MyQueue:
        def __init__(self):
            self.inbox, self.outbox = [], []
    
        def push(self, x):
            self.inbox.append(x)
    
        def pop(self):
            if not self.outbox:                  # refill only when empty
                while self.inbox:
                    self.outbox.append(self.inbox.pop())
            return self.outbox.pop()

    What interviewers listen for

    • Inbox for pushes, outbox for pops
    • Transfer only when the outbox is empty
    • Transfer reverses order, oldest on top
    • Each element is moved at most once
    • Amortized O(1) per operation

    Likely follow-up: What is the worst case for a single pop? · How would you implement a stack using queues?

    answer it out loud →
30. 30.How do you represent a graph in code? Compare an adjacency list with an adjacency matrix.easy

    The two standard representations, for V vertices and E edges:

    • Adjacency list: each vertex maps to a list (or set) of its neighbors, for example a dict of lists in Python. Space is O(V + E) and listing a vertex's neighbors costs O(degree), so BFS and DFS run in O(V + E). Checking one specific edge is O(degree), or O(1) on average if neighbors are kept in sets.
    • Adjacency matrix: a V × V grid where m[u][v] holds 1 or the edge weight. Edge lookup is O(1), but space is O(V²) however few edges there are, and listing neighbors costs O(V), so BFS becomes O(V²).

    Most real graphs are sparse, with E far below V², so I default to adjacency lists. A matrix makes sense for small or dense graphs, frequent edge queries, or matrix-shaped algorithms like Floyd-Warshall.

    An edge list of (u, v, weight) tuples is a third option, handy for Kruskal's algorithm, and grids are implicit graphs whose neighbors are computed on the fly.

    What interviewers listen for

    • List: O(V + E) space, neighbors in O(degree)
    • Matrix: O(V²) space, O(1) edge check
    • Traversal: O(V + E) with lists, O(V²) with a matrix
    • Default to lists for sparse graphs
    • Edge lists suit Kruskal; grids are implicit graphs

    Likely follow-up: How would you store a weighted, directed graph? · When would you choose Floyd-Warshall over running Dijkstra from every node?

    answer it out loud →
31. 31.Explain the sliding window technique. How do you know when it applies, and when does it break?mid

    A sliding window maintains a contiguous range [left, right] over an array or string and updates an aggregate incrementally as the window moves, instead of recomputing it for every subarray. That turns O(n²) or worse into O(n).

    • Fixed size: for "max sum of any k consecutive elements", add the element entering on the right and subtract the one leaving on the left, O(1) per step.
    • Variable size: extend right each step; while the window violates the condition, shrink from left. Each index enters and leaves at most once, so it is O(n) overall despite the inner while. Longest substring without repeats and shortest subarray with sum at least target work this way.

    It applies when validity is monotonic in the window: shrinking a valid window keeps it valid, or growing an invalid one keeps it invalid. That is why "shortest subarray with sum at least target" needs non-negative numbers. With negatives, adding an element can lower the sum, so I switch to prefix sums with a hash map, or a monotonic deque.

    What interviewers listen for

    • Contiguous range with an incrementally updated aggregate
    • Fixed size: add the incoming, remove the outgoing
    • Variable size: extend right, shrink left while invalid
    • Each index enters and leaves once: O(n)
    • Needs monotonic validity; negatives break sum windows

    Likely follow-up: How would you find the minimum window substring containing all characters of t? · How would you count subarrays with exactly k distinct values?

    answer it out loud →
32. 32.What are prefix sums, and how would you count the subarrays that sum to k?mid

    A prefix sum array stores running totals: P[0] = 0 and P[i + 1] = P[i] + a[i]. After O(n) preprocessing, the sum of any range a[i..j] is P[j + 1] - P[i] in O(1), so repeated range-sum queries become cheap. The idea extends to 2D grids, and its inverse, a difference array, applies range updates in O(1) each.

    For "count subarrays summing to k": a subarray ending at the current index sums to k exactly when some earlier prefix equals prefix - k. So I sweep once, keep a hash map from each prefix sum to how many times it has occurred, and add seen[prefix - k] at every step. The map starts as {0: 1} so subarrays that begin at index 0 are counted.

    That is O(n) time and O(n) space, and unlike a sliding window it works with negative numbers. The brute force, summing every subarray, is O(n²).

    def subarray_sum(nums, k):
        count = prefix = 0
        seen = {0: 1}                     # prefix sum -> times seen
        for x in nums:
            prefix += x
            count += seen.get(prefix - k, 0)
            seen[prefix] = seen.get(prefix, 0) + 1
        return count

    What interviewers listen for

    • P[i+1] = P[i] + a[i]; range sum is P[j+1] - P[i]
    • O(n) preprocessing, O(1) per query
    • Count earlier prefixes equal to prefix - k
    • Seed the map with {0: 1}
    • Handles negatives, unlike a sliding window

    Likely follow-up: How would you find the longest subarray with sum k? · How do 2D prefix sums answer rectangle-sum queries?

    answer it out loud →
33. 33.What is a topological sort, and how would you compute one, for example to order courses with prerequisites?mid

    A topological order of a directed graph lists the vertices so that every edge u -> v has u before v. It exists only for a DAG (directed acyclic graph); a cycle means no valid order. Typical uses are build systems, task scheduling and course prerequisites.

    Kahn's algorithm is BFS-based: compute every in-degree and queue the vertices with in-degree 0, since nothing must precede them. Repeatedly pop a vertex, append it to the order, and decrement its neighbors' in-degrees, queuing any that reach 0. If the order ends up shorter than V, the leftover vertices sit on a cycle, so this doubles as cycle detection.

    The DFS alternative appends each vertex after all its descendants finish (post-order), then reverses the list; cycle detection there needs an "on the current path" marker.

    Both are O(V + E) time and space. The order is usually not unique; using a min-heap instead of a queue yields the lexicographically smallest one.

    from collections import deque
    def topo_sort(n, edges):                   # (u, v): u must come before v
        graph, indeg = [[] for _ in range(n)], [0] * n
        for u, v in edges:
            graph[u].append(v)
            indeg[v] += 1
        q, order = deque(i for i in range(n) if indeg[i] == 0), []
        while q:
            u = q.popleft()
            order.append(u)
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0: q.append(v)
        return order if len(order) == n else None    # None: there is a cycle

    What interviewers listen for

    • Every edge u -> v puts u before v
    • Only possible for a DAG
    • Kahn's: repeatedly remove in-degree-0 vertices
    • Output shorter than V means a cycle
    • O(V + E); reversed DFS post-order also works

    Likely follow-up: How would you report which courses form the cycle? · How would you find the minimum number of semesters needed to finish all courses?

    answer it out loud →
34. 34.How does Dijkstra's algorithm work, what is its complexity, and when does it fail?hard

    Dijkstra finds shortest paths from one source in a graph with non-negative edge weights. It is BFS with a priority queue: always expand the vertex with the smallest known distance, because with no negative edges nothing found later can make that distance shorter.

    I keep a dist map and a min-heap of (distance, vertex) pairs. Pop the smallest; if it is stale (larger than the recorded distance), skip it. Otherwise relax each outgoing edge: if d + w beats the neighbor's best distance, record it and push the new pair. This lazy deletion avoids needing a decrease-key operation.

    With a binary heap it is O((V + E) log V) time and O(V + E) space. A Fibonacci heap improves the bound to O(E + V log V), and a plain array scan gives O(V²), which suits dense graphs.

    It fails with negative edges: a vertex can be finalized before a cheaper path through a negative edge is discovered. Then I use Bellman-Ford, O(V · E), which also detects negative cycles. For unweighted graphs, plain BFS is enough.

    import heapq
    def dijkstra(graph, src):             # graph: {u: [(v, weight), ...]}
        dist = {src: 0}
        pq = [(0, src)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue                  # stale entry: u was already improved
            for v, w in graph.get(u, []):
                nd = d + w
                if nd < dist.get(v, float('inf')):
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        return dist

    What interviewers listen for

    • Non-negative edge weights only
    • Min-heap always expands the closest vertex
    • Relax edges; skip stale heap entries
    • Binary heap: O((V + E) log V)
    • Negative edges: use Bellman-Ford instead

    Likely follow-up: How would you reconstruct the actual path, not just the distance? · How does A* search improve on Dijkstra?

    answer it out loud →
35. 35.Compare chaining and open addressing for resolving hash collisions. What role do the load factor and the worst case play?hard

    With separate chaining, each bucket holds a list (or tree) of the entries that hash there. It is simple, deletion is easy, and the load factor can exceed 1, with performance degrading gradually as chains grow. The cost is a pointer per entry and weaker cache locality. Java's HashMap chains, resizes past a default load factor of 0.75, and converts very long buckets into balanced trees.

    With open addressing, entries live in the array itself, and a collision probes for another slot: linear probing, quadratic probing or double hashing. It is compact and cache-friendly, which is why CPython's dict uses it, but the load factor must stay well below 1 because probe sequences lengthen sharply as the table fills. Linear probing also suffers primary clustering, and deletion needs tombstones so later searches do not stop early.

    Either way, O(1) average needs a well-spreading hash and geometric resizing. The worst case is O(n) when keys collide, which attackers can force (hash flooding); keyed, randomized hashing like Python's SipHash-based string hash, and Java's tree bins, limit the damage.

    What interviewers listen for

    • Chaining: per-bucket lists; load factor may exceed 1
    • Open addressing: probe inside the array, cache-friendly
    • Open addressing needs a low load factor and tombstones
    • Linear probing suffers primary clustering
    • Worst case O(n); keyed hashing resists flooding

    Likely follow-up: Why does deleting from a linear-probing table need tombstones? · What happens to a Java HashMap bucket that collects many collisions?

    answer it out loud →
36. 36.What is a greedy algorithm, how do you know when greedy is correct, and when does it fail?mid

    A greedy algorithm builds a solution by making the locally best choice at each step and never revisiting it. It is correct when the problem has the greedy-choice property (some optimal solution starts with the greedy choice) and optimal substructure (what remains is a smaller instance of the same problem).

    Classic cases where greedy is provably optimal:

    • Interval scheduling: to fit the most non-overlapping intervals, always pick the one that ends earliest.
    • Fractional knapsack: take items by value-to-weight ratio.
    • Huffman coding, Dijkstra, and Kruskal or Prim for minimum spanning trees.

    Where it fails: 0/1 knapsack, where the best-ratio item can waste capacity; coin change with arbitrary coins, like [1, 3, 4] for amount 6; and longest-path problems. Those need DP or search.

    To justify greedy in an interview I use an exchange argument: take any optimal solution, swap in the greedy choice, and show it gets no worse. If I cannot make that argument, I hunt for a small counterexample, and if I find one I move to DP.

    What interviewers listen for

    • Locally best choice, never revisited
    • Needs greedy-choice property and optimal substructure
    • Works: earliest-end interval scheduling, MST, Huffman
    • Fails: 0/1 knapsack, arbitrary coin change
    • Prove with an exchange argument, or find a counterexample

    Likely follow-up: Why does picking the earliest end time work, but earliest start time does not? · Can you give a counterexample for greedy 0/1 knapsack?

    answer it out loud →
37. 37.What is backtracking? Walk me through generating all subsets of a list.mid

    Backtracking is DFS over a tree of partial solutions. At each step I choose an option, explore further recursively, then un-choose it to restore state before trying the next option. It fits problems that ask for all solutions or any valid configuration: subsets, permutations, combination sum, N-queens, Sudoku and word search.

    For subsets, each call records the current path as one subset, then tries adding each remaining element from start onward. Recursing with i + 1 keeps elements in increasing index order, so [1, 2] and [2, 1] are not both produced. I append a copy of the path, because the list itself keeps changing.

    There are 2ⁿ subsets and copying each costs up to O(n), so it is O(n · 2ⁿ) time, with O(n) recursion depth beyond the output. Permutations cost O(n · n!).

    The main optimization is pruning: abandon a branch as soon as it cannot lead to a valid answer, for example when a running sum passes the target, or skip duplicates after sorting.

    def subsets(nums):
        out, path = [], []
        def backtrack(start):
            out.append(path[:])              # record a copy of the current subset
            for i in range(start, len(nums)):
                path.append(nums[i])         # choose
                backtrack(i + 1)             # explore
                path.pop()                   # un-choose
        backtrack(0)
        return out

    What interviewers listen for

    • Choose, explore, un-choose
    • DFS over partial solutions
    • Append a copy of the current path
    • Subsets O(n · 2ⁿ); permutations O(n · n!)
    • Prune branches that cannot succeed

    Likely follow-up: How would you generate subsets when the input contains duplicates? · How would you solve N-queens with backtracking?

    answer it out loud →
38. 38.Beyond detecting a cycle, where else is the fast and slow pointer technique useful?mid

    Fast and slow pointers move through a sequence at different speeds, usually one and two steps. Besides detecting a cycle, the pattern solves:

    • Middle of a linked list in one pass: when fast reaches the end, slow is in the middle. Starting both at the head with while fast and fast.next, an even-length list gives the second middle node.
    • Start of a cycle: after they meet, reset one pointer to the head and step both by one; they meet at the entry. If the head is a steps from the entry and they met b steps into a cycle of length c, then a + b is a multiple of c, so a more steps from the meeting point reach the entry.
    • Palindrome linked list: find the middle, reverse the second half, compare.
    • Implicit sequences: "happy number" and "find the duplicate number" treat x -> f(x) as a linked list with a cycle.

    All of these run in O(n) time and O(1) space.

    What interviewers listen for

    • Two pointers at different speeds, usually 1 and 2
    • Finds the middle of a list in one pass
    • Reset one pointer to head to find the cycle entry
    • Palindrome list: middle, reverse half, compare
    • Implicit cycles: happy number, find the duplicate

    Likely follow-up: Why is a + b a multiple of the cycle length at the meeting point? · How would you find the duplicate in an array of n + 1 integers in O(1) space?

    answer it out loud →
39. 39.What is a monotonic stack, and how does it find the next greater element for every item in O(n)?hard

    A monotonic stack keeps its contents in sorted order (increasing or decreasing) by popping anything that would break the order before pushing. It answers "nearest greater or smaller element to the left or right" for every position in one pass.

    For next greater element, I scan left to right with a stack of indices whose answer is still unknown; their values decrease from bottom to top. When a new value x arrives, every index on top with a smaller value has just found its next greater element, x, so I pop it and record the answer. Then I push the current index. Whatever remains at the end has no greater element, so it keeps -1.

    It looks nested, but each index is pushed once and popped at most once, so the total is O(n) time (amortized O(1) per element) and O(n) space.

    The same pattern solves daily temperatures (store the index distance instead), stock span, largest rectangle in a histogram and trapping rain water. For a circular array, loop over 2n positions using i % n.

    def next_greater(nums):
        res = [-1] * len(nums)
        stack = []                        # indices; their values decrease upward
        for i, x in enumerate(nums):
            while stack and nums[stack[-1]] < x:
                res[stack.pop()] = x      # x is the next greater for that index
            stack.append(i)
        return res

    What interviewers listen for

    • Stack kept sorted by popping violators first
    • Unresolved indices wait on the stack
    • A pop means the new value is their answer
    • Each index is pushed and popped once: O(n)
    • Also: daily temperatures, histogram, rain water

    Likely follow-up: How would you find the largest rectangle in a histogram? · How would you handle a circular array?

    answer it out loud →
40. 40.What does it mean for a sorting algorithm to be stable, and why does it matter?easy

    A sort is stable if elements that compare equal keep their original relative order. Sorting [("bob", 25), ("amy", 30), ("cat", 25)] by age, a stable sort guarantees bob still comes before cat.

    It matters mostly for multi-key sorting: sort by the secondary key first, then stable-sort by the primary key, and ties on the primary key stay ordered by the secondary one. Tables where you click one column after another rely on this, and so does LSD radix sort.

    • Stable: merge sort, insertion sort, bubble sort, counting sort and Timsort. Python's sorted and list.sort are guaranteed stable, and so is Java's object sort.
    • Not stable in their usual form: quicksort, heapsort and selection sort, which move elements long distances past equal ones.

    Any sort can be made stable by using the original index as a tie-breaker, at the cost of extra space. For plain integers stability is invisible, since equal values are indistinguishable, which is why Java can sort an int[] with a non-stable quicksort.

    What interviewers listen for

    • Equal keys keep their original relative order
    • Enables multi-key sorting in successive passes
    • Stable: merge, insertion, counting, Timsort
    • Unstable: quicksort, heapsort, selection sort
    • Original index as tie-breaker forces stability

    Likely follow-up: How would you sort people by last name, then first name, using a stable sort? · Why must the per-digit sort inside LSD radix sort be stable?

    answer it out loud →
41. 41.Why can no comparison-based sorting algorithm do better than Ω(n log n) comparisons in the worst case?hard

    Model any comparison sort as a decision tree. Each internal node is one comparison, like "is a[i] < a[j]?", with a branch per outcome, and each leaf is a final ordering. To be correct on every input of n distinct values, the algorithm must be able to produce all n! permutations, so the tree needs at least n! leaves.

    A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n!, which gives h ≥ log₂(n!). The height is the worst-case number of comparisons. By Stirling's approximation, log₂(n!) is Θ(n log n); a quick argument is that the larger half of the factors are each at least n/2, so n! ≥ (n/2)^(n/2).

    So merge sort and heapsort are asymptotically optimal comparison sorts, and a similar argument bounds the average case too.

    The bound only covers algorithms that learn about the input by comparing elements. Counting sort and radix sort read key values or digits directly, so they can run in linear time when the key range or key length is bounded.

    What interviewers listen for

    • Decision tree: comparisons are nodes, orderings are leaves
    • It must distinguish all n! permutations
    • Height h ≥ log₂(n!), which is Θ(n log n)
    • Merge sort and heapsort are asymptotically optimal
    • Non-comparison sorts escape it using key values

    Likely follow-up: How many comparisons do you need to find both the minimum and maximum of n items? · Does the bound apply to sorting integers from a small known range?

    answer it out loud →
42. 42.What is a trie, and when would you use one instead of a hash set?mid

    A trie (prefix tree) stores strings character by character. Each node represents a prefix and has children keyed by the next character, plus an end-of-word flag, because a word like "car" can also be a prefix of "card". In Python each node is often just a dict of children.

    Insert and exact search walk one node per character, O(L) for a word of length L, no matter how many words are stored. The real advantage is prefix queries: "does any word start with pre?" is also O(L), and collecting every completion is a DFS from that node. A hash set cannot answer prefix questions without scanning every key.

    Use cases: autocomplete, spell checking, word games like Word Search II (prune the grid DFS as soon as the path is not a prefix), and longest-prefix matching as in IP routing tables.

    The downside is memory: many small nodes with pointers, especially with fixed 26-slot child arrays. Compressed tries (radix trees) merge single-child chains to save space. For plain membership checks, a hash set is simpler and usually faster.

    What interviewers listen for

    • Tree of characters; each node is a prefix
    • End-of-word flag separates words from prefixes
    • Insert and search in O(L) for word length L
    • Prefix queries and autocomplete beat a hash set
    • Memory-heavy; radix trees compress chains

    Likely follow-up: How would you build autocomplete that returns the top 3 suggestions? · How does a trie speed up Word Search II?

    answer it out loud →
43. 43.What is union-find (disjoint set union), and what makes its operations nearly constant time?hard

    Union-find tracks a partition of elements into disjoint sets with two operations: find(x) returns the representative (root) of x's set, and union(a, b) merges two sets. Each set is a tree stored in a parent array, where a root is its own parent.

    Naively, trees can turn into long chains and find becomes O(n). Two optimizations fix that:

    • Union by rank or size: attach the smaller tree under the larger root, which keeps height O(log n).
    • Path compression: during find, point every visited node straight at the root, flattening the tree for next time.

    Either one alone gives roughly O(log n) per operation. With both, operations are amortized O(α(n)), where α is the inverse Ackermann function, at most 4 for any realistic n, so effectively constant.

    Uses: counting connected components, detecting a cycle in an undirected graph (an edge whose endpoints already share a root closes a cycle), Kruskal's minimum spanning tree, and grouping problems like accounts merge. It handles edges arriving online, but it cannot split sets apart.

    class DSU:
        def __init__(self, n):
            self.parent, self.size = list(range(n)), [1] * n
        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])   # path compression
            return self.parent[x]
        def union(self, a, b):
            ra, rb = self.find(a), self.find(b)
            if ra == rb: return False                # already connected
            if self.size[ra] < self.size[rb]: ra, rb = rb, ra
            self.parent[rb] = ra                     # union by size
            self.size[ra] += self.size[rb]
            return True

    What interviewers listen for

    • find returns the root; union merges two sets
    • Union by size or rank keeps trees shallow
    • Path compression flattens trees during find
    • Both together: amortized O(α(n)), effectively constant
    • Uses: components, undirected cycles, Kruskal

    Likely follow-up: How does Kruskal's algorithm use union-find? · Why can union-find not detect cycles in a directed graph?

    answer it out loud →
44. 44.How do you detect a cycle in an undirected graph, and how is that different for a directed graph?hard

    The two cases need different rules, and mixing them up is a classic mistake.

    Undirected: run DFS or BFS and remember each vertex's parent. Every edge appears in both directions, so seeing the parent again is not a cycle; reaching any other already-visited vertex is. Union-find also works: if an edge's endpoints already share a root, that edge closes a cycle. A handy sanity check is that a connected undirected graph is acyclic exactly when it has V - 1 edges.

    Directed: "already visited" is not enough, because two paths can reach the same vertex without any cycle, as in a diamond. I use DFS with three colors: white (unvisited), gray (on the current recursion path) and black (finished). An edge to a gray vertex is a back edge, which means a cycle; an edge to a black vertex is fine. Alternatively, run Kahn's topological sort: if it cannot output all V vertices, there is a cycle.

    All of these are O(V + E) time, and I start a search from every unvisited vertex so disconnected components are covered.

    What interviewers listen for

    • Undirected: a visited neighbor other than the parent
    • Undirected alternative: union-find over the edges
    • Directed: three colors; an edge to gray is a cycle
    • Directed alternative: Kahn's outputs fewer than V
    • Cover every component; O(V + E) time

    Likely follow-up: How would you handle parallel edges in the undirected case? · How would you return the vertices that form the cycle?

    answer it out loud →
45. 45.Why do we need self-balancing BSTs? Compare AVL trees and red-black trees at a high level.hard

    A plain BST's operations cost O(h), and inserting keys in sorted order produces a chain with h = n, so everything degrades to O(n). Self-balancing trees restore balance with rotations, local pointer rearrangements that preserve BST order, and guarantee O(log n) search, insert and delete.

    • AVL trees keep the heights of every node's two subtrees within 1 of each other. That strict balance keeps height close to the minimum, about 1.44 log₂ n at worst, so lookups are very fast. The price is more rebalancing work on inserts and deletes.
    • Red-black trees color nodes red or black under rules such as: a red node has no red child, and every root-to-leaf path has the same number of black nodes. Height can reach about 2 log₂ n, looser than AVL, but an insert needs at most two rotations and a delete at most three, so writes are cheaper.

    Rule of thumb: AVL for read-heavy workloads, red-black for mixed ones. Red-black trees back Java's TreeMap and are the usual implementation of C++ std::map.

    What interviewers listen for

    • Sorted inserts turn a plain BST into a chain
    • Rotations rebalance while keeping BST order
    • AVL: subtree heights differ by at most 1
    • Red-black: looser balance, cheaper updates
    • AVL for reads; red-black for mixed; TreeMap is red-black

    Likely follow-up: Walk me through a left rotation. · Why would a B-tree beat both for a database index?

    answer it out loud →
46. 46.Why does building a heap from n elements take O(n) rather than O(n log n)?hard

    Pushing elements one at a time costs O(log n) each, O(n log n) in total. Bottom-up heapify (Floyd's method) instead treats the array as a complete tree already and sifts down every non-leaf node, from the last one at index n // 2 - 1 back to the root.

    The key is that sifting down costs at most the node's height, not log n, and most nodes are near the bottom. About half the nodes are leaves and do no work, a quarter have height 1, an eighth height 2, and so on. The total is about n/4 · 1 + n/8 · 2 + n/16 · 3 + ..., which is n times the series Σ h / 2^(h+1), and that series converges to 1. So building is O(n).

    Building by sift-up gets no such benefit, because the many bottom nodes are the ones that may travel farthest.

    So heapq.heapify(list) is O(n), and top-k code often heapifies once instead of pushing in a loop. Heapsort is still O(n log n), since its n pops cost O(log n) each.

    What interviewers listen for

    • Sift down each non-leaf, from n//2 - 1 to 0
    • Sift-down costs the node height, not log n
    • Half the nodes are leaves and do no work
    • Σ h / 2^(h+1) converges, so the total is O(n)
    • heapq.heapify is O(n); heapsort is still O(n log n)

    Likely follow-up: Why is building a heap by repeated sift-up O(n log n)? · How does heapsort use an in-place max-heap?

    answer it out loud →
47. 47.In a sorted array with duplicates, how do you find the first and last positions of a target in O(log n)?mid

    Plain binary search stops at any match, so I change it to find a boundary instead of a value. The cleanest tool is a lower-bound search: the first index whose value is >= target. I use a half-open range [lo, hi) with hi = len(a). If a[mid] < target, the answer lies to the right, so lo = mid + 1; otherwise mid might be the answer, so hi = mid. The loop ends when lo == hi, which is the boundary.

    • First occurrence: the lower bound, if it is in range and holds the target.
    • Last occurrence: the first index with a value > target (the upper bound), minus one.

    Each search is O(log n), so the whole thing stays O(log n) even when every element equals the target. Finding one match and scanning outward would degrade to O(n).

    These are exactly Python's bisect_left and bisect_right, and the same template counts occurrences (upper - lower) or finds the insert position.

    def bound(a, target, upper=False):
        # first index with a[i] >= target (or a[i] > target when upper=True)
        lo, hi = 0, len(a)
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < target or (upper and a[mid] == target):
                lo = mid + 1
            else:
                hi = mid
        return lo
    
    def search_range(a, target):
        first, last = bound(a, target), bound(a, target, upper=True) - 1
        return [first, last] if first <= last else [-1, -1]

    What interviewers listen for

    • Search for a boundary, not a match
    • Half-open [lo, hi); hi = mid keeps the candidate
    • First = lower bound; last = upper bound minus one
    • Stays O(log n) even if all values are duplicates
    • Same as bisect_left and bisect_right

    Likely follow-up: How would you count the occurrences of a target? · How would you find the insert position that keeps the array sorted?

    answer it out loud →
48. 48.What does "binary search on the answer" mean? Give an example.hard

    Sometimes you do not search the array; you search the range of possible answers. It works when feasibility is monotonic: if answer x works, every larger (or every smaller) answer works too. The answers then look like no, no, no, yes, yes, and binary search finds the first yes.

    Example, Koko eating bananas: given piles and h hours (at least one hour per pile), eating at speed k per hour, one pile at a time, find the minimum k that finishes in time. Pile p takes ceil(p / k) hours, and if speed k finishes in time, any faster speed does too. So I binary search k over [1, max(piles)], and each check sums the hours in O(n). Total: O(n log M), where M is the largest pile.

    The same template solves shipping packages within D days, splitting an array into k parts to minimize the largest sum, and integer square root.

    The recipe: bound the answer space, write a feasible(x) check, confirm it is monotonic, then find the boundary with the lower-bound template.

    def min_eating_speed(piles, h):
        def hours(k):                         # total hours at speed k
            return sum((p + k - 1) // k for p in piles)
        lo, hi = 1, max(piles)
        while lo < hi:                        # smallest feasible k
            mid = (lo + hi) // 2
            if hours(mid) <= h:
                hi = mid                      # feasible: try slower
            else:
                lo = mid + 1                  # too slow: go faster
        return lo

    What interviewers listen for

    • Search the range of answers, not the array
    • Requires monotonic feasibility
    • Write a feasible(x) check, usually O(n)
    • Koko: search speed over [1, max(piles)]
    • Total O(n log M) for answer range M

    Likely follow-up: How would you split an array into k subarrays minimizing the largest sum? · How do you choose the bounds of the search range?

    answer it out loud →
49. 49.How do you find the length of the longest increasing subsequence, first in O(n²) and then in O(n log n)?hard

    A subsequence keeps order but may skip elements. The O(n²) DP: let dp[i] be the length of the longest increasing subsequence ending at index i. For every earlier j with a[j] < a[i], dp[i] = max(dp[i], dp[j] + 1). The answer is max(dp), and back-pointers can reconstruct the sequence.

    The O(n log n) method keeps tails, where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1 seen so far. tails stays sorted, so for each x I binary search for the first tail >= x. If none exists, x extends the longest subsequence and is appended; otherwise it replaces that tail, since a smaller tail leaves more room to grow. The answer is len(tails).

    Two cautions: tails is not itself a valid subsequence, only its length is meaningful; and bisect_left gives strictly increasing, while bisect_right gives non-decreasing. For [10, 9, 2, 5, 3, 7, 101, 18], the LIS length is 4, for example [2, 3, 7, 18].

    from bisect import bisect_left
    
    def length_of_lis(nums):
        tails = []        # tails[k] = smallest tail of an increasing run of length k+1
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)       # x extends the longest run
            else:
                tails[i] = x          # x is a smaller tail for length i+1
        return len(tails)

    What interviewers listen for

    • dp[i] = LIS ending at i: O(n²)
    • tails[k] = smallest tail for length k + 1
    • Binary search each element into tails
    • tails is not the actual subsequence
    • bisect_left strict; bisect_right non-decreasing

    Likely follow-up: How would you reconstruct the actual subsequence in O(n log n)? · How does LIS solve the Russian doll envelopes problem?

    answer it out loud →
50. 50.How do you compute the longest common subsequence (LCS) of two strings?mid

    Let dp[i][j] be the LCS length of the first i characters of a and the first j characters of b, with row and column 0 set to 0 for empty prefixes. Then:

    • If a[i-1] == b[j-1], that character extends a common subsequence: dp[i][j] = dp[i-1][j-1] + 1.
    • Otherwise one of the two characters goes unused: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

    The answer is dp[m][n], in O(m · n) time and space. Each row depends only on the previous one, so the length alone needs just O(min(m, n)) space. To recover the subsequence itself, keep the full table and walk back from dp[m][n], moving diagonally on matches.

    For "abcde" and "ace", the LCS is "ace", length 3.

    I clarify subsequence versus substring: a longest common substring must be contiguous, so on a mismatch its cell resets to 0 instead of taking the max. LCS underlies diff tools, and edit distance is a close relative with insert, delete and replace costs.

    What interviewers listen for

    • dp[i][j] over prefixes; row and column 0 are 0
    • Match: diagonal value plus 1
    • Mismatch: max of the top and left cells
    • O(m · n) time; rolling rows cut space
    • Substring variant resets to 0 on a mismatch

    Likely follow-up: How would you compute the edit distance between two strings? · How would you print the LCS, not just its length?

    answer it out loud →
51. 51.Explain the 0/1 knapsack problem and its DP solution. Why is it called pseudo-polynomial?hard

    Given items with weights and values and a capacity W, choose the subset with maximum total value that fits. "0/1" means each item is taken whole or not at all. Greedy by value-to-weight ratio fails here; it is only correct for the fractional version.

    Define dp[i][c] as the best value using the first i items within capacity c. For each item there are two choices: skip it (dp[i-1][c]) or, if it fits, take it (dp[i-1][c - w] + v), and I keep the max. That is O(n · W) time.

    Each row reads only the previous one, so I compress to a 1D array and iterate capacity downwards. Going down guarantees dp[c - w] still holds the previous row's value, so each item is used at most once. Iterating upwards would let an item be reused, which is exactly the unbounded knapsack.

    It is pseudo-polynomial because O(n · W) is polynomial in the numeric value W, which can be exponential in the number of bits needed to write it. The general problem is NP-hard.

    def knapsack(weights, values, capacity):
        dp = [0] * (capacity + 1)                 # dp[c] = best value within c
        for w, v in zip(weights, values):
            for c in range(capacity, w - 1, -1):  # downwards: each item once
                dp[c] = max(dp[c], dp[c - w] + v)
        return dp[capacity]

    What interviewers listen for

    • Each item is taken whole or not at all
    • Take or skip: max(dp[c], dp[c - w] + v)
    • Iterate capacity downwards so each item is used once
    • Upward iteration gives the unbounded knapsack
    • O(n · W) is pseudo-polynomial; NP-hard in general

    Likely follow-up: How would you recover which items were chosen? · How does partition equal subset sum reduce to knapsack?

    answer it out loud →
52. 52.Which bit manipulation tricks should you know for coding interviews?easy

    Beyond &, |, ^ (xor), ~ and the shifts << and >>, the tricks that come up most:

    • Check, set, clear, toggle bit i: (x >> i) & 1, x | (1 << i), x & ~(1 << i), x ^ (1 << i).
    • Clear the lowest set bit: x & (x - 1). Repeating it until zero counts set bits, and x > 0 and (x & (x - 1)) == 0 tests for a power of two.
    • Isolate the lowest set bit: x & -x, the core of Fenwick trees.
    • XOR cancels pairs: a ^ a = 0 and a ^ 0 = a, so XOR-ing every element finds the one value that appears once when all others appear twice, in O(1) space.
    • Bitmasks as sets: an integer can encode a subset of a small collection, for bitmask DP.

    Python specifics: integers never overflow, and negatives act like infinitely sign-extended two's complement, so mask with & 0xFFFFFFFF to emulate 32-bit behavior. int.bit_count() (Python 3.10+) counts set bits.

    What interviewers listen for

    • x & (x - 1) clears the lowest set bit
    • Power of two: x > 0 and (x & (x-1)) == 0
    • x & -x isolates the lowest set bit
    • XOR cancels pairs: find the single number
    • Python ints never overflow; mask to emulate 32 bits

    Likely follow-up: How would you find the two numbers that appear once when all others appear twice? · How would you count the set bits of every number from 0 to n?

    answer it out loud →
53. 53.Given a list of meeting time intervals, what is the minimum number of rooms required?mid

    The answer is the maximum number of meetings in progress at the same moment. Two standard O(n log n) approaches:

    • Min-heap of end times: sort meetings by start. For each meeting, if the earliest-ending room (the heap's root) has finished by this start, pop it to reuse that room; then push this meeting's end. The heap never shrinks, so its final size is the answer.
    • Sweep with two sorted arrays: sort all starts and all ends separately. Walk through the starts; if a start comes before the earliest end not yet used, a new room is needed, otherwise a room frees up and I advance the end pointer. The peak count is the answer.

    Both cost O(n log n) for sorting and O(n) space.

    I clarify the boundary rule: if one meeting ends at 10 and another starts at 10, they can usually share a room, so the reuse check is end <= start. The simpler variant, "can one person attend every meeting?", just sorts by start and checks that no meeting starts before the previous one ends.

    What interviewers listen for

    • Answer is the maximum simultaneous overlap
    • Min-heap of end times; reuse a room if it is free
    • Or sweep sorted starts and ends with two pointers
    • O(n log n) time, O(n) space
    • Clarify whether an end equal to a start can share

    Likely follow-up: How would you report which meeting goes in which room? · How would you solve it without sorting if times are small integers?

    answer it out loud →
54. 54.How do counting sort and radix sort achieve linear time, and when are they a good choice?hard

    Neither compares elements, so the Ω(n log n) comparison lower bound does not apply.

    Counting sort handles integer keys in a known range of size k. Count the occurrences of each key, turn the counts into prefix sums so each key knows where its block starts, then copy elements into those positions in input order, which keeps the sort stable. That is O(n + k) time and space: excellent when k is about n or smaller, hopeless when keys span a huge range like all 64-bit integers.

    Radix sort handles larger keys one digit at a time. LSD radix sort goes from the least significant digit to the most, using a stable counting sort per digit, so the order from earlier digits survives later passes. With d digits in base b, it is O(d · (n + b)), which is linear in n for fixed-width integers.

    The trade-offs: extra memory, keys must be integers or fixed-length strings, and for small or general inputs a good comparison sort often wins on constants.

    What interviewers listen for

    • No comparisons, so the n log n bound does not apply
    • Counting sort: O(n + k) for key range k
    • Prefix sums place elements stably
    • LSD radix: stable pass per digit, O(d · (n + b))
    • Needs bounded integer-like keys and extra memory

    Likely follow-up: Why must each digit pass in LSD radix sort be stable? · How would you sort a million 32-bit integers as fast as possible?

    answer it out loud →
55. 55.How would you find the maximum of every sliding window of size k in O(n) time?hard

    Brute force takes the max of each window, O(n · k). A heap with lazy removal of expired entries gives O(n log n). The optimal approach is a monotonic deque of indices whose values decrease from front to back.

    For each index i:

    • Pop from the front if that index has left the window (it is <= i - k).
    • Pop from the back while those values are <= the new value; they can never be a window maximum again, because the new element is at least as large and stays in the window longer.
    • Push i onto the back.
    • Once i >= k - 1, the front of the deque holds the current window's maximum.

    Each index is pushed and popped at most once, so the total is O(n) time and O(k) space for the deque. Storing indices rather than values is what makes the expiry check possible.

    The same structure helps DP problems where each state needs the maximum of the previous k states.

    What interviewers listen for

    • Deque of indices with decreasing values
    • Drop expired indices from the front
    • Drop smaller values from the back before pushing
    • The front is the window maximum
    • Each index pushed and popped once: O(n)

    Likely follow-up: How would you adapt it to the sliding window minimum? · Why store indices rather than values in the deque?

    answer it out loud →
56. 56.How does heapsort work, and why is quicksort usually faster in practice despite heapsort having a better worst case?mid

    Heapsort runs in two phases on the array itself:

    • Build a max-heap with bottom-up heapify, O(n).
    • Extract repeatedly: swap the root (the maximum) with the last element of the heap, shrink the heap by one, and sift the new root down, O(log n) each. After n - 1 rounds the array is sorted ascending.

    That is O(n log n) in the best, average and worst case with O(1) extra space, a stronger guarantee than quicksort's O(n²) worst case. It is not stable.

    Quicksort usually wins in practice because of cache behavior: partitioning scans memory sequentially, while sift-down jumps from index i to 2i + 1, touching memory far apart in a large heap. Heapsort also tends to do more comparisons and swaps.

    That is why introsort, the usual C++ std::sort, runs quicksort and switches to heapsort only when recursion gets too deep, combining quicksort's speed with a guaranteed O(n log n). Heapsort alone suits cases where memory is tight and worst-case time matters.

    What interviewers listen for

    • Build a max-heap in O(n)
    • Swap the root to the end, shrink, sift down
    • O(n log n) in all cases, O(1) extra space
    • Not stable, with poor cache locality
    • Introsort falls back to heapsort for bad cases

    Likely follow-up: Why does heapsort use a max-heap to sort in ascending order? · What triggers introsort to switch to heapsort?

    answer it out loud →
57. 57.What is divide and conquer, and how do you analyze its running time with the master theorem?hard

    Divide and conquer splits a problem into independent subproblems, solves them recursively, and combines the results. Merge sort, quicksort, binary search and fast multiplication algorithms all follow this shape. Unlike DP, the subproblems do not overlap, so there is nothing to cache.

    The running time usually looks like T(n) = a · T(n / b) + f(n): a subproblems of size n / b, plus f(n) to split and combine. The master theorem compares f(n) with n^(log_b a), the total work at the leaves:

    • If f(n) grows polynomially slower, the leaves dominate: Θ(n^(log_b a)).
    • If they match, every level does equal work: Θ(n^(log_b a) · log n).
    • If f(n) grows polynomially faster (and meets a regularity condition), the root dominates: Θ(f(n)).

    Examples: merge sort, 2T(n/2) + n, is Θ(n log n); binary search, T(n/2) + 1, is Θ(log n); Karatsuba, 3T(n/2) + n, is about Θ(n^1.585). Recurrences like T(n - 1) + n do not fit the form, so I sum them directly or draw a recursion tree.

    What interviewers listen for

    • Split into independent subproblems, recurse, combine
    • Recurrence T(n) = a · T(n/b) + f(n)
    • Compare f(n) with n^(log_b a)
    • Merge sort Θ(n log n); binary search Θ(log n)
    • Other recurrences: sum directly or use a recursion tree

    Likely follow-up: What is the complexity of T(n) = 2T(n/2) + n²? · How does the recurrence explain quicksort's O(n²) worst case?

    answer it out loud →

No questions match that filter.

Prefer multiple choice? All 27 Data Structures & Algorithms MCQs with answers →