Which data structures are asked most?

Arrays, hashmaps, strings, linked lists, trees (especially BST and tries), heaps, and graphs. Master these in your preferred language.

How important are Big-O tradeoffs?

Essential. You should be able to state time and space complexity for every solution and justify trade-offs.

Do I need to implement every DS from scratch?

Know implementations of linked list, BST, heap, trie, and union-find. For others, knowing the interface and complexity is usually enough.

For FAANG targets, 200–400 problems across all patterns. Prioritize quality over quantity — understand one problem deeply before moving on.

What if I blank during an interview?

Verbalize your thought process, start with brute force, think out loud, and ask clarifying questions. Interviewers value process over perfect answers.

Data Structures Interview Questions (2026) — 100 Q&A

Big O notation describes the upper bound on how an algorithm's runtime or memory usage grows relative to input size n, ignoring constant factors and lower-order terms. It matters because it lets you compare algorithms independent of hardware or implementation details — O(n²) will always lose to O(n log n) for large n regardless of the CPU speed. Engineers use it to make architectural decisions before writing a single line of code, avoiding solutions that are fast on toy inputs but catastrophically slow in production.

python
# O(n²) — nested loops, unacceptable for n=1,000,000
for i in range(n):
    for j in range(n):
        process(i, j)

O(1) — constant time regardless of input size; e.g. array index access `arr[i]`. O(log n) — halves the search space each step; e.g. binary search. O(n) — one pass through all elements; e.g. finding the max in an unsorted array. O(n log n) — divide-and-conquer with a linear merge; e.g. merge sort. O(n²) — all pairs; e.g. bubble sort or checking every pair in an array. O(2^n) — exponential explosion; e.g. generating all subsets of a set or naive recursive Fibonacci. The practical cutoff is roughly: n≤10 any complexity is fine; n≤10⁴ O(n²) works; n≤10⁶ needs O(n log n) or better; n≤10⁸ requires O(n).

python
# O(log n): binary search
def bsearch(arr, t):
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if arr[mid]==t: return mid
        elif arr[mid]<t: lo=mid+1
        else: hi=mid-1
    return -1

An array is a contiguous block of memory where each element is stored at a fixed offset from the base address, enabling O(1) random access via index arithmetic (`base + i * element_size`). Searching an unsorted array is O(n) (linear scan); a sorted array can be searched in O(log n) with binary search. Inserting or deleting at an arbitrary index is O(n) because all subsequent elements must shift. Appending to the end of a static array is O(1) if capacity allows; otherwise the array must be reallocated.

A dynamic array wraps a fixed-size array and automatically grows when capacity is exhausted. When the array is full it allocates a new buffer — typically 2× the current capacity — copies all existing elements, then frees the old buffer. This doubling strategy ensures that n total pushes cost O(n) total work: the series of copies (1 + 2 + 4 + … + n) sums to O(n), giving O(1) amortized cost per append. Python's `list` uses a growth factor of ~1.125 for small sizes and ~1.5–2× for larger ones.

python
class DynArray:
    def __init__(self):
        self._data = [None] * 1
        self._size = 0
    def append(self, val):
        if self._size == len(self._data):
            self._data = self._data + [None] * len(self._data)
        self._data[self._size] = val
        self._size += 1

A linked list is a sequence of nodes where each node stores a value and a pointer to the next node; nodes are not necessarily contiguous in memory. A singly linked list has one pointer per node (`next`), enabling O(n) traversal forward only. A doubly linked list adds a `prev` pointer, enabling O(1) deletion of a node given a direct reference (no need to find the predecessor) and bidirectional traversal, at the cost of 2× pointer overhead. The head (and optionally tail) pointer is stored separately.

python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None   # singly
        self.prev = None   # doubly (add this)

