Top 20 Data Structures Career Questions

# Two-sum — the trade-off that interviewers want to hear.
# Both solutions are correct. Only one explains the trade-off.

def two_sum_brute(nums, target):
    """O(n^2) time, O(1) space — sort-free, but slow."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum_hash(nums, target):
    """O(n) time, O(n) space — the standard interview answer."""
    seen = {}  # value -> index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

# What the interviewer wants to hear:
#
# "There are two standard approaches. The brute force is O(n^2)
#  time and O(1) space. The hash map is O(n) time and O(n)
#  space. In an interview, I would use the hash map by default
#  because n is usually large enough that O(n^2) becomes
#  unacceptable. But if I knew the array was small and the
#  memory budget was tight, I could use the brute force."
#
# The candidate who says this is more hireable than one who
# just writes the O(n) solution silently. The trade-off IS
# the answer.
#
# Bonus point: "I could also sort and use two pointers — that
# is O(n log n) time and O(1) space, which is a middle ground
# when memory is tight but n is not enormous."

# Longest substring without repeating characters
# The classic sliding window problem.

def length_of_longest_substring(s):
    seen = {}
    left = 0
    best = 0

    for right, ch in enumerate(s):
        # If we have seen ch before, and the previous
        # occurrence is inside the current window, move left.
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1

        seen[ch] = right
        best = max(best, right - left + 1)

    return best

# Test:
# "abcabcbb" -> 3 ("abc")
# "bbbbb"    -> 1 ("b")
# "pwwkew"   -> 3 ("wke")
# ""         -> 0

# What this tests:
# - Sliding window reasoning (expand right, contract left)
# - When to update the left pointer (only when the duplicate
#   is inside the current window)
# - What to store in the map (last seen index, not just a boolean)
#
# The mistake most candidates make:
# - They use a set instead of a map. Then they cannot tell
#   WHEN the previous occurrence was, so they cannot correctly
#   decide whether to move left.
#
# The right answer uses a hash map of char -> last index.
# That lets the algorithm update left precisely.

# What to say in the interview:
# "This is a sliding window. I expand right one character at a
#  time. I keep a map of char to the last index I saw it at.
#  If the current char appeared inside the current window, I
#  move left to just after that previous occurrence. The window
#  size at any point is a candidate answer. Total time is O(n),
#  space is O(min(n, alphabet))."

# Maximum subarray — Kadane's algorithm.
# The problem: find the contiguous subarray with the largest sum.

def max_subarray(nums):
    if not nums:
        return 0

    current = best = nums[0]

    for n in nums[1:]:
        # Either extend the running sum, or start fresh at n.
        current = max(n, current + n)
        best = max(best, current)

    return best

# Test:
# [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> 6 (subarray [4, -1, 2, 1])
# [1]                            -> 1
# [-5, -2, -8]                   -> -2
# []                             -> 0

# Why this is subtle:
# - If all values are negative, the answer is the largest
#   single element, not zero. That is why we initialise
#   current and best to nums[0], not 0.
#
# - The core intuition: "at each index, the best subarray
#   ending here is either the current element alone, or the
#   previous best subarray ending here plus the current element."
#
# What to say in the interview:
# "This is dynamic programming. Let current[i] be the maximum
#  subarray sum ending at index i. Then current[i] = max(nums[i],
#  current[i-1] + nums[i]). The overall best is the maximum
#  of current[0..i]. Time is O(n), space is O(1) because we only
#  keep the previous value.
#
#  The edge case that trips people up: all-negative arrays.
#  The algorithm still works as long as we seed with nums[0],
#  not 0, because starting from 0 would incorrectly 'reset' to
#  a sum of zero."

# Validate a Binary Search Tree — the trap and the fix.
# Most candidates get this wrong on the first try.

# ── WRONG (a common first attempt) ──
def is_bst_wrong(node):
    if node is None:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_bst_wrong(node.left) and is_bst_wrong(node.right)

# Why it is wrong: it only checks that each child is less/greater
# than its immediate parent. It does not enforce the BST property
# globally. Counter-example:
#         5
#        / \
#       1   7
#          / \
#         4   8
# The tree above passes the local check (4 < 7) but is NOT a BST
# because 4 < 5, and 4 is in the right subtree of 5.

# ── RIGHT — pass ranges down ──
def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True

    if not (low < node.val < high):
        return False

    return (
        is_bst(node.left, low, node.val) and
        is_bst(node.right, node.val, high)
    )

# What the interviewer wants to hear:
# "The BST property is global, not local. Each node must be
#  greater than every ancestor from the left chain, and less
#  than every ancestor from the right chain. I enforce this by
#  passing a valid range down the recursion. The range for
#  the left subtree is (low, node.val); the range for the
#  right subtree is (node.val, high). Time is O(n), space is
#  O(h) for the recursion stack."

# Level-order traversal — a queue-based BFS.
# What interviewers ask for after the standard tree questions.

from collections import deque

def level_order(root):
    if root is None:
        return []

    result = []
    q = deque([root])

    while q:
        level = []
        # Capture the size of the current level NOW, because
        # the queue will grow as we append children.
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)

    return result

# What this tests:
# - Do you know to use a queue (FIFO), not a stack (LIFO)?
# - Do you know to capture len(q) at the START of the level,
#   not check `while q` inside the level loop?
# - Do you know when BFS is more appropriate than DFS?
#
# The trap:
# If you write `for node in q:` instead of
# `for _ in range(len(q)):`, you will keep processing nodes
# you append during the same level. The level boundaries
# blur and the output is wrong.
#
# What to say in the interview:
# "This is BFS. I use a queue. The key detail is capturing
#  the current level's size before iterating, because I add
#  children to the same queue. That way I process exactly
#  one level per outer-loop iteration."

# Number of islands — the graph problem disguised as a grid.
# Interviewers love this because it tests DFS/BFS on a 2D grid.

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if (
            r < 0 or r >= rows or
            c < 0 or c >= cols or
            grid[r][c] != "1"
        ):
            return
        # Mark visited by mutating the grid
        grid[r][c] = "0"
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)

    return count

# Test:
# [["1","1","0","0","0"],
#  ["1","1","0","0","0"],
#  ["0","0","1","0","0"],
#  ["0","0","0","1","1"]] -> 3

# What this tests:
# - Translating a grid into a graph (4-directional neighbours)
# - DFS with boundary checks
# - Visited tracking (here, mutating the grid)
# - Counting connected components
#
# What to say in the interview:
# "I treat each cell as a node in a graph, with edges to its
#  four adjacent cells. I iterate over every cell. When I find
#  an unvisited land cell, I increment the count and do a DFS
#  from there, marking every reachable land cell as visited.
#  Time is O(rows * cols), space is O(rows * cols) in the worst
#  case for the recursion stack.
#
#  If the interviewer asks for BFS instead, I swap the DFS for
#  a queue — the logic is the same."

# K-th largest element — three approaches, three trade-offs.
# The interviewer is not just checking if you can code.
# They are checking if you know when to pick which approach.

import heapq

# ── 1. Sort and index ──
def kth_largest_sort(nums, k):
    nums_sorted = sorted(nums, reverse=True)
    return nums_sorted[k - 1]

# Time:  O(n log n) — sorting dominates
# Space: O(n) — for the sorted copy
# When:  When you need to run this on the same data repeatedly,
#        or when n is small. Simple and predictable.

# ── 2. Min-heap of size k ──
def kth_largest_heap(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)  # O(k)
    for n in nums[k:]:
        if n > heap[0]:
            heapq.heapreplace(heap, n)  # O(log k)
    return heap[0]

# Time:  O(n log k) — faster than sort when k << n
# Space: O(k) — only k elements in memory
# When:  Streaming data, or when k is small and n is large.
#        This is the streaming-friendly answer.

# ── 3. Quickselect ──
def kth_largest_quickselect(nums, k):
    import random
    target = len(nums) - k  # index in sorted ascending
    a = nums[:]
    left, right = 0, len(a) - 1
    while True:
        pivot_idx = random.randint(left, right)
        a[pivot_idx], a[right] = a[right], a[pivot_idx]
        pivot = a[right]
        p = left
        for i in range(left, right):
            if a[i] < pivot:
                a[p], a[i] = a[i], a[p]
                p += 1
        a[p], a[right] = a[right], a[p]
        if p == target:
            return a[p]
        elif p < target:
            left = p + 1
        else:
            right = p - 1

# Time:  O(n) average, O(n^2) worst case
# Space: O(1) — in-place partitioning
# When:  When you need average-linear time on unsorted data
#        and can tolerate worst-case risk.

# What the interviewer wants to hear:
# "There are three common approaches. Sorting is O(n log n) and
#  simple. A min-heap of size k is O(n log k), which is better
#  when k is small and the data is streamed. Quickselect is
#  O(n) on average but O(n^2) in the worst case, so it is best
#  when you control the input distribution or can randomise.
#
#  For a one-shot query on unsorted data with moderate k, the
#  heap is usually the right answer. For streaming data, the
#  heap is the only one that works. For memory-constrained
#  scenarios, quickselect has the smallest footprint."

# HashMap — the worst case interviewers actually ask about.

# A hash map works by:
#   1. Hashing the key -> an integer
#   2. Mapping the integer to a bucket index (usually modulo)
#   3. Storing the value in that bucket

# ── Average case: O(1) ──
#   With a good hash function and load factor under control,
#   each bucket holds roughly one item. Lookup is nearly
#   constant time.

# ── Worst case: O(n) ──
#   If many keys hash to the same bucket, that bucket holds
#   a list of items and lookup becomes linear in the number
#   of collisions. Two scenarios cause this:
#
#   1. Poor hash function — e.g., every key hashes to the
#      same value. Every operation becomes O(n).
#
#   2. Hash flooding attack — an attacker deliberately sends
#      keys that all hash to the same bucket, forcing O(n)
#      operations per request. This is a real DoS vector.
#
# What the interviewer wants to hear:
# "Hash maps are O(1) on average because the hash function
#  distributes keys across buckets. But if many keys collide
#  in the same bucket, or if a malicious client engineers
#  collisions, lookups become O(n). Modern languages mitigate
#  this in different ways: Java 8+ converts heavily-collided
#  buckets to red-black trees (O(log n) per operation), Python
#  randomises string hashing to prevent flooding attacks, and
#  Go uses a similar randomisation strategy."
#
# This is the kind of answer that separates "I memorised the
# complexity table" from "I understand the data structure."

# Amortised complexity — why "O(1) append" is not the whole story.

# A dynamic array (Python's list, Java's ArrayList, C++'s vector)
# supports O(1) append *on average* — this is called amortised
# analysis.

# The reason:
# - When the array is full, appending triggers a resize:
#   allocate a new (usually double-sized) buffer and copy
#   every element over. That single append costs O(n).
#
# - But that cost is paid once every n appends.
#   Over n appends, the total cost is:
#       n + n/2 + n/4 + ... = O(n)
#   So the *average* cost per append is O(1).

# ── What to say in an interview ──
# "Appending to a dynamic array is O(1) amortised, not O(1)
#  worst case. Every resize doubles the buffer and copies
#  existing elements, so any individual append can be O(n).
#  But because the resize happens only every n / factor
#  appends, the average is O(1). This is why we call it
#  amortised — the cost is spread over many operations.
#
#  If the interviewer asks about worst-case guarantees,
#  I would mention that a linked list gives O(1) insert per
#  operation but loses cache locality, and that some
#  implementations (like Go slices) pre-allocate to trade
#  memory for predictable latency."

# ── The bigger picture ──
# Most interview questions about complexity reward candidates
# who distinguish:
#   - best case vs worst case
#   - average case vs amortised
#   - theoretical complexity vs real-world latency
#
# "It is O(1)" is the beginning of a good answer, not the end.