43 Data Structures and Algorithms Interview Questions and Answers

Short answer: Big O describes how an algorithm's running time or memory usage grows as the input size n increases, dropping constants and lower-order terms. It's an upper bound on the growth rate.

In detail:

Big O answers the question "what happens when n becomes very large?". We're not interested in the exact number of operations, only the nature of the growth. That's why O(2n + 100) simplifies to O(n), and O(3n² + n) — to O(n²).

The main growth classes (from best to worst):

# O(1) — constant: doesn't depend on n
def first(arr):
    return arr[0] if arr else None

# O(log n) — logarithmic: each step halves the problem (binary search)
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# O(n) — linear: a single pass
def total(arr):
    s = 0
    for x in arr:        # n iterations
        s += x
    return s

# O(n log n) — efficient sorts (merge, quick, Timsort)
def sort_it(arr):
    return sorted(arr)

# O(n^2) — quadratic: a nested loop
def has_dup_naive(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# O(2^n) — exponential: naive Fibonacci, enumerating subsets
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

A rough guide to growth at n = 1,000,000: O(1) — 1 operation, O(log n) — ~20, O(n) — a million, O(n log n) — ~20 million, O(n²) — a trillion (already too much), O(2^n) — infeasible even at n = 50.

⚠️ Gotcha: Big O is about asymptotics (behavior at large n), not about actual time. An O(n) algorithm can be slower than an O(n²) one on small data because of large constants. People also confuse: Big O (upper bound), Ω (lower bound), Θ (tight bound); in interviews "O" usually means Θ.

Short answer: Time complexity — how time (the number of operations) grows; space complexity — how the extra memory the algorithm uses beyond the input grows.

In detail:

These two metrics are evaluated independently, and there's often a trade-off between them (time-space tradeoff): you can speed things up at the cost of memory and vice versa.

# Time O(n), Space O(1) — count in place, no extra memory
def sum_inplace(arr):
    s = 0
    for x in arr:
        s += x
    return s

# Time O(n), Space O(n) — cache seen elements for fast lookup
def has_dup_fast(arr):
    seen = set()          # extra memory grows with n -> O(n)
    for x in arr:
        if x in seen:     # lookup in a set is O(1)
            return True
        seen.add(x)
    return False

In the second example we sacrificed memory (a set of n elements) to get O(n) time instead of the O(n²) of a naive brute force. This is the classic tradeoff.

For recursion, space usually includes the depth of the call stack: a recursive tree traversal is O(h) memory, where h is the height.

⚠️ Gotcha: the input data usually does not count toward space complexity — only additional memory counts. People also often forget about the recursion stack: an "iterative" algorithm with O(1) extra memory becomes O(n) memory once rewritten as recursion.

Short answer: Amortized complexity is the average worst-case cost of an operation, averaged over a long sequence of operations. An individual operation can be expensive, but "on average" it's cheap.

In detail:

The classic example is list.append() in Python. Usually it's O(1), but occasionally the array overflows and a new block of memory has to be allocated and everything copied → O(n). However, these expansions happen rarely (the size grows multiplicatively), so amortized, append is O(1).

# n append operations
lst = []
for i in range(n):
    lst.append(i)   # each averages O(1), though the rare ones are O(n)
# total O(n), not O(n^2)

The logic: if the array grows each time by, say, ~1.125x (CPython), then the total cost of all the copies over n insertions is O(n). Divide by n operations → O(1) per operation.

⚠️ Gotcha: amortized O(1) ≠ guaranteed O(1). If predictable latency matters (real-time systems), an individual append can "stall" at O(n). Don't confuse amortized complexity with the average case — these are different concepts: the average case is about the distribution of inputs, amortization is about a sequence of operations.

Short answer: These are complexity estimates for different inputs: best case — the most favorable input, worst case — the least favorable, average case — averaged over a typical distribution. In interviews and production you usually focus on worst and average.

In detail:

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

For linear search:

• Best case O(1) — the element is at the start.
• Worst case O(n) — the element is absent or at the end.
• Average case O(n) — on average we go through half, but that's still O(n).

A vivid example of divergence is quick sort: average case O(n log n), but worst case O(n²) with a poor choice of pivot (for example, an already-sorted array with pivot = the first element).

⚠️ Gotcha: when designing systems, plan for the worst case, especially if the input can be controlled by an attacker (Hash DoS attacks exploit the worst case of hash tables, forcing all keys to collide → O(n)).

Short answer: Big O lets you predict how code will behave as data grows and choose a structure/algorithm up front that won't "hit a wall" on performance. Constants matter more for small and fixed n.

In detail:

In practice Big O saves you from situations like "it worked on 100 records, fell over on 10 million." Example: checking membership in a list is O(n), in a set/dict it's O(1). On large data, replacing a list with a set for membership checks gives a multiple speedup.

# BAD: O(n*m) — for each of the n queries, a linear search through the list
allowed_list = [...]              # m elements
result = [q for q in queries if q in allowed_list]

# GOOD: O(n) — lookup in a set is amortized O(1)
allowed = set(allowed_list)
result = [q for q in queries if q in allowed]

When constants matter more than asymptotics:

• n is small and fixed (for example, always ≤ 10) — a simple O(n²) can be faster and more readable than a "clever" O(n log n).
• The hidden constants are large: an algorithm with better asymptotics may have huge overhead (complex data structures, cache misses).
• A linear pass over a contiguous array is often faster than a "theoretically better" traversal of a linked structure because of CPU cache locality.

⚠️ Gotcha: premature optimization by Big O without profiling. First measure where the real bottleneck is — sometimes an O(n²) over 50 elements isn't worth your attention, while an O(n) DB query inside a loop kills everything.

Short answer: A Python list is a dynamic array: a contiguous block of memory with pointers to objects. Indexed access is O(1) because the element's address is computed arithmetically: base + index * size.

In detail:

arr = [10, 20, 30, 40]
arr[2]          # O(1): we compute the address directly, no scanning
arr[-1]         # O(1): len-1
arr.append(5)   # amortized O(1) — appending to the end
arr.pop()       # O(1) — removing from the end
arr.insert(0, 99)  # O(n)! shifting all elements to the right
arr.pop(0)         # O(n)! shifting all elements to the left
99 in arr          # O(n) — linear search

List complexities:

• Indexed access/assignment — O(1).
• append/pop from the end — amortized O(1).
• insert/pop at the start or middle — O(n) (shifting elements).
• Search (in, index) — O(n).

⚠️ Gotcha: list.pop(0) and list.insert(0, x) are O(n), not O(1). If you need frequent operations at both ends — use collections.deque (O(1) at both ends).

Short answer: When the array fills up, a new, larger block of memory is allocated (multiplicative growth) and the elements are copied. Since expansions are rare, the average cost of append is O(1).

In detail:

CPython stores the current size (ob_size) and the allocated capacity (allocated) for a list. As long as size < allocated, append simply writes the element — O(1). When space runs out, the capacity is increased by roughly the formula new = size + (size >> 3) + 6 (growth of ~12.5%), and copying happens — O(n).

Why amortized O(1): the total cost of all the copies over n insertions forms a geometric series and sums to O(n). Divide by n operations → O(1) per one.

import sys
lst = []
prev = -1
for i in range(20):
    lst.append(i)
    cap = sys.getsizeof(lst)   # the stepwise capacity growth is visible
    if cap != prev:
        print(len(lst), cap)
        prev = cap

If the size is known in advance, it's more efficient to allocate up front: a list comprehension or [None] * n avoid intermediate reallocations.

⚠️ Gotcha: don't confuse amortized O(1) with the idea that an individual append is always cheap — when it hits an expansion it's O(n). Also: growth is multiplicative (by a factor), not by a constant — otherwise append would become amortized O(n).

Short answer: A linked list stores elements as nodes, each referencing the next one (singly) or the next and the previous (doubly). Insertion/removal at a known node is O(1), but indexed access and search are O(n).

In detail:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None      # singly: forward only
        # self.prev = None    # doubly: + backward

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, val):     # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node

    def find(self, val):           # O(n)
        cur = self.head
        while cur:
            if cur.val == val:
                return cur
            cur = cur.next
        return None

