FastPrepAll O(1) Data Structure
Problems/All O(1) Data Structure

All O(1) Data Structure

Airbnb logoAirbnb● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb software engineer intern technical interview in India in 2022. The task was to build a structure that keeps a count for each string, can raise or lower a count, and can return a string with the largest or smallest count. The goal was O(1) time for every call. The candidate first reached O(log n) and got to O(1) after a hint, and pseudocode was fine.

The report points to the well-known version of this problem, which accepts any key on a tie. Here, a tie goes to the key whose count changed longest ago, so every answer is fixed. You get the calls as a list of operations instead of a class, and you return only the answers of the get calls.

Our version is about 90% the same as the reported question.

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]: add 1 to the count of key. A new key starts with count 1.
  • ["dec", key]: take 1 from the count of key. If the count becomes 0, remove key.
  • ["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 <= 10
  • key contains only lowercase English letters.
  • Every dec call 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 Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)

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)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public String[] runAllOne(String[][] operations) {
      // Write your code here.
    }
}
Checking account…