How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Implement BST Iterator and Ticket Queue

Quick Overview

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.

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.

BST Iterator Operation Simulation

Given BST level-order values and iterator operations, return outputs for next and hasNext in operation order.

Constraints

Inputs are Python literals matching the function signature.
Return a deterministic exact-match value.

Examples

Input: ([7,3,15,None,None,9,20], ["next","next","hasNext","next","hasNext","next","hasNext"] )

Expected Output: [3, 7, True, 9, True, 15, True]

Explanation: Iterator visits values in ascending order.

Input: ([], ["hasNext"])

Expected Output: [False]

Explanation: Empty tree.

Input: ([2,1,3], ["hasNext","next","next","next","hasNext"])

Expected Output: [True, 1, 2, 3, False]

Explanation: Full traversal.

Hints

Pick a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.

Prioritized Ticket Queue with Updates

Process upsert and get_top_ticket operations. Priority is severity, then newer timestamp, then smaller ticket id.

Constraints

Inputs are Python literals matching the function signature.
Return a deterministic exact-match value.

Examples

Input: ([['get_top_ticket'], ['upsert', 10, 'low', 5], ['upsert', 2, 'high', 3], ['get_top_ticket'], ['upsert', 10, 'high', 9], ['get_top_ticket']],)

Expected Output: [-1, None, None, 2, None, 10]

Explanation: Updates change priority.

Input: ([['upsert', 2, 'medium', 7], ['upsert', 1, 'medium', 7], ['get_top_ticket']],)

Expected Output: [None, None, 1]

Explanation: Tie breaks by smaller id.

Hints

Pick a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.

Quick Overview