Design a mutable container system that supports updating values at indices and quickly finding the smallest index holding a given value.
Design a Number Container System
Build a data structure that stores integers at numbered indices and supports two operations:
- Change the number stored at an index.
- Find the smallest index currently storing a specific number.
The key challenge is to make find(number) fast even after many updates.
A correct design must handle reassigning an index from one number to another and keep the internal state consistent at all times.
Input Format
This is an API design problem.
Implement a class with the following operations:
change(index, number): set the value atindextonumber.find(number): return the smallest index whose current value isnumber, or-1if no such index exists.
Output Format
For each find(number) call, return the smallest valid index for that number, or -1 when the number is absent.
Constraints
indexandnumberare positive integers.- Multiple calls to
changemay target the same index. - If an index is reassigned, the old number must no longer consider that index as present.
- The data structure should support many operations efficiently.
Typical interview solution targets O(log n) or better per operation.
Example 1
Input
change(1, 10) change(2, 10) find(10) change(1, 20) find(10) find(20)
Output
1 2 1
Explanation
After the first two updates, number 10 is stored at indices 1 and 2, so the smallest is 1. Reassigning index 1 to 20 removes it from the set for 10, leaving 2 as the smallest index for 10 and 1 as the index for 20.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.