Trees, Linked Lists, And Pointer Algorithms
Asked of: Machine Learning Engineer
Last updated
What's being tested
These problems test pointer-based traversal, in-place state updates, and edge-case-safe algorithm implementation across trees, linked lists, and numeric routines. For an MLE, the signal is whether you can write production-quality code for core data structures without relying on library shortcuts.
Patterns & templates
-
Fast exponentiation — implement
`pow`(x,n) with exponent halving inO(log n)time; handlen < 0,INT_MIN,x == 0. -
Floyd cycle detection — use
slowandfastpointers; after collision, reset one pointer toheadto find cycle entry inO(n). -
Tree level traversal — use
queueBFS for left-side view; first node per level is answer,O(n)time andO(width)space. -
DFS with depth tracking — pre-order left-first recursion records first value at each depth; simpler code, but stack can hit
O(height). -
In-order successor with parent pointers — if right child exists, return leftmost right subtree; otherwise climb until leaving a left edge.
-
Perfect binary tree neighbor linking — use already-established
nextpointers level by level; achieveO(n)time andO(1)extra space. -
Constant-time board state tracking — maintain row, column, diagonal counters; update each move in
O(1)instead of rescanningn×n.
Common pitfalls
Pitfall: Treating negative exponents as
1 / pow(x, -n)can overflow forINT_MIN; cast tolongbefore negation.
Pitfall: For tree views, confusing “leftmost node per level” with “always follow left children” fails on missing-child and skewed cases.
Pitfall: In linked-list cycle detection, stopping at the meeting point gives only cycle existence, not the cycle entry.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Tree And Linked Structure AlgorithmsCoding & Algorithms
- Trees, Recursion, And BST TraversalCoding & Algorithms
- Trees, Tries, and Hierarchical DataCoding & Algorithms
- Trees And Hierarchical StructuresCoding & Algorithms
- Linked Lists, Stacks, Caches, And Pointer TechniquesCoding & Algorithms
- Linked Lists, Pointers, Caches, And In-Memory StoresCoding & Algorithms