Implement BST Iterator and Ticket Queue
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
The coding interviews mentioned two algorithm/data-structure tasks:
1. **Implement a binary search tree iterator.**
You are given the root of a binary search tree. Design an iterator that supports:
- `hasNext()` -> returns whether there is another value to visit
- `next()` -> returns the next smallest value in the tree
The iterator must return values in ascending order. Aim for `O(h)` extra space, where `h` is the height of the tree, and amortized `O(1)` time per operation.
2. **Maintain a prioritized ticket queue with updates.**
Build a data structure for support tickets. Each ticket has:
- `ticket_id`: unique integer
- `severity`: one of `low`, `medium`, or `high`
- `t`: integer timestamp, where larger means more recent
Support the following operations efficiently:
- `upsert(ticket_id, severity, t)`: insert a new ticket or update an existing ticket
- `get_top_ticket()`: return the highest-priority ticket
Priority rules:
1. Higher severity comes first (`high > medium > low`)
2. If severity is the same, the more recent ticket (`t` larger) comes first
3. If there is still a tie, return the smaller `ticket_id`
Return `-1` if no tickets exist.
Quick Answer: This question evaluates understanding of binary search tree traversal and iterator design with amortized time and space analysis, as well as dynamic priority-queue design for maintaining ordered tickets with severity, recency, and tie-breaking rules.