A stack is a Last-In-First-Out (LIFO) abstract data type. `push(x)` adds x to the top; `pop()` removes and returns the top element; `peek()` returns the top without removing it. All three are O(1) when implemented over a dynamic array (using the array's end as the top) or a singly linked list (using the head as the top). Classic uses: function call stack, undo history, expression parsing, and DFS iterative traversal.

python
stack = []
stack.append(1)  # push
stack.append(2)
top = stack[-1]  # peek
stack.pop()      # pop -> 2

A queue is a First-In-First-Out (FIFO) abstract data type. `enqueue(x)` appends to the back; `dequeue()` removes from the front. Both are O(1) with a doubly linked list or a circular buffer. Implementing with a plain dynamic array makes dequeue O(n) due to shifting — avoid it. Python's `collections.deque` gives O(1) on both ends. Classic uses: BFS, task scheduling, print spooling, and producer-consumer pipelines.

python
from collections import deque
q = deque()
q.append(1)     # enqueue
q.append(2)
q.popleft()     # dequeue -> 1

A hash function maps keys of arbitrary type/size to a fixed-range integer. A good hash function is (1) deterministic — same key always yields same hash; (2) uniform — output bits are evenly distributed, minimising collisions; (3) fast to compute — typically O(key length); (4) avalanche effect — a single bit change in the input flips ~50% of output bits (critical for security-grade hashes like SHA-256). For hash tables, non-cryptographic hashes like MurmurHash3 or xxHash are preferred for speed. For string keys the FNV-1a or djb2 are popular simple choices.

python
# djb2 for strings
def djb2(s):
    h = 5381
    for c in s:
        h = ((h << 5) + h) + ord(c)  # h*33 + c
    return h & 0xFFFFFFFF

Insert (push): append the new element at the end of the array (O(1)), then bubble it up (heapify-up) by repeatedly swapping with its parent while the heap property is violated. The element travels at most h = O(log n) levels, so insert is O(log n). Extract-min (pop): swap the root with the last element (O(1)), shrink the array by one, then push the new root down (heapify-down) by swapping with the smaller child until the heap property holds — also O(log n). Peek (min without removing) is always O(1) since the root is the minimum.

python
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
print(heapq.heappop(heap))  # 1

BFS explores a graph level by level, visiting all neighbours of a node before moving to their neighbours. It uses a queue, starting from a source vertex, marking nodes visited on enqueue to avoid revisits. Time complexity O(V + E), space O(V) for the visited set and queue. BFS finds the shortest path (in terms of number of edges) between source and any reachable vertex in an unweighted graph. It also detects connected components and can check bipartiteness.

python
from collections import deque
def bfs(graph, src):
    q, visited = deque([src]), {src}
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb); q.append(nb)

DFS explores as far as possible along each branch before backtracking. Recursively: visit a node, mark it, then recurse on each unvisited neighbour. Iteratively: replace the call stack with an explicit stack. Time O(V + E), space O(V) for the recursion stack. DFS is the basis for topological sort, cycle detection, strongly connected components (Kosaraju/Tarjan), and solving mazes. DFS does not guarantee shortest paths in unweighted graphs.

python
def dfs(graph, node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    for nb in graph[node]:
        if nb not in visited:
            dfs(graph, nb, visited)
    return visited

Recursion is when a function calls itself to solve a smaller subproblem of the same shape. The base case is a condition where the function returns immediately without a recursive call, preventing infinite loops. The recursive case breaks the problem down and calls itself with a strictly smaller input, converging toward the base case. Every recursive algorithm has an equivalent iterative version (using an explicit stack). Recursive solutions are often cleaner for tree/graph traversal, divide-and-conquer, and backtracking.

python
def factorial(n):
    if n <= 1: return 1        # base case
    return n * factorial(n-1)  # recursive case

Memoization is an optimisation that caches the return value of a function call keyed by its arguments, so subsequent calls with the same arguments return the cached result in O(1) instead of recomputing. It converts certain exponential-time recursive algorithms (e.g. naive Fibonacci O(2^n)) into polynomial-time by ensuring each unique subproblem is solved only once. Memoization is top-down dynamic programming — you write the natural recursion and add a cache.

python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)  # O(n) with memo

Amortized analysis spreads the cost of occasional expensive operations over a sequence of cheaper ones to give a per-operation average. For a dynamic array that doubles on full capacity: most pushes cost O(1); the occasional doubling copy costs O(n). Using the accounting (or aggregate) method: over n pushes, the total number of element copies is 1 + 2 + 4 + … + n ≤ 2n, so total work is O(n) and cost per push is O(1) amortized even though individual doubling steps are O(n). This is why Python's `list.append` is described as O(1) amortized despite periodic reallocations.

python
# Total copies for n=8 appends (capacity 1→2→4→8):
# copies = 1 + 2 + 4 = 7 < 2*8 = 16  => O(n) total

The sliding window technique maintains a window [left, right] over a sequence, efficiently adding the element entering on the right and removing the element leaving on the left in O(1) each, giving O(n) total instead of O(nk) for the naive approach. For maximum sum of size k: compute the initial window sum, then slide right, adding the new element and subtracting the outgoing element, tracking the running maximum. Two-pointer (for variable-size windows) expands right until a condition is met, then shrinks left until it's violated again — both pointers only move forward, giving O(n).

python
def max_sum_k(arr, k):
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i-k]
        best = max(best, window)
    return best

Binary search halves the search interval each iteration, finding a target in O(log n) time on a sorted array. The two canonical bugs: (1) using `mid = (lo + hi) / 2` can overflow for large indices in languages with fixed-width integers — use `lo + (hi - lo) / 2`. (2) Loop condition `lo < hi` vs `lo <= hi` — use `lo <= hi` with the half-open convention to handle single-element arrays and ensure every index is reachable. When searching for a boundary (first true, last false), use `lo <= hi` and carefully update `lo` or `hi` without returning early.

python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1  # not found

Binary search on the answer applies when you can frame a problem as: "find the minimum (or maximum) value x such that condition(x) is true," and condition is monotone (once true, always true for larger x). Instead of searching an array, you binary search over the answer space. A classic example: "given n tasks with times and m workers, what is the minimum possible maximum load?" Check feasibility for a given load cap in O(n), then binary search the cap in O(log(sum)). Total O(n log(sum)) vs O(n²) brute force.

python
def can_split(times, m, cap):
    workers, cur = 1, 0
    for t in times:
        if cur + t > cap: workers += 1; cur = 0
        cur += t
    return workers <= m
# binary search lo=max(times), hi=sum(times)

AVL trees maintain |height(left) - height(right)| ≤ 1 at every node, enforced after every insert/delete via rotations. An LL imbalance (left-left) occurs when the left child's left subtree is too tall — fix with a right rotation at the unbalanced node. RR imbalance: right child's right subtree too tall — left rotation. LR imbalance: left child's right subtree too tall — left-rotate the left child first, then right-rotate the node. RL: right child's left subtree too tall — right-rotate the right child, then left-rotate the node. Each rotation is O(1). After balancing, height is O(log n) guaranteeing O(log n) operations.

LL case:          RR case:
    z                  z
   /                    \
  y     →[R-rot]→        y → [L-rot]
 /                        \
x                          x

Heapify-up (sift-up) restores the heap invariant after inserting at the end: compare the node at index i with its parent at ⌊i/2⌋; if the heap property is violated, swap them, and repeat at the parent index. This runs in O(log n) worst case. Heapify-down (sift-down) restores the heap after removing the root (replaced by the last leaf): compare the node at index i with its children at 2i and 2i+1; swap with the smaller (min-heap) or larger (max-heap) child if the property is violated; repeat at that child's index. Also O(log n).