Complexities:

• Insertion/removal at the head — O(1).
• Insertion/removal given a reference to the node — O(1) (for removal in a singly list you need the previous node, in a doubly list you don't).
• Indexed access to index k — O(n) (no address arithmetic, we follow references).
• Search — O(n).

Singly vs doubly: a doubly linked list lets you go in both directions and remove a node in O(1) given a reference, but it spends extra memory on the prev pointer.

⚠️ Gotcha: in Python a linked list is almost never needed — the built-in list (dynamic array) and deque (a doubly linked list under the hood) cover your needs. Linked lists are asked about as an algorithms topic (reversal, cycle detection). Also: a linked list has poor cache locality — the nodes are scattered in memory.

Short answer: An array — when you need fast indexed access and good memory locality. A linked list — when you frequently insert/remove in the middle/at the start and have a reference to the node.

In detail:

In practice in Python list or deque almost always wins, because:

• indexed access is needed more often than it seems;
• contiguous memory gives a huge win thanks to the CPU cache;
• the constants for an array are smaller.

A linked list is justified when you need O(1) insertions/removals at an arbitrary position given an existing reference (for example, an LRU cache — OrderedDict or a doubly linked list).

⚠️ Gotcha: "a linked list is better for insertions" — that's only true if you already have a reference to the right node. If you still have to find the position, then the O(n) search eats up the advantage, and an array often turns out to be faster in practice.

Short answer: A stack is LIFO (last in, first out), a queue is FIFO (first in, first out). A deque is a double-ended queue. In Python everything is implemented via collections.deque in O(1).

In detail:

from collections import deque

# STACK (LIFO): push/pop from one end
stack = []
stack.append(1)      # push, O(1)
stack.append(2)
stack.pop()          # -> 2, O(1)
# a list works fine for a stack: append/pop from the end are cheap

# QUEUE (FIFO): add to the end, take from the front
queue = deque()
queue.append(1)      # enqueue, O(1)
queue.append(2)
queue.popleft()      # -> 1, O(1)
# DON'T use a list: list.pop(0) -> O(n)!

# DEQUE (double-ended queue): O(1) at both ends
dq = deque()
dq.appendleft(0)     # O(1)
dq.append(1)         # O(1)
dq.popleft(); dq.pop()

Uses:

• Stack: DFS traversal, undoing operations (undo), evaluating expressions, checking brackets, the function call stack.
• Queue: BFS traversal, task schedulers, buffers, processing events in order of arrival.
• Deque: sliding window maximum, a queue with two ends.

⚠️ Gotcha: for a queue don't use a list with pop(0) — that's O(n) per operation, and a queue of n elements becomes O(n²). Always collections.deque. For a thread-safe queue between threads — queue.Queue.

Short answer: A hash map stores key-value pairs in an array of "buckets." The hash function turns a key into a bucket index. When two keys produce the same index — that's a collision, resolved by chaining or open addressing.

In detail:

The key-lookup algorithm:

1. Compute hash(key) — an integer.
2. Reduce it to an index: index = hash(key) % capacity.
3. Go to bucket index, find the exact key match.

Collision resolution:

• Chaining: each bucket holds a list of elements with the same index. Search within a bucket is linear.
• Open addressing: on a collision we look for the next free slot according to a probing rule. CPython's dict uses precisely open addressing.

Load factor = (number of elements) / (number of buckets). When it exceeds a threshold (~2/3 in CPython), the table is rehashed — a larger array is allocated and all elements are redistributed. This keeps collisions rare.

d = {}
d["apple"] = 1       # insertion, amortized O(1)
d["apple"]           # access, O(1) avg.
"apple" in d         # check, O(1) avg.
del d["apple"]       # deletion, O(1) avg.

# The key must be hashable (immutable)
d[(1, 2)] = "ok"     # a tuple — allowed
# d[[1, 2]] = "no"   # TypeError: list is not hashable

⚠️ Gotcha: dict keys must be hashable (have __hash__, usually immutable types). list, dict, set can't be used as keys; a tuple can (if it contains only hashable items). If you override __eq__, you must consistently override __hash__.

Short answer: O(1) because the hash function gives a direct bucket address without scanning. It degrades to O(n) when a set of keys produces identical hashes (collisions) and the lookup turns into a linear scan.

In detail:

In the average case, with a good hash function and a controlled load factor, access/insertion/deletion are O(1). The hash spreads keys evenly across buckets, and there are few of them in each.

Degradation to O(n) in the worst case:

• All keys collide (land in one bucket/chain) → the lookup is linear.
• This can be induced deliberately (Hash DoS): pick inputs with the same hash. That's why, since version 3.3, Python enables randomization of string hashes (PYTHONHASHSEED).

# A bad (artificial) hash function -> everything in one bucket
class BadKey:
    def __init__(self, v): self.v = v
    def __hash__(self): return 1          # EVERYTHING collides!
    def __eq__(self, o): return self.v == o.v
# a dict of such keys degenerates to O(n) per operation

In reality, with built-in types (int, str, tuple) the hash is good, and dict is consistently O(1).

⚠️ Gotcha: "dict is always O(1)" — that's imprecise. It's the average/amortized case. Rehashing on growth is a rare O(n) operation (it amortizes). The worst case with pathological collisions is O(n).

Short answer: A set is an unordered collection of unique hashable elements, implemented as a hash map without values. It gives O(1) membership checks, insertion, and removal.

In detail:

s = {1, 2, 3}
s.add(4)         # O(1) avg.
s.discard(2)     # O(1) avg., no error if absent
3 in s           # O(1) avg. — the main benefit of a set!

# Set operations
a, b = {1, 2, 3}, {2, 3, 4}
a & b            # intersection -> {2, 3}
a | b            # union        -> {1, 2, 3, 4}
a - b            # difference   -> {1}
a ^ b            # symmetric difference -> {1, 4}

# Deduplication in O(n)
unique = list(set([1, 1, 2, 3, 3]))

Uses: removing duplicates, a fast "have we seen it already" check, set operations, tracking visited vertices in a graph.

⚠️ Gotcha: a set does not preserve order and isn't indexable (s[0] is an error). If you need a unique collection that preserves insertion order — use dict.fromkeys(...) (a dict has preserved order since Python 3.7) or list(dict.fromkeys(items)).

Short answer: A binary tree is a structure where each node has at most two children. A BST (binary search tree) is a binary tree with an invariant: left subtree < node < right subtree, which gives O(log n) search in the balanced case.

In detail:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bst_insert(root, val):           # O(h), h = height
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root

def bst_search(root, val):           # O(h)
    while root:
        if val == root.val:
            return root
        root = root.left if val < root.val else root.right
    return None

In a balanced BST the height is h ≈ log n, so search/insertion/deletion are O(log n). In a degenerate case (inserting sorted data) the tree turns into a "list," h = n, and operations become O(n).

⚠️ Gotcha: an ordinary BST is not self-balancing. Inserting an already-sorted sequence (1, 2, 3, 4...) gives a degenerate tree with O(n). To guarantee O(log n) you need self-balancing trees (AVL, red-black).

Short answer: DFS traversals (in/pre/post-order) go deep and differ in when the node is processed. BFS traverses by levels, left to right. For a BST, in-order produces a sorted order.

In detail:

from collections import deque

# DFS — recursion (the call stack)
def preorder(node):    # node -> left -> right
    if not node: return
    print(node.val); preorder(node.left); preorder(node.right)

def inorder(node):     # left -> node -> right  (for a BST = sorted!)
    if not node: return
    inorder(node.left); print(node.val); inorder(node.right)

def postorder(node):   # left -> right -> node  (deleting a tree, expressions)
    if not node: return
    postorder(node.left); postorder(node.right); print(node.val)

# BFS — by levels, via a queue
def bfs(root):
    if not root: return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

All traversals are O(n) in time (we visit every node). Memory: DFS — O(h) (the stack), BFS — O(w) (the width of a level, in the worst case O(n)).

Uses: in-order — sorted output of a BST; pre-order — copying/serializing a tree; post-order — deleting nodes, evaluating expressions; BFS — finding the shortest path by number of edges, level-order traversal.

⚠️ Gotcha: deep DFS recursion can overflow the stack (Python's limit is ~1000). For very deep trees, use an iterative DFS with an explicit stack or raise sys.setrecursionlimit.

Short answer: Self-balancing BSTs automatically maintain a height of O(log n) on inserts/deletes via rotations. AVL trees are strictly balanced (faster lookups), red-black trees are more loosely balanced (faster inserts).

In depth:

The problem with a plain BST is that it degenerates into a list when the insertion order is unlucky. Balanced trees solve this by restructuring themselves:

• AVL tree: the invariant is that the height difference of each node's subtrees is ≤ 1. After an insert/delete, rotations are performed to restore balance. Tightly balanced → fast lookups, but more rotations on modifications.
• Red-black tree: nodes are colored red/black, and a set of rules guarantees a height of ≤ 2 log n. Less strict balance → fewer rotations on insert/delete, which is why it's used where there are many modifications (e.g., in the map/set implementations in C++ STL, Java's TreeMap).

All operations (lookup, insert, delete) are guaranteed O(log n).

# Python has no built-in balanced tree.
# If you need a sorted structure with O(log n) — sortedcontainers:
from sortedcontainers import SortedList
sl = SortedList([5, 1, 3])
sl.add(2)            # O(log n) order maintenance
sl.bisect_left(3)    # O(log n) position lookup

⚠️ Gotcha: Python has no built-in balanced tree, and in interviews they often expect you to use a dict/set (hash, O(1)) or heapq (heap) instead of a "tree." Balanced trees are needed when you require ordering (range queries, nearest smaller/larger), which a hash doesn't give you.

Short answer: A heap is a binary tree stored in an array where the parent ≤ its children (min-heap) or ≥ (max-heap). It gives O(1) access to the min/max and O(log n) insert/extract. It implements a priority queue.

In depth:

import heapq

# heapq implements a MIN-heap on a regular list
h = []
heapq.heappush(h, 5)      # O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h)          # -> 1, extract the minimum, O(log n)
h[0]                      # -> minimum without extracting, O(1)
heapq.heapify(arr)        # build a heap from a list, O(n)!

# MAX-heap: store negations
heapq.heappush(h, -val)
-heapq.heappop(h)

Complexities: building a heap from an array is O(n) (not O(n log n)!), push/pop is O(log n), peeking the minimum is O(1).

Use case — Top K in O(n log k) instead of a full sort O(n log n):

# K largest elements
def top_k(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)        # min-heap of size k
        if len(h) > k:
            heapq.heappop(h)        # drop the smallest
    return h
# Or simply: heapq.nlargest(k, nums)

Other uses: Dijkstra's algorithm, merging k sorted lists, a priority-based task scheduler, the median of a stream (two heaps).

⚠️ Gotcha: heapq is min-heap only; for a max-heap, invert the signs. When storing tuples (priority, item), Python compares by the second element when priorities are equal — if item is not comparable, you'll get a TypeError; add a unique counter: (priority, counter, item).

Short answer: A trie is a tree where each path from the root encodes a string and nodes correspond to prefixes. Searching/inserting a word is O(L), where L is the word length, independent of the number of words.

In depth:

class TrieNode:
    def __init__(self):
        self.children = {}      # character -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):              # O(L)
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):              # O(L)
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):       # O(L)
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Uses: autocomplete, spell checking, prefix search, T9, IP routing. The advantage over a hash table is efficient prefix queries and ordered traversal.

