Practical Data Structures and Algorithms Interview Questions

def power(x, n): if n < 0: x, n = 1 / x, -n result = 1 while n > 0: if n & 1: # odd bit set: multiply current base in result *= x x *= x # square the base n >>= 1 # move to next bit return result # power(2, 10) == 1024; use % mod after each multiply for modular power

from functools import lru_cache def fib_naive(n): # O(2^n) time if n < 2: return n return fib_naive(n - 1) + fib_naive(n - 2) @lru_cache(maxsize=None) def fib_memo(n): # O(n) time, O(n) space if n < 2: return n return fib_memo(n - 1) + fib_memo(n - 2) def fib_iter(n): # O(n) time, O(1) space a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

def subsets(nums): result = [] current = [] def backtrack(i): if i == len(nums): result.append(current[:]) return current.append(nums[i]) # include nums[i] backtrack(i + 1) current.pop() # exclude nums[i] backtrack(i + 1) backtrack(0) return result # 2^n subsets, each up to n long: O(n * 2^n) time

def hanoi(n, src, dst, aux, moves): if n == 0: return hanoi(n - 1, src, aux, dst, moves) # move n-1 disks out of the way moves.append((src, dst)) # move the largest disk hanoi(n - 1, aux, dst, src, moves) # move n-1 disks on top of it moves = [] hanoi(3, 'A', 'C', 'B', moves) print(len(moves)) # 7, since the count is 2^n - 1

// Java static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } static long lcm(long a, long b) { return a / gcd(a, b) * b; // divide first to avoid overflow } // Runs in O(log(min(a, b))) because remainders shrink quickly.

def two_sum(nums, target): seen = {} # value -> index for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return [] # two_sum([2, 7, 11, 15], 9) -> [0, 1] # O(n) time, O(n) space; sorting + two pointers gives O(1) space but loses indices

def max_subarray(nums): best = current = nums[0] for x in nums[1:]: current = max(x, current + x) # extend or start fresh best = max(best, current) return best # max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 (subarray 4, -1, 2, 1)

def length_of_longest_substring(s): last = {} # char -> last index seen left = best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best # 'abcabcbb' -> 3, 'bbbbb' -> 1, 'pwwkew' -> 3; O(n) time

def rotate(nums, k): n = len(nums) k %= n def reverse(l, r): while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 reverse(0, n - 1) # reverse all reverse(0, k - 1) # reverse first k reverse(k, n - 1) # reverse the rest # [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space

def product_except_self(nums): n = len(nums) out = [1] * n prefix = 1 for i in range(n): # product of everything to the left out[i] = prefix prefix *= nums[i] suffix = 1 for i in range(n - 1, -1, -1): # multiply by everything to the right out[i] *= suffix suffix *= nums[i] return out # [1,2,3,4] -> [24,12,8,6]; O(n) time, O(1) extra space besides output

// Java static boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { char a = s.charAt(i), b = s.charAt(j); if (!Character.isLetterOrDigit(a)) { i++; continue; } if (!Character.isLetterOrDigit(b)) { j--; continue; } if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false; i++; j--; } return true; } // Two pointers, O(n) time, O(1) space.

def detect_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # cycle found slow = head while slow is not fast: # move both one step slow = slow.next fast = fast.next return slow # start of the cycle return None # O(n) time, O(1) space

class ListNode: def __init__(self, val=0, nxt=None): self.val = val self.next = nxt def merge(a, b): dummy = tail = ListNode() while a and b: if a.val <= b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next # O(m + n) time, O(1) extra space

// Java static boolean isValid(String s) { Deque<Character> st = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') st.push(')'); else if (c == '[') st.push(']'); else if (c == '{') st.push('}'); else if (st.isEmpty() || st.pop() != c) return false; } return st.isEmpty(); } // Push the expected closing bracket; O(n) time, O(n) space.

def next_greater(nums): res = [-1] * len(nums) stack = [] # indices with decreasing values for i, x in enumerate(nums): while stack and nums[stack[-1]] < x: res[stack.pop()] = x stack.append(i) return res # [4, 5, 2, 25] -> [5, 25, 25, -1] # Each index is pushed and popped once: O(n)

