Recycling Server Pool
Efficiently manage server IDs by recycling exploded servers
You manage a pool of servers numbered sequentially starting from 1. Over time, some servers might “explode,” freeing up their number for future use. When launching a new server, your goal is to assign it the smallest available number.
Implement a class with the following methods:
Constructor: Accepts a list of currently allocated server numbers.
next_server_number(): Returns the smallest unused server number and marks it as allocated.
explode(server): Simulates a server explosion by recycling the given server number, making it available for future allocation.
Examples
Example 1
Setup: Create a pool with no allocated servers.
Operations:
Calling
next_server_number()returns1.Calling
next_server_number()again returns2.
Example 2
Setup: Allocated servers:
[1, 3, 4]Operations:
Calling
next_server_number()returns2(filling the gap).A subsequent call to
next_server_number()returns5.
Example 3
Setup: Allocated servers:
[1, 2, 3, 4]Operations:
Call
explode(2)to free server2.Calling
next_server_number()returns2(the recycled number).
Example 4
Setup: Allocated servers:
[1, 2, 3, 4]Operations:
Call
explode(1)andexplode(3), recycling servers1and3.The next call to
next_server_number()returns1(smallest available).Another call returns
3.A subsequent call returns
5.
We can use minimum heap for this problem. When we allocate server insert all the server number which are not in array till end of the array and max(server) + 1
// For ex: [1,3,4] My min heap will contain [2, 5(extra which is max(server) + 1)]
If server explodes add that number to heap.
// for ex 3 explodes then heap = [2,3,5]
If we wants to allocate server then
take top element from heap
if heap size == one then add heap.top()+1 to heap
and do heap.pop();
// double allocation called then pop 2 and then 3
// but now if allocation called then we add 6 to heap and then pop 5 this way there will be atleast one element in heap
// Why did I add extra? because if all of number till max of starting array are allocated then we need number outside of that array
Time complexity should be
creating heap from array heapify O(n). I mean we don't need to create heap we push back which element are not in array into vector it will give us min heap by default.
poping O(logn)
adding O(logn)
Pardon for my bad explaination.
import heapq
class RecyclingServerPool:
def __init__(self, allocated):
self.allocated = set(allocated)
self.heap = []
if allocated:
m = max(allocated)
for i in range(1, m):
if i not in self.allocated:
heapq.heappush(self.heap, i)
self.next_new = m + 1
else:
self.next_new = 1
def next_server_number(self):
if self.heap:
x = heapq.heappop(self.heap)
else:
x = self.next_new
self.next_new += 1
self.allocated.add(x)
return x
def explode(self, server):
if server in self.allocated:
self.allocated.remove(server)
heapq.heappush(self.heap, server)
pool = RecyclingServerPool([1,3,4])
print(pool.next_server_number()) # 2
print(pool.next_server_number()) # 5
pool = RecyclingServerPool([1,2,3,4])
pool.explode(2)
print(pool.next_server_number()) # 2
pool = RecyclingServerPool([1,2,3,4])
pool.explode(1)
pool.explode(3)
print(pool.next_server_number()) # 1
print(pool.next_server_number()) # 3
print(pool.next_server_number()) # 5