A Sound Retirement Plan

The cornerstone of my investment portfolio is playing the lottery. Each week I purchase some tickets, each of which has six numbers from 1-60 on them (without repeats). I have no delusions about particularly lucky numbers or trends in independently random events.

My problem is with the feasibility of checking all of these tickets. At the end of the week, I'll have a stack of tickets and the correct numbers, and I need to look through them all to see if I've won. The problem is to design such a system where either by purchasing particular numbers and/or by storing the tickets in a particular way, I reduce the difficulty in determining if there's a winner and finding it. I expect to purchase a very large number of tickets.

The following constraints apply:

-Since the jackpot pool is finite, having two identical tickets earns me less than two different tickets unless a third ticket splits a win with me. I prefer that none of the tickets are duplicates (which can be assumed given pseudorandom generation or specifically controlled for).

-The lottery I play in gives awards for matching 4, 5, or all 6 of the numbers. The system must provide the information for all of them.

-I have a large area to store the tickets, but it's not infinite.

-I do not have the time to linearly look through all the tickets after learning the winning numbers.

-If there's a computer used in the solution, take data entry errors into account.

Cannibals and Missionaries

An old puzzle turned into a little runtime analysis programming project:

You're given a number c cannibals and m missionaries on one side of a river. In the river is a boat that can carry b people at a time. Your task is to move all the missionaries from one side of the river to the other. A valid state is one in which there are no more cannibals than missionaries on either side of the river or in the boat unless there are 0 missionaries there (on the fear that the missionaries will be overpowered and eaten). The boat must have at least one person in it to move across the river.

For instance, for [m=1, c=1, b=2] a solution is for both people to take the boat across. For [m=2, c=2, b=2] a solution is for both cannibals to take the boat, one to return, both missionaries to take the boat and have one return, then the remaining cannibal and missionary to take the boat across. For [m+c>1 and b <= 1] there is no solution.

1) Write an algorithm to quickly find any solution. What is its complexity?
2) Write an algorithm to find the fastest (fewest steps) solution. What is its complexity?
3) Write an algorithm to determine whether the state is solvable. What is its complexity?
4) Write an algorithm to find the number of steps in the fastest solution, without it being necessary to produce the solution. Is it faster than #2?
5) Write a heuristic which would provide a number of steps such that if a solution was found to use that many steps, it would be the known fastest solution. (A heuristic that satisfied this problem could simply return 1)

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.