Implement Server Number Allocation
Company: Oura
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Implement a server number allocator for a data center.
Servers have a string `type`, such as `"web"`, `"database"`, or `"cache"`. Each server type has its own independent namespace of positive integer server numbers starting from `1`.
Design a class that supports the following operations efficiently:
- `allocate(type: string) -> int`: Assign and return a server number for the given server type.
- Return the smallest currently available positive integer for that type.
- If no released number is available, assign the next new number for that type.
- `release(type: string, number: int) -> void`: Release a previously allocated server number so it can be reused later for the same server type.
Requirements:
- Server numbers are independent across types. For example, `web` server `1` and `database` server `1` can both exist at the same time.
- A number that is currently allocated must not be allocated again for the same type.
- Released numbers should be reused before creating larger numbers, using the smallest available released number first.
- Handle a large number of allocation and release requests efficiently.
Example:
```text
allocate("web") -> 1
allocate("web") -> 2
allocate("database") -> 1
release("web", 1)
allocate("web") -> 1
allocate("web") -> 3
```
Quick Answer: This question evaluates the ability to design efficient stateful data structures and algorithms for resource allocation, focusing on management of per-type namespaces and correct reuse of released identifiers.