Quick Overview

Implement constant-time bounded-integer set operations with direct addressing, explicit duplicate semantics, initialization cost, and sparse-universe tradeoffs.

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.

Loading coding console...

Show the approach

Approach

Allocate one false membership slot for each value from zero through limit-1. Its invariant is that present[v] is true exactly when v belongs to the set. ADD sets the slot and reports whether it changed from false; REMOVE clears it and reports the previous value; CONTAINS simply reads it. These local operations preserve the invariant and naturally implement duplicate semantics. Initialization costs O(limit) time and state; each set operation then performs worst-case O(1) array accesses, with input-token parsing accounted separately. A sparse enormous or unknown universe would favor a hash set for expected constant-time access or a balanced search tree for logarithmic worst-case access. Direct addressing here uses the bounded range rather than general-purpose hashing. Membership does not itself provide efficient sparse sorted iteration: scanning this representation in value order costs O(limit), while an ordered set offers sorted traversal over stored values.

Time complexity:
O(limit) initialization, O(1) set work per operation plus decimal-token parsing
Space complexity:
O(limit) state, excluding output