Resizable Hash Map
Updated
Problem statement
Build a hash map from scratch that grows as it fills up. Implement a class ResizableHashMap that maps integer keys to integer values:
ResizableHashMap()creates an empty map with 8 buckets.void put(int key, int value): ifkeyis already in the map, replace its value. Otherwise add the new pair, and then, if the number of keys is now more than three quarters of the number of buckets (that is,4 · size > 3 · buckets), double the number of buckets and place every pair again.int get(int key): return the value stored forkey, or-1ifkeyis not in the map.void remove(int key): removekeyand its value if it is in the map. The number of buckets never shrinks.int capacity(): return the current number of buckets.
To test your class, you get operations, the calls made in order on one new map, and operands, the arguments of each call. Return one string per call: "null" for put and remove, and the returned number in normal decimal form for get and capacity.
The judge only checks the returned strings. The point of the exercise is to store the pairs in your own array of buckets instead of a built-in hash table; how you arrange pairs inside the buckets is up to you.
Function
runHashMap(operations: String[], operands: int[][]) → String[]Examples
Example 1
operations = ["put","put","get","put","get","remove","get","capacity"]operands = [[1,10],[2,20],[1],[1,15],[1],[2],[2],[]]return = ["null","null","10","null","15","null","-1","8"]After the two put calls the map holds 1 → 10 and 2 → 20, so get(1) is "10". put(1, 15) only replaces the value, so the next get(1) is "15". After remove(2), get(2) is "-1". The map never held more than 2 keys, and 4 · 2 = 8 is not more than 3 · 8 = 24, so it still has 8 buckets.
Example 2
operations = ["put","put","put","put","put","put","capacity","put","capacity","get"]operands = [[0,0],[1,100],[2,200],[3,300],[4,400],[5,500],[],[6,600],[],[3]]return = ["null","null","null","null","null","null","8","null","16","300"]After six new keys, 4 · 6 = 24 is not more than 3 · 8 = 24, so capacity() is still "8". The seventh new key makes 4 · 7 = 28 > 24, so the map doubles to 16 buckets and moves every pair. The pairs are still found after the move: get(3) is "300".
Example 3
operations = ["put","put","put","put","put","put","put","capacity","remove","remove","capacity","get","put","capacity"]operands = [[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[3,99],[],[1],[2],[],[3],[7,7],[]]return = ["null","null","null","null","null","null","null","8","null","null","8","99","null","8"]Six new keys fit in 8 buckets. put(3, 99) changes the value of a key that is already there, so the number of keys stays 6 and nothing grows. Removing keys 1 and 2 leaves 4 keys, and the map keeps its 8 buckets because it never shrinks. get(3) is "99". Adding key 7 makes 5 keys, and 4 · 5 = 20 is not more than 24, so there are still 8 buckets.
Constraints
1 <= operations.length <= 2000andoperands.length == operations.length- Each operation is
"put","get","remove"or"capacity". operands[i]is[key, value]forput,[key]forgetandremove, and[]forcapacity.0 <= key, value <= 10^6
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
- Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Insert Delete GetRandom O(1)Charta Health · PHONE SCREENCharta Health interview questions
- Portfolio Tickers with Constant-Time Random PickCitadel · PHONE SCREENCitadel interview questions
- Build a Pivot Table with TotalsSigma Computing · PHONE SCREEN
- Process On-Call Routing OperationsOpenAI · PHONE SCREENOpenAI interview questions
- Stateful Paginated Fetch NLyft · PHONE SCREENLyft interview questions
- Linear-Probing Key-Value StoreEase · PHONE SCREEN
- Escape Room LeaderboardPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Role-Based Network Access ControlOkta · PHONE SCREENOkta interview questions
- Track Package Receipt GapsAmazon · PHONE SCREEN
- Transformer KV Cache OperationsNVIDIA · PHONE SCREENNVIDIA interview questions