Coding questions · Meta
Construct a BST and read spiral order
This question evaluates proficiency in data structures and algorithm design by testing binary search tree reconstruction from a preorder sequence and matrix spiral (clockwise layer) traversal.
The coding round reportedly included two algorithmic tasks:
-
Rebuild a binary search tree from a preorder sequence
- You are given an array of distinct integers representing the preorder traversal of a binary search tree.
- Reconstruct the original tree and return its root.
- Aim for a solution that runs in linear time.
-
Traverse a matrix in clockwise layers
- You are given an
m x ninteger matrix. - Return all elements in the order obtained by repeatedly visiting the current outer boundary clockwise and then shrinking the boundary until every cell has been visited.
- You are given an
Rebuild BST From Preorder
Return a nested [value,left,right] BST reconstructed from distinct preorder values.
Examples
Example 1
Input: ([8,5,1,7,10,12],)
Output: [8, [5, [1, None, None], [7, None, None]], [10, None, [12, None, None]]]
Explanation: Rebuild BST from preorder using bounds.
Example 2
Input: ([],)
Output: None
Explanation: Empty preorder returns None.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Clockwise Matrix Layer Traversal
Return matrix elements in clockwise spiral layer order.
Examples
Example 1
Input: ([[1,2,3],[4,5,6],[7,8,9]],)
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation: Clockwise layer traversal.
Example 2
Input: ([[1,2,3,4]],)
Output: [1, 2, 3, 4]
Explanation: Single row works.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.