Oura | OAMaster

01Assign Server Numbers by Type

You are given a list of server-management requests. Each request is either "allocate <type>" or "deallocate <type> <id>". Every server type has its own numbering space starting from 1. When an allocate request arrives for a type, assign the smallest positive server number that is currently unused for that type. When a deallocate request arrives, that server number becomes available again for future requests of the same type. Return the server numbers assigned by all allocate requests, in the order those allocation requests appear. Function Description Complete the function assignServerNumbersByType in the editor below. assignServerNumbersByType has the following parameter:

String[] requests: the list of allocation and deallocation requests Returns int[]: the server numbers assigned by the allocation requests, in order.

Constraints

The source thread did not provide explicit numeric bounds.

Each request is either "allocate <type>" or "deallocate <type> <id>".
Server numbers are positive integers.
Every deallocation request refers to a server number that is currently allocated for that same type.

Example 1

Input:

requests = ["allocate db", "allocate db", "allocate cache", "deallocate db 1", "allocate db", "allocate cache", "deallocate cache 1", "allocate cache"]

Output:

[1, 2, 1, 1, 2, 1]

Explanation: The first two db allocations receive 1 and 2. The first cache allocation receives 1. After db 1 is released, the next db allocation reuses 1. The cache pool behaves independently, so its next allocations are 2 and then 1 again after cache 1 is released.

Example 2

Input:

requests = ["allocate gpu", "deallocate gpu 1", "allocate gpu", "allocate api", "allocate gpu", "deallocate api 1", "allocate api"]

Output:

[1, 1, 1, 2, 1]

Explanation: Each server type keeps its own smallest-available-id pool. The gpu allocations produce 1, then reuse 1 after deallocation, and later allocate 2. The api type is independent, so it allocates 1, releases it, and then allocates 1 again.

解法

每个 type 维护一个最小堆(已释放的 id 池)和一个计数器 next。allocate 时优先从堆取最小空闲 id，没有则用 next 自增。deallocate 时把 id 推回堆。整体时间 O(K log K)，K 是 allocate 总数；空间 O(K)。

import heapq
from typing import List

def assignServerNumbersByType(requests: List[str]) -> List[int]:
    free_pool: dict[str, list[int]] = {}
    next_id: dict[str, int] = {}
    assigned: List[int] = []
    for req in requests:
        parts = req.split()
        if parts[0] == "allocate":
            t = parts[1]
            pool = free_pool.setdefault(t, [])
            if pool:
                sid = heapq.heappop(pool)
            else:
                sid = next_id.get(t, 0) + 1
                next_id[t] = sid
            assigned.append(sid)
        else:
            t = parts[1]
            sid = int(parts[2])
            heapq.heappush(free_pool.setdefault(t, []), sid)
    return assigned

import java.util.*;

class Solution {
    int[] assignServerNumbersByType(String[] requests) {
        Map<String, PriorityQueue<Integer>> freePool = new HashMap<>();
        Map<String, Integer> nextId = new HashMap<>();
        List<Integer> assigned = new ArrayList<>();
        for (String req : requests) {
            String[] parts = req.split(" ");
            if (parts[0].equals("allocate")) {
                String t = parts[1];
                PriorityQueue<Integer> pool = freePool.computeIfAbsent(t, k -> new PriorityQueue<>());
                int sid;
                if (!pool.isEmpty()) sid = pool.poll();
                else { sid = nextId.getOrDefault(t, 0) + 1; nextId.put(t, sid); }
                assigned.add(sid);
            } else {
                String t = parts[1];
                int sid = Integer.parseInt(parts[2]);
                freePool.computeIfAbsent(t, k -> new PriorityQueue<>()).add(sid);
            }
        }
        int[] out = new int[assigned.size()];
        for (int i = 0; i < out.length; i++) out[i] = assigned.get(i);
        return out;
    }
}

#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <sstream>

class Solution {
public:
    std::vector<int> assignServerNumbersByType(std::vector<std::string>& requests) {
        std::unordered_map<std::string, std::priority_queue<int, std::vector<int>, std::greater<int>>> freePool;
        std::unordered_map<std::string, int> nextId;
        std::vector<int> assigned;
        for (auto& req : requests) {
            std::stringstream ss(req);
            std::string op, t;
            ss >> op >> t;
            if (op == "allocate") {
                auto& pool = freePool[t];
                int sid;
                if (!pool.empty()) { sid = pool.top(); pool.pop(); }
                else { sid = nextId[t] + 1; nextId[t] = sid; }
                assigned.push_back(sid);
            } else {
                int sid; ss >> sid;
                freePool[t].push(sid);
            }
        }
        return assigned;
    }
};