Katkat
Back

Implement a Priority Queue from Scratch with Custom Ordering and Stable Ties

MicrosoftSoftware Engineer · Other
MediumSoftware EngineerOtherSoftware Engineering Fundamentals

Last updated

Data structures question that asks you to build a priority queue from scratch with insert, peek, remove-top and size operations, a caller-supplied ordering and stable ties. It tests the choice of underlying structure, invariant-preserving insertion and removal, complexity analysis and edge-case handling.

Implement a priority queue yourself, without using the language's built-in heap module or priority-queue class. It must support:

  • push(item): add an item.
  • peek(): return the highest-priority item without removing it.
  • pop(): remove and return the highest-priority item.
  • a size query and an emptiness check.

Choose the underlying data structure, implement the operations, and state the time and space complexity of each. For practice, treat "highest priority" as "smallest key" by default and let the caller supply the ordering, so the same class can serve as a max-queue or order records by one of their fields.

Constraints and Clarifications

  • Plain arrays or lists and basic language features are allowed; library heaps and priority queues are not.
  • Calling peek or pop on an empty queue must fail in a defined, documented way.
  • Duplicate priorities are allowed.

Clarifying Questions

  • Should items with equal priority leave in the order they were inserted?
  • Will callers need to change an item's priority, or remove an arbitrary item, after inserting it?
  • Will several threads share the same queue?
  • Is the queue ever built from a large existing collection in one go?

Hints

Hint 1

Keep only the best in place: Look for a structure that always knows where the best element is without keeping everything else fully sorted.

Hint 2

Test the boundaries: Dry-run a removal when only one or two items remain, and when two candidates for the top have equal priority.

Follow-up questions

  • How would you support changing the priority of an item that is already in the queue?
  • How can you build the queue from an existing list of n items faster than n separate inserts, and why is that bound linear?
  • How would you make the queue safe for several producer and consumer threads, with consumers waiting while it is empty?
  • When would a heap with more than two children per node outperform a binary one?