How should I practice Hash Map with Separate Chaining?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Applied Intuition onsite interview problems in FastPrep.

Is Hash Map with Separate Chaining associated with Applied Intuition?

FastPrep tags this as a Applied Intuition onsite interview coding practice problem when the problem catalog has that company and stage context.

Hash Map with Separate Chaining

Applied Intuition● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Implement a hash map with integer keys and integer values, similar to C++ unordered_map, without using a built-in map, dictionary or hash table. Resolve collisions with separate chaining: the map has an array of buckets, and each bucket keeps a chain (a list) of every entry whose key lands in it.

The map starts empty with 8 buckets. When the map has b buckets, key k goes to bucket ((k mod b) + b) mod b, so a negative key also lands in a bucket from 0 to b - 1.

Process commands in order. Each command is one of:

PUT k v: store value v for key k. If k is already in the map, replace its value. Prints nothing.
GET k: print the value stored for k, or NULL if k is not in the map.
ERASE k: remove k. Print 1 if it was in the map and 0 otherwise.
SIZE: print the number of keys in the map.
BUCKET_COUNT: print the current number of buckets.
BUCKET_SIZE i: print how many entries are in bucket i.

Growth: when a PUT adds a new key and the number of keys becomes greater than the number of buckets, double the number of buckets and move every entry to its bucket under the new count. Replacing a value or erasing a key never changes the number of buckets.

Return the printed lines in order.

Interviewer Follow-ups

The interview went on to discuss how to make the map safe to use from several threads, and how to turn it into a distributed key-value store. These follow-ups are for discussion; the tests check only the printed lines.

Function

processHashMapCommands(commands: String[]) → String[]

Examples

Example 1

commands = ["PUT 1 10","PUT 9 90","GET 1","GET 9","BUCKET_SIZE 1","ERASE 1","GET 1","BUCKET_SIZE 1","SIZE"]return = ["10","90","2","1","NULL","1","1"]

The map starts with 8 buckets. Keys 1 and 9 both go to bucket 1, so they share one chain and BUCKET_SIZE 1 prints 2. Erasing key 1 prints 1, after which GET 1 prints NULL, bucket 1 holds one entry and the map holds one key.

Example 2

commands = ["PUT 0 0","PUT 1 1","PUT 2 2","PUT 3 3","PUT 4 4","PUT 5 5","PUT 6 6","PUT 7 7","BUCKET_COUNT","BUCKET_SIZE 0","PUT 8 8","BUCKET_COUNT","BUCKET_SIZE 0","BUCKET_SIZE 8","SIZE"]return = ["8","1","16","1","1","9"]

Eight keys fit in 8 buckets, so the count is still 8 and key 0 is alone in bucket 0. Adding key 8 makes 9 entries, more than 8 buckets, so the map doubles to 16 buckets and moves every entry. Key 8 now goes to bucket 8 instead of sharing bucket 0, so both buckets hold 1 entry.

Example 3

commands = ["PUT -1 5","PUT 7 3","PUT -1 6","SIZE","BUCKET_SIZE 7","GET -1","ERASE 4","BUCKET_COUNT"]return = ["2","2","6","0","8"]

Key -1 goes to bucket ((-1 mod 8) + 8) mod 8 = 7, the same bucket as key 7. The second PUT -1 only replaces the value, so the map still holds 2 keys, bucket 7 holds 2 entries and GET -1 prints 6. Key 4 is absent, so ERASE 4 prints 0, and the bucket count stays 8.

Constraints

1 <= commands.length <= 2000
Each command has one of the six forms above, with single spaces between its parts.
-10^9 <= k, v <= 10^9, written as plain decimal integers (no plus sign, no leading zeros, and no -0).
For BUCKET_SIZE i, 0 <= i < the bucket count at that moment.