First Unique Number

MediumDesignhashing

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

Implement FirstUnique(nums), which starts from the stream of integers nums and supports appending more values. - showFirstUnique() returns the earliest value in the stream (in arrival order) that has appeared **exactly once** so far, or -1 if there is no such value. - add(value) appends value to the end of the stream. A value that appears a second time is disqualified forever, even if it arrived early.

Examples

Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[4,4,7]],[],[9],[],[7],[],[9],[]]
Output: [null,7,null,7,null,9,null,-1]
4 is repeated, so 7 is the first unique. Adding 9 does not change that. A second 7 promotes 9. A second 9 leaves no unique value.
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[3]],[],[3],[],[8],[]]
Output: [null,3,null,-1,null,8]
3 is unique until it appears again. Then 8 becomes the only unique value.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i], value <= 10^8
  • At most 5 * 10^4 calls to `showFirstUnique` and `add`

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 hashing problems