python
def sift_up(h, i):
    while i > 0 and h[(i-1)//2] > h[i]:
        h[i], h[(i-1)//2] = h[(i-1)//2], h[i]
        i = (i-1)//2

The naive approach of inserting n elements one by one costs O(n log n). Bottom-up heap construction achieves O(n): treat the input array as a complete binary tree, then call heapify-down on every non-leaf node from bottom to top (indices ⌊n/2⌋-1 down to 0). The key insight is that most nodes are near the bottom and travel only a few levels down — the exact sum of work is Σ(h × nodes at depth d) = O(n). Python's `heapq.heapify` uses this O(n) algorithm.

python
def build_heap(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr  # now a valid min-heap

Union-Find maintains a partition of n elements into disjoint sets supporting two operations: find (which set does x belong to?) and union (merge the sets containing x and y). Each set is a tree; find traverses to the root. Path compression flattens the tree during find: each node on the root-path points directly to the root after the call. Union by rank always attaches the shorter tree under the taller, keeping trees shallow. Together, find and union run in O(α(n)) amortized — inverse Ackermann function, practically O(1) for all real n. Used in Kruskal's MST, cycle detection, and network connectivity.

python
parent = list(range(n)); rank = [0]*n
def find(x):
    if parent[x]!=x: parent[x]=find(parent[x])
    return parent[x]
def union(x,y):
    rx,ry=find(x),find(y)
    if rank[rx]<rank[ry]: rx,ry=ry,rx
    parent[ry]=rx
    if rank[rx]==rank[ry]: rank[rx]+=1

A segment tree is a binary tree over an array of size n where each node stores the aggregate (sum, min, max) of a contiguous subarray. The root covers [0, n-1]; each node covers half its parent's range; leaves hold individual elements. Build is O(n). Point update: update the leaf, then recompute ancestors bottom-up — O(log n). Range query: recursively combine nodes whose ranges are fully inside the query range, splitting at at most O(log n) nodes — O(log n). Total space O(4n) using an array representation (1-indexed, children at 2i and 2i+1).

python
def build(node, lo, hi):
    if lo==hi: tree[node]=arr[lo]; return
    mid=(lo+hi)//2
    build(2*node,lo,mid); build(2*node+1,mid+1,hi)
    tree[node]=tree[2*node]+tree[2*node+1]

A Fenwick tree (BIT) stores partial sums in a compact array bit[] where bit[i] covers a range of length lowbit(i) = i & (-i) ending at i. Prefix sum query: accumulate bit[i], then jump to i - lowbit(i), repeating until i = 0 — O(log n). Point update: add delta to bit[i], then jump to i + lowbit(i), propagating up — O(log n). Space O(n). Compared to segment trees: BIT is simpler to code, uses 2× less memory, and has smaller constants, but supports fewer operations (no range update + range query without extra tricks). Ideal for order statistics, inversion count, and competitive programming.

python
def update(i, d):
    while i < len(bit):
        bit[i] += d; i += i & -i
def prefix(i):
    s = 0
    while i > 0:
        s += bit[i]; i -= i & -i
    return s

All three traverse the trie character by character, taking O(L) time where L is the length of the input string — independent of the number of stored strings. Insert: for each character, if the child node doesn't exist, create it; mark the last node as end-of-word. Search: traverse; return True only if the last node exists and is marked end-of-word. startsWith: same as search but return True even if the last node is not end-of-word. Space per inserted string is O(L × ALPHABET_SIZE) in the worst case. Trie outperforms a hash set for prefix queries because hash sets can't answer "all strings starting with 'pre'" in sub-O(n) time.

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

An LRU (Least Recently Used) cache evicts the least recently accessed entry when at capacity. Use a hash map (key → node) for O(1) lookup and a doubly-linked list for O(1) eviction order maintenance. The list's tail is the LRU; head is the MRU. On get: move the accessed node to the head, return its value. On put: if key exists, update value and move to head; if at capacity, remove the tail node, delete from hash map, insert new node at head. All operations O(1). Python's `functools.lru_cache` and `collections.OrderedDict` implement this pattern.

python
from collections import OrderedDict
class LRUCache:
    def __init__(self, cap):
        self.cap = cap; self.cache = OrderedDict()
    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key); return self.cache[key]
    def put(self, key, val):
        if key in self.cache: self.cache.move_to_end(key)
        self.cache[key] = val
        if len(self.cache) > self.cap: self.cache.popitem(last=False)

A monotonic stack maintains elements in strictly increasing or decreasing order from bottom to top. For "next greater element to the right": iterate left to right, maintaining a decreasing stack. When processing element x, pop all stack elements smaller than x — x is their next greater element. Push x. After processing all elements, remaining stack entries have no greater element to the right. Total work is O(n) because each element is pushed and popped at most once. Other uses: largest rectangle in histogram, daily temperatures, online stock span.

python
def next_greater(nums):
    res = [-1] * len(nums)
    stack = []  # indices, decreasing by value
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

A monotonic deque maintains indices such that values are strictly decreasing from front to back. For sliding window max of size k: iterate through the array; before processing index i, (1) remove front if it's outside the window (index ≤ i-k); (2) remove all indices from the back whose values are ≤ current value (they can never be the max while the current element is in the window); (3) append i; the front is always the max of the current window. Total O(n) time — each index is enqueued and dequeued at most once.

python
from collections import deque
def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        while dq and dq[0] < i-k+1: dq.popleft()
        while dq and nums[dq[-1]] <= x: dq.pop()
        dq.append(i)
        if i >= k-1: res.append(nums[dq[0]])
    return res

Floyd's (tortoise-and-hare) algorithm detects cycles using two pointers: slow moves one step at a time, fast moves two. If a cycle exists, fast will eventually lap slow and they meet inside the cycle — this is guaranteed within O(n) steps. If fast reaches null, no cycle. To find the cycle start: after detection, reset one pointer to the head; move both one step at a time; they meet at the cycle's entrance. This works because the distance from head to cycle start equals the distance from meeting point to cycle start (modulo cycle length). Space O(1). The alternative (hash set of visited nodes) uses O(n) space.

python
def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow == fast: return True
    return False

Iterate with three pointers: prev (starts null), curr (starts head), and next. At each step, save curr.next, point curr.next to prev, advance prev to curr, and advance curr to saved next. When curr is null, prev points to the new head. This is O(n) time and O(1) space — no recursion, no extra memory. The recursive approach is conceptually clean but uses O(n) call stack space and risks stack overflow on very long lists.

python
def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev  # new head

Serialization converts a tree to a string/array; deserialization reconstructs it. BFS-based: level-order traversal, encoding null children explicitly. Deserialization reads values level by level, pairing each non-null node with the next two values as children — O(n) time and space. Preorder + null markers also works: recursively write node value then recurse left then right, encoding null as "#". Deserialization reads one token at a time, returning null on "#". This is the approach used in LeetCode's TreeNode codec and handles arbitrary trees including non-complete ones.

python
def serialize(root):
    res=[]; dfs=lambda n: (res.append(str(n.val) if n else "#"),
    dfs(n.left) if n else None, dfs(n.right) if n else None)
    dfs(root); return ",".join(res)

Three-color DFS assigns each vertex a state: white (unvisited), grey (in current DFS path / recursion stack), or black (fully processed). Start DFS from every white vertex. When exploring a white neighbour, mark it grey and recurse; when done, mark it black. If you encounter a grey neighbour, you've found a back edge — a cycle exists. Black neighbours are safe (already fully explored, no cycle through them). This is O(V + E) and detects all cycles. Note: for undirected graphs, simply tracking visited is enough (a revisited non-parent node means a cycle).

python
def has_cycle(graph, n):
    color = [0]*n  # 0=white,1=grey,2=black
    def dfs(u):
        color[u]=1
        for v in graph[u]:
            if color[v]==1: return True
            if color[v]==0 and dfs(v): return True
        color[u]=2; return False
    return any(dfs(i) for i in range(n) if color[i]==0)

Given n items with weights w[i] and values v[i] and a capacity W, the goal is to maximise value without exceeding W. Recurrence: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) if c ≥ w[i], else dp[i-1][c]. The 2D table is O(nW) time and space. Space optimization: since row i only depends on row i-1, use a single 1D array and iterate c from W down to w[i] (right-to-left prevents reusing item i twice). This gives O(W) space. Note: the "fractional knapsack" (items can be split) is greedily solvable in O(n log n); the 0/1 variant requires DP because greedy fails.

python
def knapsack(weights, values, W):
    dp = [0] * (W+1)
    for w, v in zip(weights, values):
        for c in range(W, w-1, -1):  # reverse!
            dp[c] = max(dp[c], dp[c-w]+v)
    return dp[W]

LCS finds the longest sequence of characters (not necessarily contiguous) that appears in both strings in the same order. DP recurrence: if s1[i] == s2[j], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base case: dp[0][*] = dp[*][0] = 0. Fill the table in O(mn) time and O(mn) space; optimize to O(min(m,n)) by keeping only two rows. Backtrack through the table to reconstruct the actual subsequence. LCS is the basis of `diff` tools, DNA alignment, and plagiarism detection.

python
def lcs(a, b):
    m,n=len(a),len(b); dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            dp[i][j]=dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]

