Construct a BST and read spiral order
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
The coding round reportedly included two algorithmic tasks:
1. **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.
2. **Traverse a matrix in clockwise layers**
- You are given an `m x n` integer 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.
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.