⚠️ Gotcha: a trie can take a lot of memory (a node per character). If you only need exact matches without prefix queries, a set/dict is simpler and more compact.

Short answer: An adjacency matrix is a 2D V×V array, giving a fast O(1) edge check but using O(V²) memory. An adjacency list stores a list of neighbors for each vertex, uses O(V+E) memory, and is efficient for sparse graphs.

In depth:

# Adjacency list (most common) — O(V + E) memory
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [],
}
# for a weighted graph: 0: [(1, 5), (2, 3)]  # (neighbor, weight)

# Adjacency matrix — O(V^2) memory
V = 4
matrix = [[0] * V for _ in range(V)]
matrix[0][1] = 1        # edge 0->1
# edge check matrix[u][v] -> O(1)

⚠️ Gotcha: for sparse graphs (few edges, E << V²), it's almost always an adjacency list. A matrix is justified for dense graphs or when you need very frequent "is there an edge" checks. Directed graph: u->v doesn't imply v->u; for an undirected graph, add the edge in both directions.

Short answer: BFS traverses breadth-first via a queue (finds the shortest path by number of edges), DFS goes depth-first via a stack/recursion. Both are O(V+E). A cycle is found by tracking vertex states.

In depth:

from collections import deque

def bfs(graph, start):                    # O(V + E)
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)           # mark BEFORE enqueuing!
                q.append(nb)
    return visited

