Interview:Assign-Next-Available-ID

Question:

Given an array of observed ids and a threshold, an ID is considered “active” (unavailable) if its frequency is ≥ threshold. If its frequency is < threshold, it is eligible for reuse.

You need to assign numAssignments new IDs in strictly ascending numerical order, starting from 1. During this process, you must skip any IDs that are currently “active”. Return the value of the last ID assigned.

Example: Suppose n = 7, ids = [1, 3, 2, 3, 5, 1, 3], numAssignments = 4, and threshold = 2. Output: 6

Summary of thoughts

• We can first consider all of the integer in the array are inactive so that the output should be numAssignments. However, this is the ideal case. If there are any integer’s frequency larger than threshold, then update(add 1) the result.
• Count frequency using HashMap, to count the occurences of each identifier
• Use ArrayList to count which numbers are larger than or equal to threshold, which are active(unavailble to use). We can store then in a list and sort them in ascending order.
• Imagine an ideal scenario where no IDs are occupied. If we need to assign numAssignments IDs, the last one we hand out would simply be numAssignments. Therefore, we initialize result = numAssignments.
• If an activeId <= result, it means a number within our planned range is already taken. To compensate for this missing spot, we must push our target one step further by incrementing it (result++). If an activeId > result, it means this occupied number is completely outside our required range and doesn’t affect us. Because our list is sorted, all subsequent active IDs will also be larger, so we can safely break out of the loop early to save time.
• Return result

Code（Java）

class Result {

    public static long assignIdentifiers(List<Integer> ids, int threshold, long numAssignments) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int id : ids) {
            frequencyMap.put(id, frequencyMap.getOrDefault(id, 0) + 1);
        }
        
        List<Integer> activeIds = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() >= threshold) {
                activeIds.add(entry.getKey());
            }
        }
        Collections.sort(activeIds); // O(nlog(n))
        
        long res = numAssignments;
        
        for (int activeId : activeIds) {
            if (activeId <= res) {
                res++;
            } else {
                break;
            }
        }
        
        return res;
    }
}