Resizable Array-Backed Integer Set
The Walt Disney Company● MediumFULLTIMEPHONE SCREENProblem statement
Implement a set without hashing by storing unique integers in a contiguous array. Process commands ADD value, REMOVE value, CONTAINS value, SIZE, and CAPACITY. Every command emits a string result: mutations and membership emit true/false; SIZE and CAPACITY emit a decimal integer.
The backing capacity starts at initialCapacity, doubles before inserting into a full array, and halves after removal when size is at most one quarter of capacity, never below the initial capacity. Preserve the relative order of remaining values.
Function
dynamicArraySet(operations: String[], initialCapacity: int) → String[]Examples
Example 1
operations = ["ADD 4","ADD 7","ADD 4","CONTAINS 7","SIZE","CAPACITY"]initialCapacity = 2return = ["true","true","false","true","2","2"]Duplicate insertion fails and capacity remains two.
Example 2
operations = ["ADD 1","ADD 2","ADD 3","CAPACITY","REMOVE 2","REMOVE 3","CAPACITY"]initialCapacity = 2return = ["true","true","true","4","true","true","2"]The third insert grows to four; size one then triggers shrink to two.
Example 3
operations = ["REMOVE 9","CONTAINS 9","SIZE","CAPACITY"]initialCapacity = 3return = ["false","false","0","3"]Missing removal is harmless and capacity never falls below its initial value.
Constraints
1 <= initialCapacity <= 10^4.1 <= operations.length <= 10^4.- Values are signed 32-bit integers and commands are valid.