def reverse_k_group(head, k): # check that k nodes are available node, count = head, 0 while node and count < k: node = node.next count += 1 if count < k: return head # leave the remainder as is prev, cur = None, head for _ in range(k): # reverse k nodes cur.next, prev, cur = prev, cur, cur.next head.next = reverse_k_group(cur, k) # old head is now the group tail return prev # 1-2-3-4-5, k=2 -> 2-1-4-3-5; O(n) time

def inorder(root): result, stack = [], [] node = root while node or stack: while node: # go as far left as possible stack.append(node) node = node.left node = stack.pop() result.append(node.val) # visit node = node.right # then the right subtree return result # O(n) time, O(h) space; no recursion limit issues

// Java static int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } // Each node visited once: O(n) time, O(h) stack space. // BFS alternative: count levels while processing the queue level by level.

from collections import deque def level_order(root): if not root: return [] out, q = [], deque([root]) while q: level = [] for _ in range(len(q)): # process exactly one level node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) out.append(level) return out

def is_valid_bst(root, low=float('-inf'), high=float('inf')): if not root: return True if not (low < root.val < high): return False return (is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)) # Passing bounds checks the whole-subtree property, not just children. # O(n) time, O(h) space.

def lca(root, p, q): if root is None or root is p or root is q: return root left = lca(root.left, p, q) right = lca(root.right, p, q) if left and right: # p and q are on different sides return root return left or right # O(n) time, O(h) space; assumes both nodes exist in the tree

def serialize(root): out = [] def dfs(node): if not node: out.append('#') return out.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ','.join(out) def deserialize(data): vals = iter(data.split(',')) def build(): v = next(vals) if v == '#': return None node = TreeNode(int(v)) node.left = build() node.right = build() return node return build() # Preorder with null markers uniquely encodes the tree: O(n) both ways.

import heapq def kth_largest(nums, k): heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) # drop the smallest return heap[0] # smallest of the k largest # kth_largest([3, 2, 1, 5, 6, 4], 2) -> 5 # O(n log k) time, O(k) space; quickselect gives O(n) average

import heapq def merge_k_lists(lists): heap = [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) # i breaks ties dummy = tail = ListNode() while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next # O(N log K) for N total nodes

// Java static int minPlatforms(int[] arr, int[] dep) { Arrays.sort(arr); Arrays.sort(dep); int i = 0, j = 0, cur = 0, best = 0; while (i < arr.length) { if (arr[i] <= dep[j]) { // a train arrives before the next departs cur++; i++; best = Math.max(best, cur); } else { cur--; j++; } } return best; } // O(n log n) for sorting, O(1) extra space.

def can_jump(nums): farthest = 0 for i, step in enumerate(nums): if i > farthest: # this index is unreachable return False farthest = max(farthest, i + step) if farthest >= len(nums) - 1: return True return True # [2,3,1,1,4] -> True, [3,2,1,0,4] -> False # Greedy: track the farthest reachable index, O(n) time, O(1) space

import heapq class MedianFinder: def __init__(self): self.low = [] # max-heap via negation (smaller half) self.high = [] # min-heap (larger half) def add(self, x): heapq.heappush(self.low, -x) heapq.heappush(self.high, -heapq.heappop(self.low)) if len(self.high) > len(self.low): heapq.heappush(self.low, -heapq.heappop(self.high)) def median(self): if len(self.low) > len(self.high): return -self.low[0] return (-self.low[0] + self.high[0]) / 2 # add is O(log n), median is O(1)

from collections import deque def shortest_path(grid): R, C = len(grid), len(grid[0]) if grid[0][0] or grid[R-1][C-1]: return -1 q = deque([(0, 0, 1)]) seen = {(0, 0)} while q: r, c, d = q.popleft() if (r, c) == (R - 1, C - 1): return d for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C and not grid[nr][nc] and (nr, nc) not in seen: seen.add((nr, nc)) q.append((nr, nc, d + 1)) return -1 # BFS: O(R * C)

// Java static int numIslands(char[][] g) { int count = 0; for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++) if (g[r][c] == '1') { count++; sink(g, r, c); } return count; } static void sink(char[][] g, int r, int c) { if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return; g[r][c] = '0'; // mark visited sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1); } // O(rows * cols) time

