Deleting from an open-addressed table is the operation that goes wrong. Emptying the slot cuts the probe sequence of every key stored behind it, and those keys become unreachable. The cure is a tombstone: a mark meaning "something used to live here, keep walking", which a later insertion may overwrite.
Write tombstones(ops, m) for a table with linear probing (step = 1). Each operation is a pair:
("add", key)— walk the probe sequence and put the key in the first tombstone or empty slot;("del", key)— walk until the key is found and leave a tombstone there, or until an empty slot says it was never stored;("find", key)— walk until the key is found, or an empty slot ends the search.
Return the list of find answers, as booleans, in order.
Examples
Input: ops = [("add", 1), ("add", 4), ("del", 1), ("find", 4), ("find", 7)], m = 3
Output: [True, False]
Explanation: 4 lives in slot 2 behind 1. The tombstone in slot 1 keeps it reachable; the search for 7 stops at the empty slot 0.
Input: ops = [("add", 2), ("del", 2), ("find", 2)], m = 4
Output: [False]
Constraints
1 <= m <= 10**4,0 <= len(ops) <= 10**5,0 <= key <= 10**9- An
addis never given a key the table already holds, and the table never fills up.
Goals
- See why clearing a slot in an open-addressed table loses other keys
- Mark a removed slot so a probe walks past it but an insert may reuse it
- Keep lookups correct after any mixture of adds and deletes