Design a Number Container System

class NumbContainer {
public:
    NumbContainer() {}

    void update(int idx, int num) {
        idxToNum[idx] = num;
        numToIdx[num].push(idx);
    }

    int locate(int num) {
        if (numToIdx.find(num) == numToIdx.end()) {
            return -1;
        }

        auto& indicesHeap = numToIdx[num];

        while (!indicesHeap.empty()) {
            int i = indicesHeap.top();

            if (idxToNum[i] == num) {
                return i;
            }

            indicesHeap.pop();
        }

        return -1;
    }

private:
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> numToIdx;
    unordered_map<int, int> idxToNum;
};

/**
 * Your NumbContainer object will be instantiated and called as such:
 * NumbContainer* obj = new NumbContainer();
 * obj->update(idx,num);
 * int param_2 = obj->locate(num);
 */

In the solution for designing a number container system using C++, the NumbContainer class plays a central role. This system provides capabilities to update the mapping of a number to a specific index and to locate an index corresponding to a number using two primary methods: update() and locate().

• update(int idx, int num): This function maps a given number num to an index idx. It uses an unordered_map, idxToNum, to map the individual indices to their respective numbers. Additionally, it manages a reverse mapping from numbers to their indices using another unordered_map, numToIdx, which stores indices in a min-heap (priority queue). This heap arrangement ensures the smallest available index can be accessed efficiently.

• locate(int num): This method returns the smallest index where the given number num is located, using the heaps stored in numToIdx. If the number is not present, it returns -1. If the index stored in the heap does not match the number at that index (a possible condition due to updates), it removes that index from the heap. The structure ensures that searches are optimal, only returning the active and correct index and cleaning up any discrepancies caused by updates to other indices.

Executing these operations in constant average time complexity is achieved by the use of unordered_map and priority_queue, providing efficient access and update times. This system is particularly useful in scenarios where frequent updates to the indices of numbers are expected, and quick lookups are essential. The use of a min-heap (by priority_queue with a greater comparison function) enables the locate method to efficiently find the smallest index, critical for performance in large datasets.

In summary, the NumbContainer class provides a robust solution for managing a dynamic set of index-to-number mappings, optimizing both update and lookup operations through the use of efficient data structures tailored for quick access and update scenarios.

class NumberTracker {

    public NumberTracker() {
        numToIndicesMap = new HashMap<>();
        idxToNumMap = new HashMap<>();
    }

    public void update(int idx, int num) {
        idxToNumMap.put(idx, num);

        numToIndicesMap
            .computeIfAbsent(num, k -> new PriorityQueue<>())
            .add(idx);
    }

    public int locate(int num) {
        if (!numToIndicesMap.containsKey(num)) {
            return -1;
        }

        PriorityQueue<Integer> indicesHeap = numToIndicesMap.get(num);

        while (!indicesHeap.isEmpty()) {
            int currentIdx = indicesHeap.peek();
            if (idxToNumMap.get(currentIdx) == num) {
                return currentIdx;
            }
            indicesHeap.poll();
        }

        return -1;
    }

    private Map<Integer, PriorityQueue<Integer>> numToIndicesMap;
    private Map<Integer, Integer> idxToNumMap;
}

The given Java solution involves the creation of a NumberTracker system designed to efficiently track and manage associations between numbers and their container indices in two main ways:

• Update operation: By associating a number with a specific index. If a number is attached to an index that already exists, it updates the index with the new number. Behind the scenes, it maintains a mapping (idxToNumMap) from indices to numbers and a reverse lookup (numToIndicesMap) which associates each number with a priority queue of indices.

• Locate operation: By fetching the smallest index for a given number. This method checks if the number exists in numToIndicesMap. If so, it uses a priority queue to efficiently find and return the smallest index currently associated with that number. It ensures the returned index is still actively linked to the number, considering updates might have altered mappings.

The solution ensures that:

• Each update is handled efficiently by using a hash map for idxToNumMap for quick inserts and look-ups, and a compute-if-absent pattern on numToIndicesMap to manage lists of indices via a priority queue, optimizing retrieval and update operations.

• The locate method leverages the priority queue to efficiently get the smallest index and checks consistency via idxToNumMap to ensure the index is still valid. If the condition fails (index does not match the number anymore), it continuously polls the priority queue to get the next potential index.

It’s essential to note the additional handling required during the locate operation to address possible discrepancies due to updates, ensuring the tracker always provides accurate and current data. This design offers a blend of performance and reliability for managing number-container relationships dynamically.

class IndexNumberManager:
    def __init__(self):
        self.num_to_idx_map = defaultdict(list)
        self.idx_to_num_map = {}

    def change(self, idx: int, num: int) -> None:
        self.idx_to_num_map[idx] = num
        heapq.heappush(self.num_to_idx_map[num], idx)

    def find(self, num: int) -> int:
        if not self.num_to_idx_map[num]:
            return -1

        while self.num_to_idx_map[num]:
            top_idx = self.num_to_idx_map[num][0]

            if self.idx_to_num_map.get(top_idx) == num:
                return top_idx

            heapq.heappop(self.num_to_idx_map[num])

        return -1

# Usage
# obj = IndexNumberManager()
# obj.change(idx, num)
# result = obj.find(num)

This program presents a Python class IndexNumberManager, designed for managing a number container system that associates indices with numbers efficiently. Here's a concise summary of how each method functions:

• Initialization (__init__):

  • Establishes two maps:
    • num_to_idx_map: Maps numbers to a heap of indices.
    • idx_to_num_map: Maps indices to the most recent number associated with them.

• Change Method (change):

  • Associates an index with a number and updates both mappings:
    • Updates the index-to-number map directly.
    • Inserts the index into the min-heap associated with the number in the number-to-index map.

• Find Method (find):

  • Retrieves the smallest index associated with a number:
    • If no indices are associated with the number, it returns -1.
    • Checks if the smallest index still corresponds to the number:
      • If it does, returns this index.
      • If not, removes this index from the heap and checks the next one.
    • If no valid index is found, it returns -1.

This design ensures:

• Efficient index changes and lookups.
• Maintained consistency between the two maps to provide accurate and quick retrievals.