Design a Number Container System

MediumHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Design a system of numbered containers, where each container index holds at most one number. - NumberContainers() creates a system with every container empty. - change(index, number) puts number into container index. If the container already holds a number, that number is replaced. - find(number) returns the **smallest index** of a container currently holding number, or -1 if no container holds it. Indices can be very large, so do not allocate an array over the index range.

Examples

Input: ["NumberContainers","find","change","change","find","change","find","find"] [[],[7],[4,7],[9,7],[7],[4,3],[7],[3]]
Output: [null,-1,null,null,4,null,9,4]
Containers 4 and 9 both hold 7, so `find(7)` is 4. After container 4 switches to 3, the smallest index holding 7 is 9.
Input: ["NumberContainers","change","change","change","find","change","find","find"] [[],[1,5],[1,5],[1,6],[5],[1,5],[5],[6]]
Output: [null,null,null,null,-1,null,1,-1]
Container 1 is overwritten several times; only its current number counts.

Constraints

  • `1 <= index, number <= 10^9`
  • At most 10^5 calls in total.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems