Implement a Set Data Structure with a Resizable Array, Then Improve It with Hashing

Implement a set data structure from scratch. It stores distinct elements and supports: ```python class MySet: def add(self, x) -> bool: ... # True if x was inserted, False if already present def remove(self, x) -> bool: ... # True if x was removed, False if absent def contains(self, x) -> bool: ... def size(self) -> int: ... ``` You may not use the language's built-in set or hash map types. The backing storage is a fixed-length array that you allocate yourself. When the number of stored elements grows or shrinks enough, allocate a new array of a different length and move the elements. ### Constraints and Clarifications - Elements support equality comparison (for example, integers or strings). - The interviewer may ask for the solution in a specific language; the design should not depend on language-specific collection classes. ### Clarifying Questions - For the first version, should membership be found without hashing at all, or is hashing expected from the start? - When hashing is introduced, may you use the language's built-in hash code for an element, or must you write the hash function yourself? - Are `None` or null elements allowed? - Is there a memory target that should drive how aggressively the array grows and shrinks? ### Part 1 — Array-Backed Set With Resizing Implement the set on a resizable array without hashing. Explain your growth and shrink policy and the cost of each operation. ```hint Keep the live elements packed Think about how removal can avoid shifting many elements when the order of elements in a set does not matter. ``` ```hint Avoid resize thrashing Consider what happens if the array grows and shrinks at the same threshold and a caller alternates add and remove at that boundary. ``` #### What This Part Should Cover - Correct add, remove, contains, and size with duplicate rejection. - A growth and shrink policy with amortized analysis and a gap between the thresholds. - Time and space complexity for each operation. ### Part 2 — Faster Membership With Hashing Improve the design so that `contains`, `add`, and `remove` no longer scan every element, by turning an element's hash value into an array index. ```hint Two elements, one slot Decide what your structure does when two different elements map to the same index, and how that choice affects removal. ``` #### What This Part Should Cover - Mapping a hash value to an index and a collision strategy (chaining or open addressing), including correct deletion. - Load factor, rehashing on resize, and expected versus worst-case complexity. - How the hashing version compares with the array version for small sizes and for adversarial inputs. ### What a Strong Answer Covers - Clarifying which tools are allowed before writing code, then a clean and correct baseline. - Amortized resizing analysis with hysteresis to prevent thrashing. - A correct hash-based version, including collision handling, deletion, and rehashing. - Honest complexity statements for both versions, including the hash version's worst case. ### Follow-up Questions 1. How would you make the set safe to use from multiple threads, and what would the lock granularity be? 2. With open addressing, why can you not simply clear a slot on removal? 3. How would you iterate over the set while other threads add elements?