Add, Remove, and Find Values in a Bounded Integer Universe
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a set that supports adding, removing, and searching integer values from a known bounded range.
Implement `bounded_set(limit: int, operations: string[][]) -> bool[]`. Each operation is `[action,value]`, with action `ADD`, `REMOVE`, or `CONTAINS` and value represented as a decimal string. Return one boolean per operation.
### Constraints & Assumptions
The source emphasizes that the hidden bounded-value range makes a simpler bucket/direct-address representation possible. This practice contract states that range explicitly and defines set semantics where duplicate behavior was unreported.
- `1 <= limit <= 1000000`; every value satisfies `0 <= value < limit`.
- At most 200000 operations. The set is initially empty.
- ADD returns true if it inserted a previously absent value, false if already present.
- REMOVE returns true if it removed a present value, false if absent.
- CONTAINS returns whether the value is currently present.
- Use O(limit) state and support each operation in worst-case O(1) time after initialization. Account separately for initializing that state.
### Example
```text
limit = 5
operations = [["ADD","2"],["ADD","2"],["CONTAINS","2"],
["REMOVE","2"],["CONTAINS","2"],["REMOVE","2"]]
result = [true,false,true,true,false,false]
```
Explain why the known range changes the data-structure choice and what you would use if values were sparse across an enormous or unknown universe. Clarify the distinction between membership and maintaining sorted iteration.
```hint Use the contract before adding machinery
Every possible value has a valid small array index. Decide what one bit or boolean at that index should represent.
```
Overview: Implement constant-time bounded-integer set operations with direct addressing, explicit duplicate semantics, initialization cost, and sparse-universe tradeoffs.
Implement a set that supports adding, removing, and searching integer values from a known bounded range.
Implement `bounded_set(limit: int, operations: string[][]) -> bool[]`. Each operation is `[action,value]`, with action `ADD`, `REMOVE`, or `CONTAINS` and value represented as a decimal string. Return one boolean per operation.
### Constraints & Assumptions
The source emphasizes that the hidden bounded-value range makes a simpler bucket/direct-address representation possible. This practice contract states that range explicitly and defines set semantics where duplicate behavior was unreported.
- `1 <= limit <= 1000000`; every value satisfies `0 <= value < limit`.
- At most 200000 operations. The set is initially empty.
- ADD returns true if it inserted a previously absent value, false if already present.
- REMOVE returns true if it removed a present value, false if absent.
- CONTAINS returns whether the value is currently present.
- Use O(limit) state and support each operation in worst-case O(1) time after initialization. Account separately for initializing that state.
### Example
```text
limit = 5
operations = [["ADD","2"],["ADD","2"],["CONTAINS","2"],
["REMOVE","2"],["CONTAINS","2"],["REMOVE","2"]]
result = [true,false,true,true,false,false]
```
Explain why the known range changes the data-structure choice and what you would use if values were sparse across an enormous or unknown universe. Clarify the distinction between membership and maintaining sorted iteration.
```hint Use the contract before adding machinery
Every possible value has a valid small array index. Decide what one bit or boolean at that index should represent.
```
Constraints
- 1 <= limit <= 1000000; every decimal-string value represents an integer in [0,limit).
- At most 200000 operations, each [ADD,value], [REMOVE,value] or [CONTAINS,value].
- The set begins empty. ADD reports a new insertion, REMOVE reports an existing removal, and CONTAINS reports membership.
- Return one boolean per operation; use direct bounded state with worst-case constant-time set access after initialization.
Examples
Input: (5, [['ADD', '2'], ['ADD', '2'], ['CONTAINS', '2'], ['REMOVE', '2'], ['CONTAINS', '2'], ['REMOVE', '2']])
Expected Output: [True, False, True, True, False, False]
Explanation: The source sequence separates duplicate insertion, removal and membership.
Input: (1, [['CONTAINS', '0'], ['ADD', '0'], ['REMOVE', '0'], ['ADD', '0'], ['CONTAINS', '0']])
Expected Output: [False, True, True, True, True]
Explanation: The sole value can be removed and reinserted.