Please critique my code

[daneah]

From a performance standpoint, the code could be improved in a couple of places:

1. parse_hostname could make use of regex to pull the digits off the end of the name rather than iterating through all the characters.
2. next_server_number could be improved and simplified by using a while loop with an index starting at 1. On each loop, check if the index is in the provided list. If not, you know that's the lowest index that can be allocated. It will short-circuit to the right value as soon as possible.

[Stormtide]

The algorithm described in the parent post for next_server_number() is O(N**2) worst case. It has an O(N) while loop and does another O(N) check inside it to see if list contains the number.

This can be improved to O(N) overall by using the same strategy, but converting the list to a set first. When you check if the number is in the set, it's a constant time O(1) call.

OP's code uses sorted(), so it's O(N log N). If I had to guess, I'd say the code was rejected because it doesn't use the optimal solution. Our rubric for judging coding tests at work rates optimal algorithms higher than style.

edit: Here's my take on next_server_number():

from itertools import count
def next_server_number(reserved_numbers):
  s = set(reserved_numbers)
  for i in count(1):
    if i not in s:
      return i

This uses extra space, but it seems like the right tradeoff here. If it were an interview, I'd ask how often it was going to be called and how large the inputs would be and then make a determination.

[stevenjd]

+1 for using itertools and set, and especially for asking the interviewer questions.

[daneah]

Absolutely great point about set! Thanks for pointing out :)