Sequentially Ordinal Rank Tracker

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below
0
Stuck? Show a way to structure it+
  1. 01Clarify whether scores are unique and whether getRank is called sequentially.
  2. 02Keep the requested prefix in a min-heap and all remaining items in a max-heap.
  3. 03On add, place the score then rebalance so the prefix has exactly the requested size.
  4. 04On get, promote the best remaining score and return the prefix minimum.

Reference answer

Then expect these follow-ups

  • How would you support deleting an existing name?

    Tests: lazy deletion

  • How would you make rank requests arbitrary rather than sequential?

    Tests: order statistics

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Next question