Call History Manager
Updated
Problem statement
Build the call history of a phone. Each entry stores a caller's name and phone number. The history lists calls in time order and keeps only one entry per person: the one for their latest call. A phone number identifies a person. The history starts empty and holds at most capacity people.
You are given a list of operations. Run them in order:
["call", name, phone]: a call arrives fromphone. Ifphonealready has an entry, remove it. Then addphonewith thisnameas the newest entry. If the history now holds more thancapacitypeople, remove the entry with the oldest call.["get", phone]: give the name stored forphone, or""ifphonehas no entry. A lookup does not change the order of the history.
Return the answers of all get operations, in order.
Try to make every operation run in O(1) average time.
Function
runCallHistory(capacity: int, operations: String[][]) → String[]Examples
Example 1
capacity = 2operations = [["call","alice","5550100001"],["call","bob","5550100002"],["get","5550100001"],["call","carol","5550100003"],["get","5550100001"],["get","5550100002"]]return = ["alice","","bob"]After two calls the history holds alice (older) and bob (newer). Looking up "5550100001" gives "alice" and does not change the order.
The call from carol makes 3 people, more than capacity = 2, so the oldest entry, alice, is dropped. Now "5550100001" is not in the history and gives "", while "5550100002" still gives "bob".
Example 2
capacity = 2operations = [["call","alice","5550100001"],["call","bob","5550100002"],["call","ali","5550100001"],["call","dan","5550100004"],["get","5550100002"],["get","5550100001"],["get","5550100004"]]return = ["","ali","dan"]The third call comes from "5550100001" again, now with the name ali. Its old entry is replaced, so the history holds bob (older) and ali (newer).
The call from dan makes 3 people, so the oldest entry, bob, is dropped. The lookups give "" for bob's number, "ali" for "5550100001" and "dan" for "5550100004".
Example 3
capacity = 1operations = [["get","5550100009"],["call","erin","5550100005"],["call","erin","5550100005"],["get","5550100005"]]return = ["","erin"]The first lookup runs on an empty history, so it gives "". erin then calls twice from the same number. The second call replaces the first entry, so the history still holds one person and nothing is dropped. The last lookup gives "erin".
Constraints
1 <= capacity <= 1041 <= operations.length <= 104- Each
operations[i]is["call", name, phone]or["get", phone]. 1 <= name.length <= 10, andnamecontains only lowercase English letters.phoneis made of exactly10digits.
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
- Russian Doll EnvelopesONSITE INTERVIEW · Seen Sep 2022
- All O(1) Data StructureONSITE INTERVIEW · Seen Jul 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
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheServiceNow · PHONE SCREEN · ONSITE INTERVIEWServiceNow interview questions
- LRU CacheLotusFlare · ONSITE INTERVIEW
- LRU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- LRU Cache OperationsHevo Data · ONSITE INTERVIEW
- LRU Cache OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- LRU Cache Operation SequenceGoogle · ONSITE INTERVIEWGoogle interview questions
- Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- LRU CacheAMD · ONSITE INTERVIEWAMD interview questions
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple 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)