FastPrepLinear-Probing Key-Value Store

Linear-Probing Key-Value Store

Ease logoEase● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Implement an integer key-value store without using a built-in map, dictionary, or set for its entries.

Process the parallel arrays from left to right. put inserts or replaces a value, get appends the stored value or -1, and delete removes a key when present. Return the results of all get operations.

Store entries in an open-addressed table with linear probing. Deleted slots must remain searchable, and the table must grow when another insertion would make at least half its slots occupied.

Function

runLinearProbingStore(operations: String[], keys: int[], values: int[]) → int[]

Examples

Example 1

operations = ["put","put","get","put","get","delete","get"]keys = [1,9,9,1,1,9,9]values = [10,90,0,11,0,0,0]return = [90,11,-1]

Updates preserve the key, and deleting a colliding key removes only that entry.

Example 2

operations = ["get","put","get","delete","get"]keys = [-3,-3,-3,-3,-3]values = [0,7,0,0,0]return = [-1,7,-1]

A missing key returns -1 before insertion and again after deletion.

Example 3

operations = ["put","put","put","get","get","get"]keys = [0,8,16,0,8,16]values = [4,5,6,0,0,0]return = [4,5,6]

Keys that initially share a probe sequence remain distinct.

Constraints

  • 1 <= operations.length == keys.length == values.length <= 100000.
  • Every operation is put, get, or delete.
  • -10^9 <= keys[i] <= 10^9 and stored values are between 0 and 10^9.
  • values[i] is ignored for get and delete.
See Ease hiring insights
public int[] runLinearProbingStore(String[] operations, int[] keys, int[] values) {
    // Write your solution here.
}
operations["put","put","get","put","get","delete","get"]
keys[1,9,9,1,1,9,9]
values[10,90,0,11,0,0,0]
expected[90,11,-1]
Checking account…