CareerCup

The trickiest part about this problem is that random has to be O(1). We can achieve this by using a list + dictionary to keep a track of the servers. The removal operation will be tricky since we have to swap it with the last element and then pop it to obtain constant time. I present my solution below in Python with test code.

Solution:

import random
class Pool:
  def __init__(self):
    self.servers = []
    self.serverIndices = {}

  def addServer(self, serverNumber):
    if serverNumber not in self.serverIndices:
      self.servers.append(serverNumber)
      self.serverIndices[serverNumber] = len(self.servers)-1
      return True
    return False

  def deleteServer(self, serverNumber):
    if serverNumber in self.serverIndices:
      # Key trick is to swap with last element
      # and then delete it
      index = self.serverIndices[serverNumber]
      lastNumber = self.servers[-1]
      self.servers[-1] = serverNumber # Place it at last index

      # Remove it from the list and the hashmap
      self.servers.pop() # Remove the server
      del self.serverIndices[serverNumber]

      # Update the servers list and the hashmap
      if index != len(self.servers):
        self.servers[index] = lastNumber
        self.serverIndices[lastNumber] = index

      return True
    return False

  def getRandomServer(self):
    return self.servers[random.randint(0, len(self.servers)-1)]

  def __repr__(self):
    return 'Current pool: ' + str(self.servers)

Test Code:

# Test Code
p = Pool()
# Add servers
p.addServer(5)
p.addServer(3)
p.addServer(2)
p.addServer(10)
p.addServer(6)

# Print servers
print(p) # Current pool: [5, 3, 2, 10, 6]

# Get Random servers
print('Random server:', p.getRandomServer()) # Random server: 2
print('Random server:', p.getRandomServer()) # Random server: 5
print('Random server:', p.getRandomServer()) # Random server: 5

# Remove Servers
print(p.deleteServer(3)) # True
print(p.deleteServer(10)) # True
print(p.deleteServer(5)) # True
print(p.deleteServer(3)) # False
print(p.deleteServer(999)) # False
print(p) # Current pool: [2, 6]

# Get random servers
print('Random server:', p.getRandomServer()) # Random server: 6
print('Random server:', p.getRandomServer()) # Random server: 6