Linear-Probing Key-Value Store
Reported by candidates from Ease's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt at this Ease problem is treating delete like it empties a slot. It doesn't. Ease candidates reported this OA in September 2026, and it asks you to build a hash map from scratch with open addressing and linear probing, no built-in map, dict, or set allowed. Deleted slots have to stay searchable, and the table has to grow before it hits half full. If you wipe a slot on delete, later gets break on colliding keys. StealthCoder sits invisibly on your desktop as a safety net if you blank mid-assessment, but the tombstone idea below is the whole trick.
The problem
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.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The pattern is hash-table design. Use three states per slot: empty, occupied, and tombstone. On get, probe from hash(key) forward and stop only at an empty slot, skipping tombstones. On put, search the full probe chain first for an existing key and update it. If it's absent, reuse the first tombstone you passed, or the empty slot. On delete, mark a tombstone, never empty. The pitfall is stopping a search at a tombstone, or inserting a duplicate key past it. Another trap is negative keys, so normalize the modulo. Resize when used slots plus one would reach half the capacity. Count tombstones as used, then rehash only live entries. Keep it iterative and O(1) amortized for 100000 operations. If you freeze on the resize rules during the live OA, StealthCoder is the hedge that reads the problem and gives you a working version.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Linear-Probing Key-Value Store cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.
Get StealthCoderThis OA pattern shows up on LeetCode as design hashmap. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Ease's OA.
Ease reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Linear-Probing Key-Value Store FAQ
What's the trick in the Ease linear-probing key-value store?+
Tombstones. Deleting a key must mark the slot as deleted, not empty, so probe chains for other colliding keys stay intact. Searches skip tombstones and stop only at truly empty slots. Get this right and the rest is routine bookkeeping.
How do I handle negative keys in the hash function?+
Keys go down to -10^9, and in many languages the modulo of a negative number is negative. Normalize it with ((key % cap) + cap) % cap before indexing. Otherwise you'll get out-of-bounds errors or wrong probe starts on inputs like -3.
When exactly should the table grow?+
Grow when another insertion would make at least half the slots occupied. Count tombstones as occupied for this check, since they still lengthen probe chains. On resize, rehash only live entries into a larger table, which also clears the tombstones.
Can I use a built-in map to check my work?+
Not in the submitted solution. The problem bans built-in maps, dicts, and sets for entries. Locally, a throwaway comparison against a standard map on random operations is a fast way to catch tombstone bugs before you submit.
How do I prepare for this in 48 hours?+
Write the table once from memory with three slot states, then run the three examples by hand. Check the update-after-collision case and the delete-then-get case. Also test an insert that reuses a tombstone. That covers nearly every failure mode here.