def dfs(graph, start, visited=None):      # O(V + E)
    if visited is None:
        visited = set()
    visited.add(start)
    for nb in graph[start]:
        if nb not in visited:
            dfs(graph, nb, visited)
    return visited

# Cycle detection in a DIRECTED graph (three colors)
def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}
    def dfs(v):
        color[v] = GRAY                   # currently being processed
        for nb in graph[v]:
            if color[nb] == GRAY:         # edge to a "gray" node -> cycle
                return True
            if color[nb] == WHITE and dfs(nb):
                return True
        color[v] = BLACK                  # fully processed
        return False
    return any(color[v] == WHITE and dfs(v) for v in graph)

Key difference: BFS guarantees the shortest path in an unweighted graph; DFS is convenient for topological sort, finding connected components, and cycle detection. For an undirected graph, a cycle is simpler: during DFS you reach an already-visited vertex that isn't the parent.

⚠️ Gotcha: in BFS, mark a vertex as visited when adding it to the queue, not when extracting it — otherwise the same vertex ends up in the queue many times. For a weighted graph, the shortest path is Dijkstra (heapq), not plain BFS.

Short answer: Simple ones (bubble, selection, insertion) are O(n²), suitable for small/nearly-sorted data. Efficient ones (merge, quick, heap) are O(n log n). They differ in stability and memory.

