Katkat
Back

Implement BST Iterator and Ticket Queue

MetaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement an iterator for a Binary Search Tree (BST) using controlled traversal, and your skill in designing a priority-based queue that handles multi-criteria ordering.

Part 1: BST Iterator

Implement an iterator class BSTIterator that iterates over a Binary Search Tree (BST) in-order.

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        pass
    def next(self) -> int:
        pass
    def hasNext(self) -> bool:
        pass
  • next() should return the next smallest number in the BST.
  • hasNext() should return True if there are still elements to visit.
  • Constraints: Your next() and hasNext() operations should run in average O(1) time, and the iterator should use O(h) memory, where h is the height of the tree.

Part 2: Ticket Queue

Design a system to manage support tickets. Each ticket is defined as a tuple (severity, timestamp, ticket_id).

Implement a class TicketQueue that supports:

  • add_ticket(severity, timestamp, ticket_id): Adds a ticket to the queue.
  • get_next_ticket(): Returns the ticket_id of the highest priority ticket. Priority is determined by:
    1. Higher severity (higher integer is more urgent).
    2. If severity is equal, lower timestamp (older tickets first).
    3. If severity and timestamp are equal, lower ticket_id (lexicographical/numerical order).

Example:

tq = TicketQueue()
tq.add_ticket(1, 100, "A")
tq.add_ticket(2, 50, "B")
tq.add_ticket(2, 50, "C")
# get_next_ticket() returns "B" (highest severity, then earliest timestamp, then lowest ID)

Hints

Hint 1

For the BST Iterator, use a stack to simulate the recursive in-order traversal by pre-processing the leftmost branch.

Hint 2

For the Ticket Queue, consider using a heap where the comparison logic is customized to prioritize severity (descending) and timestamp/ID (ascending).

Hint 3

In Python, if using `heapq`, you can invert the severity sign to leverage the min-heap to act as a max-heap for that specific attribute.

Follow-up questions

  • How would you modify the BST Iterator to support a 'peek' operation without advancing the iterator?
  • If the Ticket Queue required high concurrency, what locking mechanisms or data structures would you use to prevent race conditions during insertion?
  • How does the time complexity of the Ticket Queue operations change if you implement them using a sorted list instead of a heap?