All O'one Data Structure

HardDesigndesign

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 structure that stores string keys with positive integer counts and can report a key with the **largest** and the **smallest** count. - AllOne() creates an empty structure. - inc(key) adds 1 to key's count, inserting it with count 1 if it is not present. - dec(key) subtracts 1 from key's count. If the count reaches 0, the key is removed. dec is only called on keys that are present. - getMaxKey() returns a key with the highest count, or "" if the structure is empty. - getMinKey() returns a key with the lowest count, or "" if the structure is empty. **Tie-breaking:** when several keys share the highest (or lowest) count, return the **lexicographically smallest** of them. inc and dec should run in O(1) average time; the getters may additionally spend time proportional to the number of keys tied at that count.

Examples

Input: ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"] [[],["red"],["red"],[],[],["blue"],[],[]]
Output: [null,null,null,"red","red",null,"red","blue"]
With only `red` present it is both max and min. After `blue` arrives with count 1, `red` (2) is the max and `blue` (1) the min.
Input: ["AllOne","getMaxKey","inc","inc","getMinKey","dec","getMaxKey","dec","getMinKey"] [[],[],["b"],["a"],[],["a"],[],["b"],[]]
Output: [null,"",null,null,"a",null,"b",null,""]
An empty structure returns an empty string. `a` and `b` tie at count 1, so the smaller key `a` is returned. Decrementing removes keys at count 1.

Constraints

  • `1 <= key.length <= 10`, and `key` consists of lowercase English letters.
  • `dec` is only called on a key that is currently present.
  • At most 5 * 10^4 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 design problems