In depth:

# Insertion sort — O(n^2), but O(n) on nearly-sorted data, stable
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key, j = arr[i], i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Selection sort — always O(n^2), unstable, O(1) memory
def selection_sort(arr):
    for i in range(len(arr)):
        m = min(range(i, len(arr)), key=lambda k: arr[k])
        arr[i], arr[m] = arr[m], arr[i]
    return arr

A stable sort preserves the relative order of equal elements — important for multi-level sorting.

⚠️ Gotcha: "O(n²) sorts are useless" is wrong. Insertion sort is faster on small n (which is why Timsort uses it on small blocks) and is O(n) on nearly-sorted data. Selection sort minimizes the number of swaps.

Short answer: Merge sort is stable, guaranteed O(n log n), but uses O(n) extra memory. Quick sort is in-place (O(log n) stack), fast in practice, but has a worst case of O(n²) and is unstable.

In depth:

# MERGE SORT: divide (in half) and conquer (merge)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # merging two sorted halves — O(n)
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= -> stability
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res

# QUICK SORT: pick a pivot, partition, recurse
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

• Merge sort: always O(n log n), stable, predictable. Downside — O(n) memory. Good for linked lists and external sorting (data doesn't fit in memory).
• Quick sort: O(n log n) on average with small constants (faster than merge in practice), in-place. Downside — worst case O(n²) with a bad pivot (minimized by random selection or "median of three"), unstable.

⚠️ Gotcha: quick sort's worst case O(n²) arises on an already-sorted array if the pivot is an extreme element. In an interview, mention pivot randomization. The naive implementation above creates new lists (O(n) memory) — a real quick sort partitions in-place.

Short answer: Timsort is a hybrid algorithm (merge + insertion sort) used in sorted() and list.sort(). It's O(n log n) in the worst case, O(n) on nearly-sorted data, and stable.

In depth:

Timsort finds already-sorted segments ("runs"), extends them with insertion sort if needed, then merges them as in merge sort. This gives a huge win on real data, which is often partially ordered.

sorted([3, 1, 2])                 # -> [1, 2, 3], O(n log n), stable
sorted(words, key=len)            # sort by key
sorted(data, key=lambda x: (x.age, x.name))   # multi-level
sorted(arr, reverse=True)         # descending
arr.sort()                        # in-place, saves memory

Properties: stable (preserves the order of equal elements), adaptive (O(n) on sorted data), O(n) extra memory.

⚠️ Gotcha: list.sort() sorts in place and returns None; sorted() returns a new list. A common mistake: x = mylist.sort() → x will be None. Timsort's stability lets you sort by several keys sequentially (but it's more efficient with a single tuple key).

Short answer: Linear search scans all elements — O(n), works on any data. Binary search halves the range — O(log n), but requires a sorted array.

In depth:

def linear_search(arr, target):       # O(n), any data
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

import bisect
arr = [1, 3, 5, 7, 9]
i = bisect.bisect_left(arr, 5)        # O(log n), position of 5 -> 2
found = i < len(arr) and arr[i] == 5  # presence check
bisect.insort(arr, 4)                 # insert while keeping order

Binary search is O(log n): each comparison discards half the candidates. For n = 1,000,000, ~20 steps suffice.

⚠️ Gotcha: binary search works only on sorted data. If the array isn't sorted, you first sort it O(n log n) — and then for a single search a linear O(n) scan is simpler. Binary search pays off for repeated searches over the same sorted array.

Short answer: The main sources of bugs are the loop bounds (< vs <=), computing the midpoint, and updating the bounds. Use a half-open interval invariant and consistent updates.

In depth:

# Variant 1: closed interval [lo, hi], condition lo <= hi
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                    # <= ! otherwise we miss the case lo==hi
        mid = lo + (hi - lo) // 2      # no overflow (not critical in Python)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1               # +1 !
        else:
            hi = mid - 1               # -1 !
    return -1