import heapq def dijkstra(graph, src): # graph: {node: [(neighbour, weight), ...]} dist = {src: 0} heap = [(0, src)] while heap: d, u = heapq.heappop(heap) if d > dist.get(u, float('inf')): continue # stale entry for v, w in graph.get(u, []): nd = d + w if nd < dist.get(v, float('inf')): dist[v] = nd heapq.heappush(heap, (nd, v)) return dist # O((V + E) log V); weights must be non-negative

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

class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # path halving x = self.parent[x] return x def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] return True # Nearly O(1) amortised per operation

def climb_stairs(n): if n <= 2: return n prev2, prev1 = 1, 2 # ways(1), ways(2) for _ in range(3, n + 1): prev2, prev1 = prev1, prev1 + prev2 return prev1 # ways(n) = ways(n-1) + ways(n-2): a Fibonacci pattern # climb_stairs(5) -> 8; O(n) time, O(1) space

def coin_change(coins, amount): INF = amount + 1 dp = [0] + [INF] * amount # dp[x] = min coins for amount x for x in range(1, amount + 1): for c in coins: if c <= x and dp[x - c] + 1 < dp[x]: dp[x] = dp[x - c] + 1 return dp[amount] if dp[amount] != INF else -1 # coin_change([1, 3, 4], 6) -> 2 (3 + 3) # O(amount * len(coins)) time, O(amount) space

// Java static int lcs(String a, String b) { int m = a.length(), n = b.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } return dp[m][n]; } // lcs(abcde, ace) = 3; O(m * n) time and space

def knapsack(weights, values, capacity): dp = [0] * (capacity + 1) # dp[w] = best value with capacity w for wt, val in zip(weights, values): for w in range(capacity, wt - 1, -1): # go downwards: each item once dp[w] = max(dp[w], dp[w - wt] + val) return dp[capacity] # knapsack([1, 3, 4], [15, 20, 30], 4) -> 35 # O(n * W) time, O(W) space

def edit_distance(a, b): m, n = len(a), len(b) prev = list(range(n + 1)) # distances from empty prefix of a for i in range(1, m + 1): cur = [i] + [0] * n for j in range(1, n + 1): if a[i - 1] == b[j - 1]: cur[j] = prev[j - 1] else: cur[j] = 1 + min(prev[j], # delete cur[j - 1], # insert prev[j - 1]) # replace prev = cur return prev[n] # edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space

def rob(nums): take, skip = 0, 0 # best if the previous house is taken or skipped for x in nums: take, skip = skip + x, max(take, skip) return max(take, skip) # rob([2, 7, 9, 3, 1]) -> 12 (2 + 9 + 1) # dp[i] = max(dp[i-1], dp[i-2] + nums[i]); O(n) time, O(1) space

// Java static int binarySearch(int[] a, int target) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // avoids overflow if (a[mid] == target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } // O(log n) time, O(1) space

def merge_sort(a): if len(a) <= 1: return a mid = len(a) // 2 left = merge_sort(a[:mid]) right = merge_sort(a[mid:]) out, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # <= keeps the sort stable out.append(left[i]); i += 1 else: out.append(right[j]); j += 1 out.extend(left[i:]) out.extend(right[j:]) return out # O(n log n) time, O(n) extra space

from bisect import bisect_left, bisect_right def search_range(nums, target): lo = bisect_left(nums, target) # first index >= target if lo == len(nums) or nums[lo] != target: return [-1, -1] hi = bisect_right(nums, target) - 1 # last index <= target return [lo, hi] # [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)

def permutations(nums): result, path = [], [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] = True path.append(x) backtrack() path.pop() # undo the choice used[i] = False backtrack() return result # n! permutations: O(n * n!) time

def search_rotated(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1 # [4,5,6,7,0,1,2], 0 -> 4; O(log n)

def int_sqrt(x): lo, hi = 0, x ans = 0 while lo <= hi: mid = (lo + hi) // 2 if mid * mid <= x: ans = mid # mid is a valid candidate lo = mid + 1 else: hi = mid - 1 return ans # int_sqrt(8) -> 2, int_sqrt(16) -> 4; O(log x)