Edit distance between strings a and b is the minimum number of single-character insertions, deletions, or substitutions to transform a into b. DP recurrence: dp[i][j] = cost of transforming a[0..i-1] to b[0..j-1]. If a[i-1]==b[j-1]: dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min(dp[i-1][j-1] (substitute), dp[i-1][j] (delete from a), dp[i][j-1] (insert into a)). Time O(mn), space O(min(m,n)) with rolling array. Used in spell checking, DNA alignment, fuzzy search, and autocorrect.

python
def edit_dist(a, b):
    m,n=len(a),len(b); dp=list(range(n+1))
    for i in range(1,m+1):
        prev=dp[:]; dp[0]=i
        for j in range(1,n+1):
            dp[j]=prev[j-1] if a[i-1]==b[j-1] else 1+min(prev[j-1],prev[j],dp[j-1])
    return dp[n]

Given coin denominations and a target amount, find the minimum number of coins. DP: dp[0] = 0; dp[i] = min(dp[i - coin] + 1) for all coins ≤ i; initialize dp[1..amount] = ∞. Fill bottom-up in O(amount × coins) time and O(amount) space. This is unbounded knapsack (coins can be reused). Greedy fails on arbitrary coin sets (e.g. coins = {1,3,4}, amount=6: greedy picks 4+1+1=3 coins, DP finds 3+3=2). The "can you make exact change" variant is a boolean DP.

