ML Engineer
Coding & Data Structures (LeetCode)
Every MLE interview at FAANG has 2โ3 LeetCode coding rounds as the primary filter. Problems range from medium to hard, focusing on arrays, graphs, trees, DP, and heaps. Speed and correctness under time pressure matter โ aim for clean O(n log n) or better solutions with clear verbal explanation.
Core Theory
- 1Two pointers: use two indices moving toward each other or in the same direction to reduce O(nยฒ) brute force to O(n). Classic: two-sum on sorted array, container with most water, trapping rain water, 3-sum.
- 2Sliding window: maintain a window [l, r] and expand/shrink based on a condition. O(n) for problems like longest substring without repeating characters, minimum window substring, max sum subarray of size k.
- 3Binary search: works on any monotone condition, not just sorted arrays. Template: lo=0, hi=n-1, while lo<=hi, mid=(lo+hi)//2. Also binary search on answer space (Koko bananas, minimum capacity ships).
- 4BFS/DFS on graphs: BFS = queue, finds shortest path in unweighted graphs. DFS = stack/recursion, finds connected components, cycles, topological order. Know both iterative and recursive DFS.
- 5Dynamic programming: identify overlapping subproblems + optimal substructure. State definition is the key insight. 1D DP (climbing stairs, house robber), 2D DP (edit distance, LCS), DP on intervals, DP on trees.
- 6Heaps (priority queues): Python heapq is a min-heap. For max-heap, negate values. Key patterns: top-K elements in O(n log K), merge K sorted lists, median of data stream with two heaps.
- 7Tree traversals: inorder (L-root-R = sorted for BST), preorder (root-L-R = copy tree), postorder (L-R-root = delete tree). BFS level-order with deque. Know LCA, serialize/deserialize, path sum.
- 8Monotonic stack: stack that stays increasing or decreasing. Solves next greater element, largest rectangle in histogram, daily temperatures in O(n). Recognize the pattern: 'nearest larger/smaller element'.
Key Formulas
| 1 | import heapq |
| 2 | |
| 3 | class MedianFinder: |
| 4 | """ |
| 5 | Maintain two heaps: |
| 6 | - max_heap (lo): stores lower half, negate for max-heap via heapq |
| 7 | - min_heap (hi): stores upper half |
| 8 | Invariant: len(lo) == len(hi) or len(lo) == len(hi) + 1 |
| 9 | """ |
| 10 | def __init__(self): |
| 11 | self.lo = [] # max-heap (negated) |
| 12 | self.hi = [] # min-heap |
| 13 | |
| 14 | def addNum(self, num: int) -> None: |
| 15 | # Always push to lo first |
| 16 | heapq.heappush(self.lo, -num) |
| 17 | |
| 18 | # Balance: lo's max must be <= hi's min |
| 19 | if self.hi and (-self.lo[0]) > self.hi[0]: |
| 20 | val = -heapq.heappop(self.lo) |
| 21 | heapq.heappush(self.hi, val) |
| 22 | |
| 23 | # Keep sizes balanced: lo can have at most 1 extra |
| 24 | if len(self.lo) > len(self.hi) + 1: |
| 25 | val = -heapq.heappop(self.lo) |
| 26 | heapq.heappush(self.hi, val) |
| 27 | elif len(self.hi) > len(self.lo): |
| 28 | val = heapq.heappop(self.hi) |
| 29 | heapq.heappush(self.lo, -val) |
| 30 | |
| 31 | def findMedian(self) -> float: |
| 32 | if len(self.lo) > len(self.hi): |
| 33 | return -self.lo[0] |
| 34 | return (-self.lo[0] + self.hi[0]) / 2.0 |
| 35 | |
| 36 | # Test |
| 37 | mf = MedianFinder() |
| 38 | for n in [1, 2, 3, 4, 5]: |
| 39 | mf.addNum(n) |
| 40 | print(f"After {n}: median = {mf.findMedian()}") |
| 41 | # Output: 1.0, 1.5, 2.0, 2.5, 3.0 |
| 42 | |
| 43 | # โโโ Bonus: LRU Cache โ HashMap + Doubly Linked List โโโโโโโโโโโโโโโ |
| 44 | from collections import OrderedDict |
| 45 | |
| 46 | class LRUCache: |
| 47 | def __init__(self, capacity: int): |
| 48 | self.cap = capacity |
| 49 | self.cache = OrderedDict() # preserves insertion order |
| 50 | |
| 51 | def get(self, key: int) -> int: |
| 52 | if key not in self.cache: |
| 53 | return -1 |
| 54 | self.cache.move_to_end(key) # mark as recently used |
| 55 | return self.cache[key] |
| 56 | |
| 57 | def put(self, key: int, value: int) -> None: |
| 58 | if key in self.cache: |
| 59 | self.cache.move_to_end(key) |
| 60 | self.cache[key] = value |
| 61 | if len(self.cache) > self.cap: |
| 62 | self.cache.popitem(last=False) # evict least recently used |
Two canonical Hard problems asked in MLE interviews. MedianFinder: two heaps where lo is a max-heap (negated) storing the lower half, hi is a min-heap storing the upper half. The invariant ensures median is always O(1) after O(log n) inserts. LRUCache: Python's OrderedDict is a doubly-linked list + hash map built-in, making both get and put O(1).
Worked Interview Problems
3 problemsProblem
Given beginWord='hit', endWord='cog', wordList=['hot','dot','dog','lot','log','cog'], find the shortest transformation sequence length. Each step changes one letter and the result must be in wordList.
Solution
Model as a graph: each word is a node. Two words are connected if they differ by exactly one letter. BFS from beginWord finds the shortest path.
Build adjacency: for each word, generate all patterns with one wildcard (e.g., 'hit' โ '*it', 'h*t', 'hi*'). Group words by pattern. This avoids O(nยฒ) pairwise comparison.
BFS: queue starts with (beginWord, 1). Pop word, check all neighbors via patterns. If neighbor == endWord, return level. Mark visited to avoid cycles.
Python: from collections import deque. q = deque([(beginWord, 1)]). visited = {beginWord}. While q: word, steps = q.popleft(). For each pattern of word, for each neighbor in pattern_map[pattern]: if neighbor == endWord: return steps+1. If not visited: visited.add, q.append.
Time: O(Mยฒ ร N) where M = word length, N = number of words. Space: O(Mยฒ ร N) for the pattern map.
Answer
Return 5 for this example: hitโhotโdotโdogโcog. BFS guarantees shortest path. Key insight: wildcard pattern grouping reduces edge construction from O(NยฒรM) to O(NรMยฒ).
Common Mistakes
Off-by-one errors in binary search: use lo + (hi-lo)//2, not (lo+hi)//2 (overflow in other languages). Know exactly when to use lo <= hi vs lo < hi and when to set hi = mid vs hi = mid-1.
Forgetting to mark nodes visited in BFS/DFS before pushing to the queue (not after popping). This causes TLE from re-processing the same node multiple times.
Using recursion for DFS on very large graphs without converting to iterative โ Python's default recursion limit is 1000 and will throw RecursionError on large inputs. Use sys.setrecursionlimit or an explicit stack.
Wrong heap usage: Python's heapq is a min-heap. For max-heap, negate values on insert and negate back on pop. Forgetting this causes incorrect results in top-K or scheduling problems.
Not returning early in DP when the base case is hit, leading to index out of bounds errors.