All O(1) Data Structure
Updated
Problem statement
Build a structure that keeps a count for each string key. It starts empty. You are given a list of operations. Run them in order:
["inc", key]: add1to the count ofkey. A new key starts with count1.["dec", key]: take1from the count ofkey. If the count becomes0, removekey.["getMaxKey"]: give a key with the largest count, or""if there are no keys.["getMinKey"]: give a key with the smallest count, or""if there are no keys.
If several keys tie for the largest or the smallest count, give the one whose last inc or dec call came earliest.
Return the answers of all getMaxKey and getMinKey calls, in the order the calls were made.
Try to make every call run in O(1) average time.
Function
runAllOne(operations: String[][]) → String[]Examples
Example 1
operations = [["inc","a"],["inc","b"],["inc","b"],["getMaxKey"],["getMinKey"],["inc","a"],["getMaxKey"],["dec","b"],["getMinKey"]]return = ["b","a","b","b"]After the first three calls, "a" has count 1 and "b" has count 2, so getMaxKey returns "b" and getMinKey returns "a".
Then "a" also reaches count 2. Both keys tie for the largest count. The last change to "b" came before the last change to "a", so getMaxKey returns "b".
Finally dec lowers "b" to count 1, the only smallest count, so getMinKey returns "b".
Example 2
operations = [["getMaxKey"],["inc","x"],["dec","x"],["getMinKey"]]return = ["",""]The first getMaxKey runs before any key exists, so it returns "". "x" is added and then lowered to count 0, which removes it. The structure is empty again, so getMinKey also returns "".
Example 3
operations = [["inc","c"],["inc","d"],["inc","e"],["getMinKey"],["inc","c"],["getMinKey"],["getMaxKey"],["dec","c"],["getMinKey"],["getMaxKey"]]return = ["c","d","c","d","d"]"c", "d" and "e" all have count 1. "c" changed first, so getMinKey returns "c".
Then "c" goes up to count 2. Now "d" and "e" share the smallest count, and "d" changed first, so getMinKey returns "d". getMaxKey returns "c".
After dec, all three keys have count 1 again. "c" just changed, so "d" is now the key that changed longest ago. Both get calls return "d".
Constraints
1 <= operations.length <= 5 * 104- Each
operations[i]is["inc", key],["dec", key],["getMaxKey"]or["getMinKey"]. 1 <= key.length <= 10keycontains only lowercase English letters.- Every
deccall is for a key that is in the structure.
More Airbnb interview questions
- Shortest Uncommon SubstringONSITE INTERVIEW · Seen Nov 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Superhost EligibilityONSITE INTERVIEW · Seen Sep 2026
- Call History ManagerONSITE INTERVIEW · Seen Sep 2022
- Russian Doll EnvelopesONSITE INTERVIEW · Seen Sep 2022
- Cheapest Flight with Its PathOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Alien DictionaryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2019
- Task Management SystemOA · Seen Nov 2026
- Recipe Management SystemOA · Seen Nov 2026
- Progressive Banking SystemOA · Seen Nov 2026
Similar questions at other companies
- LFU CacheAmazon · ONSITE INTERVIEW
- LFU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- LFU CacheSnowflake · OA · ONSITE INTERVIEWSnowflake interview questions
- LRU Cache with TTLAutodesk · ONSITE INTERVIEWAutodesk interview questions
- Recover a Function-Call LRU Cache with a Write-Ahead LogAnthropic · ONSITE INTERVIEWAnthropic interview questions
- LFU CacheSalesforce · ONSITE INTERVIEWSalesforce interview questions
- LFU CacheBlinkit · ONSITE INTERVIEWBlinkit interview questions
- Thread-Safe LRU Cache with TTLLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Fair Multi-Tenant CacheOkta · ONSITE INTERVIEWOkta interview questions
- LFU CacheZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)