Construct a BST and read spiral order
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: 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.
Rebuild BST From Preorder
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([8,5,1,7,10,12],)
Expected Output: [8, [5, [1, None, None], [7, None, None]], [10, None, [12, None, None]]]
Explanation: Rebuild BST from preorder using bounds.
Input: ([],)
Expected Output: None
Explanation: Empty preorder returns None.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Clockwise Matrix Layer Traversal
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,2,3],[4,5,6],[7,8,9]],)
Expected Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation: Clockwise layer traversal.
Input: ([[1,2,3,4]],)
Expected Output: [1, 2, 3, 4]
Explanation: Single row works.
Input: ([],)
Expected Output: []
Explanation: Empty matrix returns empty output.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.