Smallest Number in Infinite Set

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

You start with a set containing **every positive integer** 1, 2, 3, .... - SmallestInfiniteSet() creates the full set. - popSmallest() removes the smallest integer in the set and returns it. - addBack(num) puts the positive integer num back into the set. If num is already in the set, nothing happens. Because the set is infinite, popSmallest always has something to return.

Examples

Input: ["SmallestInfiniteSet","popSmallest","popSmallest","addBack","addBack","popSmallest","popSmallest","addBack","popSmallest","popSmallest"] [[],[],[],[1],[5],[],[],[2],[],[]]
Output: [null,1,2,null,null,1,3,null,2,4]
Adding back 5 does nothing because 5 was never removed. After 1 is returned again, the smallest remaining number is 3. Then 2 is added back and popped before 4.
Input: ["SmallestInfiniteSet","addBack","popSmallest","addBack","addBack","popSmallest","popSmallest"] [[],[3],[],[1],[1],[],[]]
Output: [null,null,1,null,null,1,2]
Adding back a number twice only inserts it once, so 1 is returned once and then 2.

Constraints

  • `1 <= num <= 1000`
  • At most 1000 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