# Variant 2: half-open [lo, hi), condition lo < hi — generalizes to "first >= x"
def lower_bound(arr, target):
    lo, hi = 0, len(arr)               # hi = len, NOT len-1
    while lo < hi:                     # strictly <
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid                   # NO -1
    return lo                          # first position >= target

Bug-free rules:

1. Fix the interval invariant clearly (closed [lo, hi] or half-open [lo, hi)) and stick to it.
2. The loop condition and the bound updates must match the invariant.
3. mid = lo + (hi - lo) // 2 avoids overflow (important in C/Java).
4. Make sure the interval shrinks on every iteration, otherwise an infinite loop.

⚠️ Gotcha: an infinite loop if hi = mid under the condition lo <= hi — the bounds stop converging. In practice, use bisect from the standard library instead of a hand-rolled implementation. The most common bugs: < vs <=, a forgotten +1/-1, an incorrect mid.

Short answer: Recursion is a function that calls itself. It needs a base case (stopping condition) and a recursive step (reduction to a smaller problem). Each call pushes a frame onto the call stack — recursion that's too deep overflows the stack.

In depth:

def factorial(n):
    if n <= 1:               # BASE CASE — without it, infinite recursion
        return 1
    return n * factorial(n - 1)   # STEP — a smaller problem

# The call stack grows: factorial(3) -> factorial(2) -> factorial(1)
# Depth = n -> O(n) memory on the stack

import sys
sys.setrecursionlimit(10000)      # default ~1000, raise it for deep recursion

Each recursive call saves its local variables and return point on the stack. Recursion depth = stack height = O(depth) memory.

Recursion vs iteration: recursion is often more readable for tree-shaped/divisible problems (trees, divide & conquer), but iteration is more memory-efficient (no frames) and doesn't overflow the stack. Any recursion can be rewritten as a loop with an explicit stack.

⚠️ Gotcha: a forgotten or unreachable base case → RecursionError: maximum recursion depth exceeded. Python's limit is ~1000 frames. For deep structures (a long linked list, a deep tree) prefer an iterative approach with an explicit stack.

Short answer: Tail recursion is when the recursive call is the function's last operation. Some languages optimize it into a loop (TCO), but Python deliberately doesn't — each call still creates a frame.

In depth:

# Tail form: the recursive call is the last action
def fact_tail(n, acc=1):
    if n <= 1:
        return acc
    return fact_tail(n - 1, acc * n)   # nothing after the call

# In Python this is still O(n) stack memory and will crash on large n!
# fact_tail(100000) -> RecursionError

Guido van Rossum consciously declined TCO in Python for these reasons:

1. Readable tracebacks: with TCO the intermediate frames are lost from the traceback, making debugging harder.
2. Philosophy: Python prefers explicit loops over recursion ("flat is better than nested").
3. It would require added complexity and ambiguity (what exactly counts as a tail call).

So in Python, tail recursion is rewritten as a plain loop:

def fact_iter(n):
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc          # O(1) memory, no stack limit

⚠️ Gotcha: don't rely on tail recursion in Python for deep computations — it isn't optimized and will hit the stack limit. In Scheme/Scala/Haskell it's optimized, in Python and Java it's not.

Short answer: DP solves problems with overlapping subproblems and optimal substructure by caching results. Memoization is top-down (recursion + cache), tabulation is bottom-up (filling a table iteratively).

In depth:

Signs that DP applies: (1) overlapping subproblems (the same subproblems are solved repeatedly), (2) optimal substructure (the solution is built from solutions to subproblems).

# Naive Fibonacci: O(2^n) — recomputes the same thing
def fib_slow(n):
    return n if n < 2 else fib_slow(n-1) + fib_slow(n-2)

# MEMOIZATION (top-down): recursion + cache -> O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)

# TABULATION (bottom-up): fill a table -> O(n) time, O(1) memory
def fib_tab(n):
    if n < 2: return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Classic problems:

• Knapsack: maximize value under a weight constraint, O(n*W).
• LCS (longest common subsequence): the longest common subsequence, O(n*m).
• Stairs/coins/edit distance — all DP.

# 0/1 knapsack: dp[w] = max value at capacity w
def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):   # reverse order!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Memoization vs tabulation: memoization is more natural (just add a cache to recursion), computes only the needed subproblems, but risks overflowing the stack. Tabulation has no recursion, is often more memory-efficient (you can keep only the last rows), but computes all subproblems.

⚠️ Gotcha: DP applies only with overlapping subproblems — if there are none (merge sort), it's just divide & conquer and a cache won't help. In knapsack, the weight traversal order (reverse for 0/1, forward for unbounded) is critical.

Short answer: A greedy algorithm makes a locally optimal choice at each step without revisiting it. DP enumerates options and combines subproblems. Greedy is faster, but correct only when the greedy-choice property holds.

In depth:

# Greedy: making change (works for "canonical" coin systems)
def coin_change_greedy(amount, coins=[25, 10, 5, 1]):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c          # take as many large coins as possible
        amount %= c
    return count
# For [25,10,5,1] greedy is correct. For [1,3,4] and amount=6:
# greedy -> 4+1+1 = 3 coins, but the optimum is 3+3 = 2 coins -> need DP!

• Greedy is correct when the problem has the greedy-choice property (a local optimum leads to a global one) and optimal substructure. Examples: activity selection, Huffman coding, MST (Kruskal/Prim), Dijkstra.
• DP is needed when greed goes wrong — you have to consider combinations of subproblems (as in making change for [1,3,4] above).

Greedy is usually O(n log n) (often because of the sort), DP is O(n*k) and more. Greedy is simpler and faster, but requires a correctness proof.

⚠️ Gotcha: greed seems right but often gives a suboptimal answer. Always check with a counterexample or prove the greedy-choice property. If greedy can't be proven, use DP.

Short answer: Two pointers are two indices moving through an array (from opposite ends or at different speeds), reducing O(n²) to O(n). The sliding window is a special case for contiguous segments.

In depth:

# TWO POINTERS: a pair with a given sum in a SORTED array -> O(n)
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1            # need more -> move the left one
        else:
            hi -= 1            # need less -> move the right one
    return None

# SLIDING WINDOW: longest substring without repeats -> O(n)
def longest_unique(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1      # shrink the window from the left
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

# Fixed-size window k: subarray sum -> O(n)
def max_sum_window(arr, k):
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]    # add the new one, drop the old one
        best = max(best, window)
    return best

Patterns: two pointers — for sorted arrays, pairs, reversals, in-place dedup. Sliding window — for segments/substrings with a condition (max sum, no repeats, minimum window).

⚠️ Gotcha: for two sum via two pointers the array must be sorted (otherwise use a hash table, see below). In a sliding window, watch the correct shrinking of the left bound — a common mistake is not moving left when the condition is violated.

Short answer: A hash table lets you check in O(1) whether "we've seen the number we need." The classic is two sum: for each element, look for the complement target - x in the set of already-seen ones, in O(n).

In depth:

# Two Sum on an UNSORTED array -> O(n) time, O(n) memory
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:         # O(1) check!
            return (seen[complement], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)

The idea is universal: instead of a nested loop O(n²), in a single pass we remember what we've seen in a hash table and check the condition in O(1). Used in: finding duplicates, counting frequencies, grouping (anagrams), caching.

⚠️ Gotcha: the hash solution spends O(n) memory — that's a time-space tradeoff against the O(1)-memory two-pointers solution (but that one requires a sort O(n log n)). The choice depends on whether the data is sorted and whether memory matters.

Short answer: Backtracking is systematic enumeration with rollback: we build a solution step by step, and if the current path doesn't lead to a solution, we roll back and try another. Used for combinatorial problems.

In depth:

# All permutations -> O(n!)
def permutations(nums):
    res = []
    def backtrack(path, remaining):
        if not remaining:
            res.append(path[:])        # found a complete solution
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()                             # ROLLBACK (backtrack)
    backtrack([], nums)
    return res

# Subsets -> O(2^n)
def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

Uses: permutations/combinations/subsets, N queens, sudoku, generating parentheses, finding a path in a maze. Often sped up with pruning — discarding obviously dead-end branches early.

⚠️ Gotcha: backtracking is exponential (O(2^n), O(n!)) — suitable only for small n. Always do the rollback (path.pop()) symmetrically to the choice, otherwise state will "leak" between branches. Add pruning to avoid enumerating everything.

Short answer: Understand → examples → brute force → optimize → code → test (UEBOCT). Don't rush to write code right away — talk through your approach out loud.

In depth:

1. Understand: clarify the input/output, constraints (n, ranges, duplicates, sortedness), edge cases. Restate the problem in your own words.
2. Examples: work through 1-2 examples by hand, including edge cases (empty input, one element, negatives).
3. Brute force: describe a naive solution and its complexity — this shows understanding and gives a "lower bar."
4. Optimize: look for the bottleneck. Think about data structures (a hash for O(1) lookup, a heap for top-k, two pointers/window) and patterns. State the tradeoffs.
5. Code: write cleanly, meaningful names, small steps.
6. Test: run through the examples and edge cases, check for off-by-one.

Hints for choosing a method: "sorted array" → binary search / two pointers; "segment/substring" → sliding window; "pair/complement/frequency" → hash table; "top K / priority" → heap; "all variants/permutations" → backtracking; "optimum with subproblems" → DP.

⚠️ Gotcha: silent coding is an anti-pattern in an interview. Think out loud, talk through the options and tradeoffs. And always clarify the constraints on n before coding — they hint at the target complexity (n ≤ 20 → exponential is fine; n ≤ 10^6 → you need O(n)/O(n log n)).

Short answer: Strings/lists are reversed with the slice [::-1] (O(n)) or with two pointers in place. A linked list is reversed by re-pointing the next pointers.

In depth:

# String (immutable -> a new object)
s = "hello"
s[::-1]                       # "olleh", O(n) time and memory

