FastPrepSeparate-Chaining Hash Table

Separate-Chaining Hash Table

Microsoft logoMicrosoft● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Implement an integer key/value hash table using separate chaining. The table starts empty and has bucketCount fixed buckets. Map a key to bucket ((key % bucketCount) + bucketCount) % bucketCount; each bucket stores its own collection of key/value entries. Do not use a built-in map or dictionary for the implementation.

Process operations in order and return one integer result per operation:

  • [0, key, value]: put the value; return 1 for a new key and 0 for an overwritten key.
  • [1, key]: get its current value, or -1 when absent.
  • [2, key]: remove the key; return 1 if present and 0 otherwise.

Different keys in the same bucket must coexist. Overwriting a key does not add a second entry. The bucket count does not change.

Function

processChainedHashTable(bucketCount: int, operations: int[][]) → int[]

Examples

Example 1

bucketCount = 2operations = [[0,1,10],[0,3,30],[1,1],[0,1,12],[1,1],[2,3],[1,3]]return = [1,1,10,0,12,1,-1]

Keys 1 and 3 collide but remain separate; overwriting 1 changes its value without inserting a duplicate.

Example 2

bucketCount = 2operations = [[0,-1,5],[0,1,8],[1,-1],[2,-1],[1,1]]return = [1,1,5,1,8]

Normalize the negative key into a valid bucket and preserve the other colliding key after removal.

Example 3

bucketCount = 5operations = [[1,42],[2,42]]return = [ -1,0 ]

A missing get returns -1 and a missing remove returns 0.

Constraints

  • 1 <= bucketCount <= 1000.
  • 0 <= operations.length <= 10000.
  • Every operation has one of the three stated forms.
  • -1000000 <= key <= 1000000; 0 <= value <= 1000000.

More Microsoft problems

See Microsoft hiring insights
public int[] processChainedHashTable(int bucketCount, int[][] operations) {
    // Write your code here
}
bucketCount2
operations[[0,1,10],[0,3,30],[1,1],[0,1,12],[1,1],[2,3],[1,3]]
expected[1,1,10,0,12,1,-1]
Checking account…