python
def coin_change(coins, amount):
    dp = [float('inf')] * (amount+1); dp[0]=0
    for i in range(1, amount+1):
        for c in coins:
            if c<=i: dp[i]=min(dp[i], dp[i-c]+1)
    return dp[amount] if dp[amount]!=float('inf') else -1

Merge sort divides the array in half recursively until subarrays of size 1 are reached, then merges sorted pairs back together. The merge step linearly scans two sorted arrays into one in O(n). The recurrence is T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2: a=2, b=2, f(n)=n, n^(log_b a)=n^1): T(n) = O(n log n). Merge sort is stable, comparison-based, and optimal for linked lists (no random access needed). Its O(n) auxiliary space is a drawback for large in-memory arrays.

python
def merge_sort(arr):
    if len(arr)<=1: return arr
    mid=len(arr)//2
    L,R=merge_sort(arr[:mid]),merge_sort(arr[mid:])
    i=j=0; res=[]
    while i<len(L) and j<len(R):
        if L[i]<=R[j]: res.append(L[i]); i+=1
        else: res.append(R[j]); j+=1
    return res+L[i:]+R[j:]

Quicksort partitions an array around a pivot: elements smaller go left, larger go right, then recursively sort each partition. Lomuto partition selects the last element as pivot; Hoare uses two converging pointers. Average case O(n log n): each level of recursion does O(n) work and on average creates balanced partitions. Worst case O(n²): always picking the min or max pivot (sorted input with last-element pivot) creates partitions of size 0 and n-1. Randomized pivot: swap a random element with the last before partitioning, reducing probability of worst case to negligibly small (O(n²) with probability 1/n!). In practice quicksort outperforms merge sort due to better cache behaviour and O(log n) stack space.

python
import random
def quicksort(arr, lo, hi):
    if lo<hi:
        r=random.randint(lo,hi); arr[r],arr[hi]=arr[hi],arr[r]
        p=partition(arr,lo,hi)
        quicksort(arr,lo,p-1); quicksort(arr,p+1,hi)

Data Structures Interview Questions (2026)

Frequently Asked Questions

Which data structures are asked most?

How important are Big-O tradeoffs?

Do I need to implement every DS from scratch?

How much LeetCode?

What if I blank during an interview?

Related Topics

Ready to apply?