# List in place with two pointers -> O(1) extra memory
def reverse_inplace(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1; hi -= 1
    return arr

# Reversing a linked list -> O(n)
def reverse_linked_list(head):
    prev = None
    while head:
        nxt = head.next       # save the next one
        head.next = prev      # reverse the pointer
        prev = head           # advance prev
        head = nxt            # advance head
    return prev               # the new head

⚠️ Gotcha: when reversing a linked list, be sure to save next before reassigning, otherwise you'll lose the rest of the list. The slice [::-1] is simple but creates a copy (O(n) memory) — for an in-place reversal you need two pointers.

Short answer: Duplicates are found via a set in O(n). Anagrams are checked by sorting (O(n log n)) or by counting character frequencies (O(n)).

In depth:

# Is there a duplicate -> O(n) time, O(n) memory
def has_duplicate(arr):
    return len(set(arr)) != len(arr)

# Anagrams: sorting -> O(n log n)
def is_anagram_sort(a, b):
    return sorted(a) == sorted(b)

# Anagrams: frequency count -> O(n)
from collections import Counter
def is_anagram(a, b):
    return Counter(a) == Counter(b)

# Grouping anagrams -> O(n * k log k)
def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))        # key — the sorted letters
        groups.setdefault(key, []).append(w)
    return list(groups.values())

⚠️ Gotcha: for anagrams via Counter counting it's O(n), versus sorting O(n log n). Clarify: should case, spaces, unicode be taken into account. Counter(a) == Counter(b) is the cleanest way in Python.

Short answer: Print the numbers 1..n, replacing multiples of 3 with "Fizz," multiples of 5 with "Buzz," and multiples of 15 with "FizzBuzz." A classic check of basic logic.

In depth:

def fizzbuzz(n):
    for i in range(1, n + 1):
        if i % 15 == 0:          # 15 FIRST (a multiple of both 3 and 5)
            print("FizzBuzz")
        elif i % 3 == 0:
            print("Fizz")
        elif i % 5 == 0:
            print("Buzz")
        else:
            print(i)

# Alternative via concatenation (extensible)
def fizzbuzz2(n):
    for i in range(1, n + 1):
        out = ("Fizz" if i % 3 == 0 else "") + ("Buzz" if i % 5 == 0 else "")
        print(out or i)

O(n) time.

⚠️ Gotcha: check % 15 (or both conditions together) before the separate % 3 and % 5 — otherwise multiples of 15 will print as "Fizz." That's the main FizzBuzz filter.

Short answer: Use a stack: on an opening bracket push it, on a closing bracket check the top of the stack. At the end the stack should be empty. O(n).

In depth:

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)                 # opening -> onto the stack
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False                 # no pair or mismatch
    return not stack                         # empty -> everything is closed

is_valid("()[]{}")     # True
is_valid("([)]")       # False — incorrect nesting
is_valid("(")          # False — left unclosed

O(n) time, O(n) memory (the stack).

⚠️ Gotcha: don't forget to check that the stack is empty at the end (( → left unclosed) and that the stack is not empty before pop () without an opening one). Both edge cases are often missed.

Short answer: Floyd's algorithm ("tortoise and hare") uses two pointers at different speeds. If there's a cycle, the fast one catches the slow one. O(n) time, O(1) memory.

In depth:

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # by 1 step
        fast = fast.next.next       # by 2 steps
        if slow is fast:            # met -> cycle
            return True
    return False                    # fast reached the end -> no cycle

# Find the START of the cycle
def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    slow = head                     # one pointer back to the start
    while slow is not fast:         # move both by 1 step
        slow, fast = slow.next, fast.next
    return slow                     # the cycle entry point

Why it works: if there's a cycle, the fast pointer "gains" on the slow one by 1 node per iteration and will inevitably coincide. An alternative is a set of visited nodes (O(n) memory), but Floyd is more elegant (O(1)).

⚠️ Gotcha: check fast and fast.next before fast.next.next — otherwise an AttributeError at the end of the list. Compare nodes by is (identity), not == (values may coincide on different nodes).

Short answer: When n is guaranteed to be small (e.g., ≤ 1000-5000), when the code runs rarely, or when simplicity matters more than performance and there's no bottleneck.

In depth:

O(n²) performs ~n² operations. A rough guideline (at ~10^8 simple operations per second):

• n = 100 → 10,000 operations — instant.
• n = 1,000 → 10^6 — fractions of a millisecond.
• n = 10,000 → 10^8 — about a second, the edge of acceptable.
• n = 100,000 → 10^10 — tens of seconds, already unacceptable.

O(n²) is justified when:

• the input size is hard-capped from above and small;
• the algorithm is simpler and more readable than the optimal one (maintainability > microseconds);
• it's not a hot path (runs once a day, not in a loop per request);
• the constants of the O(n²) solution are so small that on real n it's faster than the "smart" one.

⚠️ Gotcha: hidden O(n²). The classic is x in list inside a loop over the list, or string concatenation in a loop (s += ... creates a new string each time → O(n²); use "".join(...)). These traps are invisible in tests and blow up in production. Always clarify the constraints on n before agreeing to O(n²).

Choose by the required exploration order, not by the data structure's name. Linear search works on arbitrary data; binary search requires sorting and discards half the range at each step. BFS uses a queue and finds the minimum number of edges in an unweighted graph, while DFS uses a stack or recursion and is useful for components, cycle detection, and topological traversal.

BFS: start ─► all of layer 1 ─► all of layer 2 ─► ...
DFS: start ─► go deep ─► dead end ─► backtrack

⚠️ Always maintain a visited set in a graph; otherwise a cycle can make the traversal repeat forever. Dijkstra's greedy proof also fails with negative edges—use Bellman–Ford or another suitable algorithm instead.