## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
This is from Facebook's web site:
http://www.facebook.com/jobs_puzzles/?puzzle_id=1&ref=nf Evil Gambling Monster There are 9 casinos, laid out in the following configuration, with the lines between them representing overnight travel routes: 1 ---- 2 ---- 3 | | | | | | 4 ---- 5 ---- 6 | | | | | | 7 ---- 8 ---- 9 On an otherwise uneventful visit to one of these casinos, your dear mother has had the misfortune to be enslaved by an evil gambling monster. I call him Gamblor, and it is time to snatch her away from his neon claws.[1] Unfortunately, Gamblor demands the payment of a great deal of money in return for releasing his hostage. Luckily, you are a psychic computer scientist. With your powers, you can predict in advance over the next 30 days how much you would win (or lose) if you played at a particular casino on that day. This schedule of winnings is represented by the following nine 30-element arrays: wins1 = [ 53,-84, 50,-73, 54, 60, 74, 22,-63,-78, 75, 72, -46, 99,-33, 24, 6,-66, 77,-61,-60,-46,-52, 84, 91,-21,-52,-72,-39,-41] wins2 = [ 77,-86,-25, 27,-59,-71,-13,-85, 50, 24,-63, 26, -4,-10, 25, 62,-85,-68, 96, 92,-29,-64,-54, 18, -79,-62, 97,-32,-35,-42] wins3 = [ 27,-57,-28,-98, 69, 12,-70,-43, 27, 80, 80, 64, 6,-23,-45,-68,-60,-31,-36,-63,-39, 34,-27, 7, -47, -7, 44,-50, 60,-90] wins4 = [ 7,-12,-48, 79,-11,-78, -8, 19,-21,-81, -1,-40, 83,-95, 36,-62,-63, 76, 6, 0,-87, 67,-66,-15, -26,-14, 78,-81, 36, 38] wins5 = [-71,-56,-73,-20,-77, 15, 2, 14,-66, 81, 33, 33, -59, 16, 37, 77, 53, 73, 53,-40,-26, 66,-73, 7, -48, 1, 93,-70, 19, 30] wins6 = [ 68, 47, 73, 94,-72, 96, 10, 30, 11, 44, 11,-56, -23, 51, 60,-86, 29, 13, 87,-17, 73,-39,-51,-99, 68, 1, 1, 62, 30,-79] wins7 = [ -8, -1, 68,-34, -7, 96,-37,-96, 26, 73, 47,-62, -83,-76, 89, 77,-62, 18, -9,-75,-99,-36,-14,-50, -36,-45, 50, 64,-83,-19] wins8 = [ 85, 9, 79, 53, 75,-28, 49,-62,-25,-24,-89,-77, 13,-72,-54, 2,-95,-17,-80, -5, 8,-79, 59, 93, -30,-77,-51,-79, 87,-35] wins9 = [ 1, 72, 74,-20, 26, 49, 52,-25, 86,-72, 50, 97, -50,-36,-74, -4, 65,-70, 78, 85, 25,-14,-93,-16, -20,-24, 7, 28, -3, -5] Travel routes between the casinos are represented by the following adjoinment matrix: adj = [[1, 1, 0, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0, 0], [1, 0, 0, 1, 1, 0, 1, 0, 0], [0, 1, 0, 1, 1, 1, 0, 1, 0], [0, 0, 1, 0, 1, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 0, 0, 1, 0, 1, 1]] You begin on the first day at the location of casino 1. For example, if you were at casino #1 on day 1, you would win $53 if you decided to play. Later, if you were at casino #3 on day 4, you would lose $98 if you decided to play. Since you can only travel the distance of one route every night, you cannot reach all the casinos right away - e.g. you would not be able to play at casino #6 on the first day to win $68. The casino owners don't like your special abilities, but they have agreed to let you play subject to the following conditions: * At the beginning of the 30 days, you may either begin playing at your current casino immediately or decide to wait until the next day. * Once you begin playing, you must play each consecutive day until you stop. * Once you stop playing, you may not play again. Each night after playing or not playing, you may either stay at your current location or travel to an immediately adjoining casino. You may travel overnight between casinos regardless of whether or not you have played that day. You cannot play a fraction of a day; if a particular day is one where you have chosen to play, you will earn the predicted win or loss for that day. You wish to determine how many N >= 0 days to not play, how many subsequent M >= 0 consecutive days to play (and how many remaining K >= 0 days you also don't play), and the path to travel between casinos during this 30-day time period such that you maximize your total winnings.
My instincts are to use some clever form of matrix multiplication, but this problem may be close enough to the traveling salesman problem that no general solution exists. So my next guess is to write an algorithm that systematically tries all the possible solutions using a DFS.
The way I understand the question is:
1. During any given day you are at one particular casino (the "current" casino). You remain there throughout the day. At the end of the day you may travel to an adjacent casino, which becomes the "current" casino on the next day, or you may stay at the same casino (which will remain current the following day). 2. On each day you may either play at the current casino, or not play. 3. The days on which you do play must be consecutive. If this understanding is correct, then it is a simple matter of finding the longest vertex-weighted path in a directed acyclic graph, which can be done in linear time. The graph is the following. 1. A node for each pair (casino,day), representing that you are at casino "casino" on day "day". Node (casino,day) has weight equal to your earnings at casino "casino" on day "day". 2. A zero weight "source" node. 3. A zero weight "sink" node. 4. An arc from each (casino,day) to each (adjacent casino,day+1). A casino is considered adjacent to itself (representing that you may stay in the same casino overnight). 5. An edge from each (casino,day) to the sink. 6. An edge from the source to each (casino,day) such that casino "casino" is reachable by day "day". (Only casino 1 is reachable by day 1; casinos 1,2,4 are reachable by day 2; casinos 1,2,4,3,5,7 are reachable by day 3; all but casino 9 are reachable by day 4, and all casinos are reachable thereafter.) Actually, we can delete the nodes (casino,day) that are not reachable from the source node. The problem now reduces to finding a maximum-weight path from the source to the sink. This can be done in linear time in the graph size, which is O(#days * #casinos).
A.F. Tuesday, February 06, 2007 |

Powered by FogBugz