Katkat
Back

Implement Server Number Allocation

OuraSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manage and reuse resources efficiently using data structures that allow for logarithmic time allocation and deallocation within partitioned namespaces.

Problem Statement

You are tasked with building a resource allocation system for a server farm. Servers are assigned an ID based on their type (a string). For each type, server IDs must be assigned as the smallest positive integer (1, 2, 3, ...) that is not currently in use by that specific type.

Implement a ServerAllocator class with the following methods:

  • allocate(type: str) -> int: Assigns the smallest available positive integer ID for the given type and marks it as used.
  • release(type: str, id: int) -> None: Marks the given id as available again for the specified type.

Constraints

  • type is a non-empty string.
  • id is a positive integer.
  • Total number of calls will not exceed 10^5.
  • release will only be called for IDs that were previously allocated and are currently in use.

Examples

# Example 1
allocator = ServerAllocator()
allocator.allocate("web") # returns 1
allocator.allocate("web") # returns 2
allocator.release("web", 1)
allocator.allocate("web") # returns 1 (reused)
allocator.allocate("db")  # returns 1

Considerations

  • How will you track the next available ID for types where no IDs have been released?
  • How will you efficiently manage released IDs to ensure you always pick the smallest one?

Hints

Hint 1

Use a hash map to store the state of each server type separately.

Hint 2

For each type, maintain a counter for the next ID that has never been used, and a Min-Heap to track IDs that were released and are ready for reuse.

Hint 3

When allocating, check the Min-Heap first; if it is empty, use the counter and increment it.

Follow-up questions

  • What is the time complexity of your allocate and release operations in the worst case?
  • If the number of types is extremely large, how would you optimize memory usage if many types only ever have one server allocated?
  • How would you adapt this system if you needed to support a 'reserve' operation, where an ID is marked as unavailable but not yet linked to a specific instance?