xyz Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
of 0 vote

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.


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

  def addServer(self, serverNumber):
    if serverNumber not in self.serverIndices:
      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

# 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

- prudent_programmer March 19, 2018 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More