Facebook Puzzle Master Page

While I don't typically associate Facebook with any kind of intelligence, it is true that it's a massive site and there has to be a great deal of quality engineering on the backend to keep everything running. I suppose I should be less surprised, then, at the quality of the puzzles they've provided on their Jobs/Puzzles page. These are technically provided to give you an opportunity to get an interview, but they're also fun just to work out, and they have an automated submission process which gives the additional satisfaction of a computer approving your solution.

The Facebook Jobs/Puzzles page

Grow Arrays

You've got a simple class that's an implementation of a growable array. Each time an object is put beyond the end of the array, a new array of twice the size of the previous (or large enough to store the object, whichever is larger) is created, the elements are copied over, and the new array is used.

The issue is that you have some legacy code that needs access to an actual array rather than your wrapping class. You can't touch the old code, but you can do anything you want in your code. The old code has a .setArray(array) method that allows you to specify that it should use a different array than the one it's currently using. There may be more than one legacy object using your growable array class.

What are some possible ways to make the legacy code work with your GrowArray? What are the drawbacks and benefits of each?

Mass transit heuristics

Consider the bus lines of a major city. You're given a set of bus stops (which are set and immovable by your project) and you are helping to create the different bus routes that will service all of these stops. The plan will have a list of each bus route and how often buses come along each route. You can ignore rush hour peaks and changes in traveler load for the weekends-- assume the average load is the same at any time of day.

Your job is not to create this set of routes, but to write a heuristic that measures the efficiency of a given set of routes. You can use whatever metrics you like to determine the best route. First, what are some measurements that might help determine the "best" set of routes? And second, how would you code an evaluator to generate a single value that incorporates all of these measurements?

Picking teams

Write an algorithm to fairly assign n players to m sports teams in a league. Each player will create an order of their peers based on how much they want to be on their team (or how good they are). This list will not include the player themselves.

For instance, to split 6 players A,B,C,D,E,F into 3 teams, the players might submit:
A: {B, C, D, E, F}
B: {A, D, C, F, E}
C: {A, B, D, F, E}
D: {C, B, A, E, F}
E: {B, A, D, F, C}
F: {A, B, C, D, E}

Your algorithm must (1) be fair globally and (2) maximize each player's perception of the team they end up on. In our example, the team EC would do a poor job of satisfying (2) because each player is paired with their last choice, while AB would do a good job of satisfying (2) but probably fail to satisfy (1) because they're both very highly-ranked players.

It's up to you to determine how to quantify these two requirements, and run-time is not a large consideration.

Ranking cars

You work at a used car dealership, and you have an inventory of cars. Each car has several properties. We'll deal with four here-- gas mileage, body style, price, color. Your job is to create a sorted list of this inventory for each new customer.

You have two set heuristics-- when all else is the same, higher mileage or lower price should be preferred.

In your sorting algorithm, you can pose questions to the customer in the form of, "Do you prefer car A or car B?" Write an algorithm that (1) doesn't ask the customer a question if its answer can be discerned from your heuristics and previous answers (assume transitivity) and (2) chooses which questions to ask so as to minimize the total number of questions needed.

First Post!

Just a brief introduction--

I just started a new job a couple months ago. One thing I discovered is that I really enjoy the little coding puzzles I saw from the different employers. Having done my own fairly mundane problems in the past, I've been keeping an eye out for more interesting problems. Just thought I'd start keeping them all in one place.

Feel free to solve these, add to them, suggest alternatives, or tell me why they're terrible. Some will be very open-ended "How would you solve this problem?" types, others will be more concrete. I'll try to be language-agnostic, but I'll probably tend towards what I know. Feel free to answer in any language you prefer.