My Facebook Interview Experience

And did you mean users instead of friends? If a user is already a friend with someone, that means they can only be one degree away.

Here's what I came up with. Is this about right?

  # Set up a mock DB holding users and relationships.
  # 1 is 1 degree from 2, 5 and 6
  # 1 is 2 degrees from 3, 4, 6
  # 1 is 3 degrees from 7 and 8
  # 1 is 4 degrees from 7 and 8
  people_store = [''] #0 -- put blank in 0 so we can have a one-based list.
  people_store.append([2,5,6]) #1
  people_store.append([1,3]) #2
  people_store.append([2,4,6]) #3
  people_store.append([3,6,7,8]) #4
  people_store.append([1]) #5
  people_store.append([1,3,4]) #6
  people_store.append([4,8]) #7
  people_store.append([4,7,9]) #8
  people_store.append([8]) #9

  def find_users_within_x_degrees(user_id, degrees):
      """Given a user ID, find other users within two degrees."""
     
      # Users that are within the degree range.
      # Start by adding current user's friends (1 degree).
      users_within_range = set(people_store[user_id])
    
      # Keep track of user IDs that have been checked.
      checked_ids = set()
    
      # Start at 2, because we have already handled 1 degree above.
      for degree in range(2, degrees+1):
          # Get other users IDs and get their friends. Only do so for users we haven't checked.
          for other_user_id in users_within_range.difference(checked_ids):
              checked_ids.add(other_user_id)
            
              # Add other user's friends.
              users_within_range.update(people_store[other_user_id])
    
      # Because friendships are reciprocal, if the number of degrees is > 1, the requested user_id will be in the set, and should be removed.
      if degrees > 1:
          users_within_range.remove(user_id)
    
      return users_within_range

The team I interviewed for was less technical than a core engineering team but the process was much more straightforward and actually easier than I expected. I'm from outside the US and had heard about month long hiring processes and day long interviews but in reality it was three short phone interviews and a single in-person interview which they paid for. I got the feeling they were looking for a personality fit rather than just engineering skills.

At least they're not asking why man hole covers are round, or if you had a bathtub the size of New York how many Grand Pianos would fit in it (correct answer: "I'm not aware that the Grand Piano is an internationally recognised standard unit of measure")

On the other hand, interviewing is not a solved problem in IT. It can't be, otherwise half (or more) of the people would never have gotten in, and productivity would soar.

On the gripping hand, for all that I want to denigrate Facebook, these questions do actually make sense - do you want people on your server writing an O(n) algorithm when an O(log n) one will do? When N is ridiculously large, like 500 million or something like that? And if the only place to learn these things is in an academic environment, then so be it. I admire the generic self-taught programmer as much as anybody else, but if they really love what they do, it would behoove them to borrow someone's old computer science textbooks and skim through them.