Puzzles We did for Google Interview before.

[Seabook]

The following is the Old Puzzles, most of them from TopCoder or real Google Interview. It took some time to arrange them cause actually guys, we did a pretty good job. I roughly counted that we've been doing at least 30 puzzles over all already.

Attention:
1) we need to host different Programming Language, so in the subversion all other codes will be presented in the simple Text files
except Java.

We need to follow one template:
1. Detailed Name including (Name, Source, Level)
2. Always have a solution link.
3. Detailed Description of the problem.

1. HowEasy From TopCoder, Level: 250 (Easy).
You can get Solution from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/howeasy

/*************************************************************************************************************************************
Problem Statement
***Note:  Please keep programs under 7000 characters in length.  Thank you


Class Name: HowEasy
Method Name: pointVal
Parameters: String
Returns: int
 
TopCoder has decided to automate the process of assigning problem difficulty
levels to problems.  TopCoder developers have concluded that problem difficulty
is related only to the Average Word Length of Words in the problem statement:

If the Average Word Length is less than or equal to 3,  the problem is a 250
point problem.
If the Average Word Length is equal to 4 or 5, the problem is a 500 point
problem.
If the Average Word Length is greater than or equal to 6, the problem is a 1000
point problem.
 
Definitions:
Token - a set of characters bound on either side by spaces, the beginning of
the input String parameter or the end of the input String parameter.
Word - a Token that contains only letters (a-z or A-Z) and may end with a
single period. A Word must have at least one letter.
Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)

The following are Words :
"ab",  "ab."

The following are not Words :
"ab..", "a.b", ".ab", "a.b.", "a2b.", "."

Average Word Length - the sum of the Word Lengths of every Word in the problem
statement divided by the number of Words in the problem statement.  The
division is integer division. If the number of Words is 0, the Average Word
Length is 0.
 
Implement a class HowEasy, which contains a method pointVal.  The method takes
a String as a parameter that is the problem statement and returns an int that
is the point value of the problem (250, 500, or 1000). The problem statement
should be processed from left to right.
 
Here is the method signature (be sure your method is public):
int pointVal(String problemStatement);
 
problemStatement is a String containing between 1 and 50 letters, numbers,
spaces, or periods.  TopCoder will ensure the input is valid.
 
Examples:
 
If problemStatement="This is a problem statement", the Average Word Length is
23/5=4, so the method should return 500.
If problemStatement="523hi.", there are no Words, so the Average Word Length is
0, and the method should return 250.
If problemStatement="Implement a class H5 which contains some method." the
Average Word Length is 38/7=5 and the method should return 500.
If problemStatement=" no9 . wor7ds he8re. hj.." the Average Word Length is 0,
and the method should return 250.
Definition
  
Class:
HowEasy
Method:
pointVal
Parameters:
String
Returns:
int
Method signature:
int pointVal(String param0)
(be sure your method is public)
  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*************************************************************************************************************************************/

[Seabook]

Attention:
There are maybe some alignment issues in the Description. You can always check the correct format in the SVN ProblemDesc.txt

1. Tothello From TopCoder, Level: 500 (Medium).
Interesting Puzzle. Have fun on solving the issue that time.

You can get Solution from:

http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/tothello

/*******************************************************************************************************

/*******************************************************************************************************
Problem Statement

THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
TOURNAMENT

Class Name: Tothello
Method Name: bestMove
Parameters: String[], String[], String
Returns: int
Method signature (be sure your method is public):  int bestMove(String[]
redPieces, String[] blackPieces, String whoseTurn);


PROBLEM STATEMENT
The game Tothello is a TopCoder modified version of the board game Othello.
The game is played on an 8 x 8 grid with two players, Black and Red.  The
players alternate turns placing one piece representing their color in one empty
square of the grid.  When the Red player puts a red piece down, any black
pieces that end up between the piece that was placed on the board and any other
red piece already on the board should be changed to red.  If the change in
color from black to red of any piece on the board causes other black pieces to
lie between two red pieces, those black pieces should also be changed to red.
The changing of black pieces will continue until no one black piece lies
between two red pieces.  The manner that pieces change color apply when the
Black player places a piece on the grid, however, the pieces would then change
from red to black.  A player also has the option of passing - not putting any
pieces down - on his turn, in which case the other player just gets to go twice
in a row.

You are to write a program that helps a player determine their best possible
move - the move that results in the most pieces being that player's color at
the end of the move.

Implement a class Tothello that contains a method bestMove.  bestMove inputs
the current state of the grid before a specified player's move and outputs the
number of the player's pieces on the board as a result of the player's best
move.

NOTES
- redPieces is a String[] representing the current positions of red pieces on
the board.
- blackPieces is a String[] representing the current positions of black pieces
on the board.
- The board is an 8x8 grid with the columns referred to by the uppercase
letters A-H and the rows referred to by the numbers 1-8 (inclusive).  The
column is specified before the row.  A1 is in the upper left.  H8 is in the
lower right.
- redPieces and blackPieces are not necessarily the same length (players may
have passed on moves).
- A black piece is between two red pieces if a red piece can be found before an
empty square on either side by following the horizontal, vertical, or either
diagonal out from the Black piece.  For example:

- - - R - - - -
- - - B - - - -
- - - B - - - -    All three Black pieces are between two red pieces.
- - - B - - - -
- - - R - - - -


- - - R - - - -
- - - B B - - -
- - - B - B - -   All four Black pieces are between two Red pieces.
- - - R R R R R


- - - R - - - -
- - - B R - - -
- - - - - - - -   The Black piece is not between two Red pieces.
- - - R R - - -


R R R R R R R R
R - - - - - - R
R - B B - B - R
R - B B B B - R   None of the Black pieces are between two Red pieces.
R - - - - - - R
R R R R R R R R

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- Both redPieces and blackPieces contain between 0 and 50 elements (inclusive).
- All elements of redPieces and blackPieces consist of uppercase letters A-H
and numbers 1-8 (inclusive).
- All elements of redPieces and blackPieces are in the form of letter-number
pairs with each letter representing the column and each number representing the
row of the piece's position (i.e. "A2" where 'A' is the column and '2' is the
row of the piece's position).
- whoseTurn is a String that is equal to either "Red" or "Black" representing
the player for which the method is being run.
- The current state of the board represented by redPieces and blackPieces
contains no red pieces between any black pieces and no black pieces between any
red pieces (a state where there were black pieces between red pieces is
impossible at the start of a move, assuming the game has been played
correctly.)
- The elements are unique in redPieces and blackPieces, and redPieces and
blackPieces do not contain any of the same elements.
- The game board must start with at least one unoccupied space.

EXAMPLES
If redPieces=[C2,C3,C4,C5,D4,E4,
F2,F3,F4,F5,G6] and
blackPieces=[B1,E1,G1,C6,H7,G4] and whoseTurn="Black",
Before the player's move, the board is:

  A B C D E F G H
1 - B - - B - B -
2 - - R - - R - -
3 - - R - - R - -
4 - - R R R R B -
5 - - R - - R - -
6 - - B - - - R -
7 - - - - - - - B
8 - - - - - - - -

Black's best move is C1, which results in:

    A B C D E F G H       A B C D E F G H       A B C D E F G H       A B C D E F G H
1 - B - - B - B -     1 - B B - B - B -     1 - B B - B - B -     1 - B B - B - B -
2 - - R - - R - -     2 - - B - - R - -     2 - - B - - R - -     2 - - B - - R - -

3 - - R - - R - -     3 - - B - - R - -     3 - - B - - R - -     3 - - B - - R - -

4 - - R R R R B - --> 4 - - B R R R B - --> 4 - - B B B B B - --> 4 - - B B B B B -
5 - - R - - R - -     5 - - B - - R - -     5 - - B - - R - -     5 - - B - - B - -
6 - - B - - - R -     6 - - B - - - R -     6 - - B - - - R -     6 - - B - - - B -
7 - - - - - - - B     7 - - - - - - - B     7 - - - - - - - B     7 - - - - - - - B
8 - - - - - - - -     8 - - - - - - - -     8 - - - - - - - -     8 - - - - - - - -

There end up being 16 black pieces, so the method should return 16.

If redPieces=[A1,B8,C6,C8,D8] and blackPieces=[B2,C2,C3,C4,C5] and
whoseTurn="Red", Red's best move is C1, and the method should return 11.



Definition
????
Class:
Tothello
Method:
bestMove
Parameters:
String[], String[], String
Returns:
int
Method signature:
int bestMove(String[] param0, String[] param1, String param2)

(be sure your method is public)

????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*******************************************************************************************************/

[Seabook]

1. CampLunches From TopCoder, Level: 250 (Easy).
Pick up an easy one from the China Tournament in 2008. Happy Coding.

Solution Links:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/camplunches

*****************************************************************************************************/
Problem Statement
????
My two kids go to different summer camps, and each day we go over their lunch menus. I noticed that both camps have a different set of lunches that repeat on a regular basis.
You will be given the repeating menu of lunches for each camp. Each schedule will start at the first element on the first day, which is designated as day zero (0). Return the first day that both camps serve the same lunch, or -1 if they will never serve the same lunch on the same day.
Definition
????
Class:
CampLunches
Method:
firstMatching
Parameters:

String[], String[]
Returns:
int
Method signature:

int firstMatching(String[] menu1, String[] menu2)

(be sure your method is public)
????

Notes
-
The days start at zero (i.e., the first day of camp is day zero).
-
There may be repeats within each individual menu. See Example 2.
Constraints
-
menu1 and menu2 will each contain between 1 and 50 elements, inclusive.
-
Each element of each menu will contain only lower case letters ('a' - 'z') and spaces (' ').
-
Each element of each menu will contain between 2 and 50 characters, inclusive.
Examples
0)

????
{"pbj", "pizza"}
{"pbj", "pizza"}
Returns: 0
They are the same on the very first day. Even though they are also the same on the second day, we are looking for the first time they are the same.
1)

????
{"pbj", "pizza"}
{"pizza", "pbj"}
Returns: -1
They will never be the same on the same day.
2)

????
{"pbj", "pizza"}
{"pizza", "pbj", "pizza"}
Returns: 3
The sequence of lunches is pbj/pizza, pizza/pbj, pbj/pizza, pizza/pizza, so on the third day (starting from zero) they are the same.
3)

????
{"pbj"}
{"pizza", "tuna", "pbj"}
Returns: 2

4)

????
{"pizza", "pbj", "meatballs", "peanut butter and jelly", "pizza hero"}
{"pbj", "meatballs", "peanut butter and jelly", "pizza hero"}
Returns: 16
Note, "pizza" is not the same lunch as "pizza hero".
5)

????
{"pizza"}
{"pizza ", "pizza"}
Returns: 1
Watch out for trailing spaces.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

/*****************************************************************************************************

[Seabook]

1. ComplementMachine2D From TopCoder, Level: 1000 (Hard).
Tried and no solution yet for this puzzle. I can't understand one sentence. Post here for reference.

You can get Solution from:

NO SOLUTION YET.


****************************************************************************************/

Today should be insanely difficult.  Good luck everyone. Wish we could see some genius algorithm.

Problem Statement
????
A binary matrix is a matrix in which each cell contains either a 0 or a 1. A two dimensional complement machine is a machine that works over a binary matrix of N rows numbered from 0 through N-1 and M columns numbered from 0 to M-1.
The machine has 4 instructions: N, S, E and W. Instructions N and S take an integer parameter i (0 <= i <= N-1). N replaces each cell with a row index less than or equal to i with its complement, while S replaces each cell with a row index greater than or equal to i with its complement. The complement of 0 is 1, and the complement of 1 is 0. Instructions W and E take an integer parameter j (0 <= j <= M-1). W replaces each cell with a column index less than or equal to j with its complement, while E replaces each cell with a column index greater than or equal to j with its complement.
We call a binary matrix erasable if it is possible to make all its cells contain a 0 after a finite number of instructions using a two dimensional complement machine. A contiguous submatrix is a matrix formed by selecting one or more consecutive rows and one or more consecutive columns from a bigger matrix. It is possible to select all rows and/or all columns. (See notes for an exact definition of "contiguous submatrix".)
You will be given a String[] matrix representing a binary matrix. Return the number of cells in the largest contiguous submatrix of the original matrix that is erasable.
Definition
????
Class:
ComplementMachine2D
Method:
largestSubmatrix
Parameters:

String[]
Returns:
int
Method signature:

int largestSubmatrix(String[] matrix)

(be sure your method is public)
????

Notes
-

Suppose that A is a binary matrix containing N rows and M columns. Both rows and columns are 0-indexed. Let's use A[i][j] to denote the cell in row i, column j. A contiguous submatrix B of matrix A can be uniquely represented by 4 integers I1, I2, J1 and J2, 0 <= I1 <= I2 < N, 0 <= J1 <= J2 < M. The matrix B contains I2-I1+1 rows and J2-J1+1 columns. The value of B[i][j] is the same as A[i+I1][j+J1], for any i, j such that 0 <= i <= I2-I1, 0 <= j <= J2-J1.
Constraints
-
matrix will contain between 1 and 40 elements, inclusive.
-
Each element of matrix will contain between 1 and 40 characters, inclusive.
-
All elements of matrix will contain the same number of characters.
-
Each character of each element of matrix will be either '0' or '1'.
Examples
0)

????
{"0011",
 "0011",
 "1100",
 "0111"}
Returns: 12
The entire matrix is not erasable because it has an odd number of 0s and all allowed transformations complement an even number of cell values, and therefore maintain the parity of 0s. The contiguous submatrix that consists of the three topmost rows and all columns, however, is erasable. Here we depict a possible succession of steps that erases it:
0011         1100         0000
0011  -N1->  1100  -W1->  0000
1100         1100         0000
The first step complements the topmost 2 rows and the second step complements the leftmost 2 columns.
1)

????
{"0011",
 "1011",
 "0101",
 "1010"}
Returns: 9

2)

????
{"1011",
 "0011",
 "0101",
 "1010"}
Returns: 8

3)

????
{"0000110101010",
 "0111101010111",
 "1110110111011"}
Returns: 13

4)

????
{"11000000000110101101",
 "00111111011101101101",
 "00110011110111100010",
 "10011110111110000111",
 "00111010000000110111",
 "00001101011011010110",
 "11010010100100101100",
 "11101101011011000001",
 "11000010100100111001",
 "11011010100100101010",
 "10110010100100110110",
 "01100010100100111001",
 "10110010100100110011",
 "01110101011011001010",
 "01111101011011001011",
 "00001000010010101011",
 "11100101100100110001",
 "10100100111001010101",
 "11111000001010011110",
 "01110100001110011111"}
Returns: 100
The 10x10 contiguous submatrix that corresponds to rows 5-14 and columns 5-14 is erasable.

[Seabook]

5. MatchMaker From TopCoder, Level: 250(Easy).
It's an interesting puzzle, but pretty easy.

You can get Solution from:

http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/matchmaker


/****************************************************************************************

Problem Statement
????

THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
TOURNAMENT

DEFINITION
Class Name: MatchMaker
Method Name: getBestMatches
Paramaters: String[], String, int
Returns: String[]
Method signature (be sure your method is public):  String[]
getBestMatches(String[] members, String currentUser, int sf);

PROBLEM STATEMENT
A new online match making company needs some software to help find the "perfect
couples".  People who sign up answer a series of multiple-choice questions.
Then, when a member makes a "Get Best Mates" request, the software returns a
list of users whose gender matches the requested gender and whose answers to
the questions were equal to or greater than a similarity factor when compared
to the user's answers.

Implement a class MatchMaker, which contains a method getBestMatches.  The
method takes as parameters a String[] members, String currentUser, and an int
sf:
- members contains information about all the members.  Elements of members are
of the form "NAME G D X X X X X X X X X X"
   * NAME represents the member's name
   * G represents the gender of the current user.
   * D represents the requested gender of the potential mate.
* Each X indicates the member's answer to one of the multiple-choice
questions.  The first X is the answer to the first question, the second is the
answer to the second question, et cetera.
- currentUser is the name of the user who made the "Get Best Mates" request. 
- sf is an integer representing the similarity factor.

The method returns a String[] consisting of members' names who have at least sf
identical answers to currentUser and are of the requested gender.  The names
should be returned in order from most identical answers to least.  If two
members have the same number of identical answers as the currentUser, the names
should be returned in the same relative order they were inputted.

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:

- members will have between 1 and 50 elements, inclusive.
- Each element of members will have a length between 7 and 44, inclusive.
- NAME will have a length between 1 and 20, inclusive, and only contain
uppercase letters A-Z.
- G can be either an uppercase M or an uppercase F.
- D can be either an uppercase M or an uppercase F.
- Each X is a capital letter (A-D).
- The number of Xs in each element of the members is equal.  The number of Xs
will be between 1 and 10, inclusive.
- No two elements will have the same NAME.
- Names are case sensitive.
- currentUser consists of between 1 and 20, inclusive, uppercase letters, A-Z,
and must be a member.
- sf is an int between 1 and 10, inclusive.
- sf must be less than or equal to the number of answers (Xs) of the members.

NOTES
The currentUser should not be included in the returned list of potential mates.


EXAMPLES

For the following examples, assume members =
{"BETTY F M A A C C",
 "TOM M F A D C A",
 "SUE F M D D D D",
 "ELLEN F M A A C A",
 "JOE M F A A C A",
 "ED M F A D D A",
 "SALLY F M C D A B",
 "MARGE F M A A C C"}

If currentUser="BETTY" and sf=2, BETTY and TOM have two identical answers and
BETTY and JOE have three identical answers, so the method should return
{"JOE","TOM"}.

If currentUser="JOE" and sf=1, the method should return
{"ELLEN","BETTY","MARGE"}.

If currentUser="MARGE" and sf=4, the method should return [].
Definition
????
Class:
MatchMaker
Method:
getBestMatches
Parameters:
String[], String, int
Returns:
String[]
Method signature:
String[] getBestMatches(String[] param0, String param1, int param2)

(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

****************************************************************************************/

[Seabook]

6. Comment From TopCoder, Level 500 (Medium)
Qu huanwen again provided an awesome solution. He seems pretty good on solving these issues.

Get Source Code from:

http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/matchmaker

/****************************************************************************************
Problem Statement
????

Comments are an important part of most code, however, in some circumstances, they end up just taking up space, and bandwidth. Your task is to write a class Comment with a method strip, which removes all the comments from a piece of code. For this problem, we will consider only two type of comments: comments starting with "//" and comments starting with "/*" and ending with "*/". The first type of comments removes everything starting from "//" until the end of the line. The second type of comment removes everything, starting at "/*", until the sequence "*/" is found. In addition comments may not be nested in any way. So, as soon as a "/*" comment is opened, everything is commented, until a "*/" is found. Thus the String "/*//*/code", without comments, is "code". Note that even though "//" is present, it does not comment out code, because it is commented out itself, by the comment starting with "/*". Similarly, the neither "//*" nor "///*" open a "/*" comment, because everything after the "//" is already commented out, and thus can not start a comment.
However, it is not enough to simple search for the sequence "//" and "/*", because these could be surrounded by quotes, and thus not a comment. For example, in the code:
String s = "//";
"//" does not start a comment, because it is part of a String. A String begins at a '"', which is not commented. A String ends at the first non-escaped '"'. An escaped quote is one that is preceded by a '\'. Any time a backslash is found, within a string, the next character is escaped, and the two of them together make one character. For example, in java, c++, and c# "\n" represents a new line, "\"" represents a quote, and "\\" represents a single '\' (not two, because the first one escapes the second, and together they make one '\'). Your method must take all of this into consideration when removing comments. It must remove the rest of the line, when a "//" comment is found, and remove characters starting with "/*" up to "*/" whenever a "/*" comment is found. In addition, it must take into account that characters which are part of a String, cannot begin a comment (though they may end a comment which was previously begun by "/*"). You will be given an input String[], code, where each element represents a line of code. Your method should remove all of the commented parts of the code, and return the result. If, after removing commented text, any of the lines have been entirely removed, your return should not contain elements for those lines.
To summarize: Upon finding "//" (not in a String) - remove the entire rest of the line. Upon finding "/*" (not in a String) - remove all character until "*/" Upon finding '"' (not in a comment) - all characters until the next unescaped quote are part of a String, and can not start a comment. Upon finding '\' (in a String) - the next character is escaped, and can not close the String.
Definition
????
Class:
Comment
Method:
strip
Parameters:
String[]
Returns:
String[]
Method signature:
String[] strip(String[] code)

(be sure your method is public)
????

Notes
-
code will not neccessarily be syntactically correct. Your method should remove based simply on the rules above.
-
When removing characters after finding "/*", remove until "*/" is found. Do not worry about the */ being part of a String, as everything between "/*" and "*/" is part of a comment, and thus can not be a String.
-
For the purposes of this problem, characters may only by escaped by '\' when they are within a String.
-
The beginning of a comment must be on one line. Thus if one element ends with '/' and the next element starts with '*', this will not start a comment.
-
"/*" comments may not be nested. After removing comments, "/*/**/*/" becomes "*/"
-
In reality, you would have to deal with code like "char c = '"';//comment" (single quote, double quote, single quote). However, for the purposes of this problem, you should treat such sequences as described above, in which case there are no comments here because the quote starts a String.
Constraints
-
code will contain between 1 and 50 elements, inclusive.
-
Each element of code will contain between 1 and 50 characters, inclusive.
-
Each character of each element of code will be a letter ('a' to 'z' or 'A' to 'Z'), a number ('0' to '9'), a space, or a character from: ;:"',<.>/?[{]}\|`~!@#$%^&*()-_

=+
-
All "/*" comments will be closed by the end of the last element of code.
-
All Strings (uncommented code starting with '"') will be closed before the end of the line they were started on.
Examples
0)

????
{"public class Comment{"
," public String[] strip(String[] code){"
,"//this isn't right!"
,"  return code;"
," }"
,"}"}
Returns:
{ "public class Comment{",
  " public String[] strip(String[] code){",
  "  return code;",
  " }",
  "}" }
We remove the one commented line.
1)

????
{"/*public class Comment{"
," public String[] strip(String[] code){"
,"//this isn't right!"
,"  return code;"
," }"
,"}*/"}
Returns: { }
Here, everything is commented out.
2)

????
{"String s = \"\\\"/**/\\\"\""}
Returns: { "String s = \"\\\"/**/\\\"\"" }
The strings above are doubly escaped so that you can use the {} button in the arena. The actual input and output string are the same and are: String s = "\"/**/\""
3)

????
{"public class Comment{"
," public String[] strip(String[] code){"
," //this isn't right!"
,"  return code;"
," }"
,"}"}
Returns:
{ "public class Comment{",
  " public String[] strip(String[] code){",
  " ",
  "  return code;",
  " }",
  "}" }

4)

????
{"char c = '\"'//\""}
Returns: { "char c = '\"'//\"" }
note again that there are extra escape characters.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved

****************************************************************************************/

[Seabook]

7. Checkers From TopCoder, Level 250(Easy)
No so easy, fun algorithm, but haven't been able to really solve the puzzle.
Only Code Snippet available at this stage.

Get Source Code from:
No Full Solution yet. Only Code Snippet.
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/checkers


/***************************************************************************                                            
Problem Statement
????
THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
TOURNAMENT

PROBLEM STATEMENT

Checkers is a board game played with two players on an 8 by 8 board.  Player 1
is represented by red game pieces and player 2 is represented by black game
pieces.  

There are two types of moves for a game piece.  The first will be referred to
as a simple move.  It involves moving a game piece diagonally 1 space. This
means that the piece would be moved either up 1 space and right 1 space or up 1
space and left 1 space.  Here are examples of a simple move.  ('-' is an
unoccupied space, 'R' is a red piece, 'B' is a black piece, complete board may
not be shown in diagram)


- - - - - - - -        - - - - - - - -  
- - - - - - - -  --->  - - R - - - - -  
- R - - - - - -        - - - - - - - -  
                  or
- - - - - - - -        - - - - - - - -  
- - - - - - - -  --->  R - - - - - - -  
- R - - - - - -        - - - - - - - -  

The second type of move is referred to as a jump.  A jump involves moving over
*one* of the opponents pieces and landing in an empty space.  A jump to the
right would involve a piece moving diagonally two spaces to the right(right two
and up two). Similarly, a jump to the left would involve a piece moving
diagonally two spaces to the left(left two and up two).  See the following
diagrams.

- - - - - - - -        - - - - - - - -  
- - - - - - - -  --->  - - - - R - - -  
- B - B - - - -        - B - B - - - -  
- - R - - - - -        - - - - - - - -  
                  or
- - - - - - - -        - - - - - - - -  
- - - - - - - -  --->  R - - - - - - -  
- B - B - - - -        - B - B - - - -  
- - R - - - - -        - - - - - - - -  

Implement a class Checkers containing a method compute.  compute should return
an int representing the fewest number of moves it will take for player 1 to
move his red piece to the opposite end of the board.  If player 1 cannot get to
the opposite end of the board using the moves described above, compute should
return -1.

DEFINITION
Class Name: Checkers
Method Name: compute
Parameters: String, String[]
Returns: int
Method signature (be sure your method is public): int compute (String startPos,
String[] pieces);

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- pieces will contain between 0 and 50, inclusive, elements.
- Each element of pieces will be in the form "column,row" (quotation marks are
for clarity only) where column and row are integers between 0 and 7, inclusive.
- startPos will be in the form "column,row" (quotation marks are for clarity
only) where column and row are integers between 0 and 7, inclusive.
- No two elements of pieces or startPos can have the same "column,row" value
(that is, no two pieces may be placed on the same square of the board).

NOTES
- Consecutive jumps count as 1 move.
- A game piece's location is not restricted the way it is in "real" checkers
(pieces can be placed at or moved to any unoccupied location on the board).
- To successfully perform either type of move, the destination square must be
on the board and not occupied by another piece. 
- Input will be in coordinate format "x,y" (quotation marks are for clarity
only) where the bottom left spot on the board is "0,0", the bottom right spot
on the board is "7,0", the top left is "0,7" and the top right is "7,7".
- The opposite end of the board is defined as the top row of the board,
specifically, any location on the board where the y (row) coordinate is 7.
-  The red piece can only move or jump in the direction of the opposite end of
the board.  For example, each move or jump (including subsequent jumps in the
case of multiple jumps) must have a row value that is greater than that of the
previous position of that piece.

EXAMPLES
1.
        Fig. 1               Fig. 2              Fig. 3              Fig. 4
  7 - - - - - - - -    7 - - - - - - - -   7 - - - - - - - -   7 - - - - - - R -
  6 - - - - - B - -    6 - - - - - B - -   6 - - - - - B - -   6 - - - - - B - -
  5 - - - - - - - -    5 - - - - - - - -   5 - - - - R - - -   5 - - - - - - - -
  4 - - - - - - - -    4 - - - - - R - -   4 - - - - - - - -   4 - - - - - - - -
  3 B - - - B - - -    3 B - - - B - - -   3 B - - - B - - -   3 B - - - B - - -
  2 - - - - B - - -    2 - - - - B - - -   2 - - - - B - - -   2 - - - - B - - -
  1 - - B - - - - -    1 - - B - - - - -   1 - - B - - - - -   1 - - B - - - - -
  0 - R - - - - - -    0 - - - - - - - -   0 - - - - - - - -   0 - - - - - - - -
    0 1 2 3 4 5 6 7      0 1 2 3 4 5 6 7     0 1 2 3 4 5 6 7     0 1 2 3 4 5 6 7

  startPos = "1,0"
  pieces = {"2,1", "0,3", "4,3", "5,6", "4,2"}
  
  Fig. 1: The initial setup of the board.  Move count = 0; 
Fig. 2: The red piece has made a jump from 1,0 to 3,2 and then from 3,2 to
5,4.  Remember, this only counts as a single move.  Move count = 1; 
Fig. 3: The red piece has made a simple move from 5,4 to 4,5.  Move count =
2; 
  Fig. 4: The red piece has jumped from 4,5 to 6,7.  Move count = 3;

  So the output is: 3
Because the fewest number of moves from startPos to the opposite end of the
board is 3. 

2.
  startPos = "4,4"
  pieces = {}
  return: 3  
 
3.
  startPos = "4,4"
  pieces = {"6,6", "5,5", "3,5", "2,6"}
  return: -1 

4.
  startPos = "4,1"
  pieces = {"2,4", "3,4", "4,4", "5,4", "2,6", "3,6", "4,6", "5,6"}
  return: 3 


Definition
????
Class:
Checkers
Method:
compute
Parameters:
String, String[]
Returns:
int
Method signature:
int compute(String param0, String[] param1)
(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. 

Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. 

(c)2003, TopCoder, Inc. All rights reserved.

***************************************************************************/

[Seabook]

8. Lottery From TopCoder, Level 550(Medium)
Qu huanwen's code.

Get Source Code from:
https://ds-algorithm.googlecode.com/svn/GoogleGroups/src/lottery

/************************************************************************************************
Problem Statement
????
In most states, gamblers can choose from a wide variety of different lottery games. The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number that you may use on your lottery ticket. (All integers between 1 and choices, inclusive, are valid and can appear on your ticket.) blanks represents the number of spots on your ticket where numbers can be written.
The sorted and unique variables indicate restrictions on the tickets you can create. If sorted is set to true, then the numbers on your ticket must be written in non-descending order. If sorted is set to false, then the numbers may be written in any order. Likewise, if unique is set to true, then each number you write on your ticket must be distinct. If unique is set to false, then repeats are allowed.
Here are some example lottery tickets, where choices = 15 and blanks = 4:
{3, 7, 12, 14} -- this ticket is unconditionally valid.
{13, 4, 1, 9} -- because the numbers are not in nondescending order, this ticket is valid only if sorted = false.
{8, 8, 8, 15} -- because there are repeated numbers, this ticket is valid only if unique = false.
{11, 6, 2, 6} -- this ticket is valid only if sorted = false and unique = false.
Given a list of lotteries and their corresponding rules, return a list of lottery names sorted by how easy they are to win. The probability that you will win a lottery is equal to (1 / (number of valid lottery tickets for that game)). The easiest lottery to win should appear at the front of the list. Ties should be broken alphabetically (see example 1).
Definition
????
Class:
Lottery
Method:
sortByOdds

Parameters:
String[]
Returns:
String[]
Method signature:

String[] sortByOdds(String[] rules)

(be sure your method is public)
????

Constraints
-
rules will contain between 0 and 50 elements, inclusive.
-
Each element of rules will contain between 11 and 50 characters, inclusive.
-
Each element of rules will be in the format "<NAME>:_<CHOICES>_<BLANKS>_<

SORTED>_<UNIQUE>" (quotes for clarity). The underscore character represents exactly one space. The string will have no leading or trailing spaces.
-
<NAME> will contain between 1 and 40 characters, inclusive, and will consist of only uppercase letters ('A'-'Z') and spaces (' '), with no leading or trailing spaces.
-
<CHOICES> will be an integer between 10 and 100, inclusive, with no leading zeroes.
-
<BLANKS> will be an integer between 1 and 8, inclusive, with no leading zeroes.
-
<SORTED> will be either 'T' (true) or 'F' (false).
-
<UNIQUE> will be either 'T' (true) or 'F' (false).
-
No two elements in rules will have the same name.
Examples
0)

????
{"PICK ANY TWO: 10 2 F F"
,"PICK TWO IN ORDER: 10 2 T F"
,"PICK TWO DIFFERENT: 10 2 F T"
,"PICK TWO LIMITED: 10 2 T T"}
Returns:
{ "PICK TWO LIMITED",
  "PICK TWO IN ORDER",
  "PICK TWO DIFFERENT",
  "PICK ANY TWO" }
The "PICK ANY TWO" game lets either blank be a number from 1 to 10. Therefore, there are 10 * 10 = 100 possible tickets, and your odds of winning are 1/100.
The "PICK TWO IN ORDER" game means that the first number cannot be greater than the second number. This eliminates 45 possible tickets, leaving us with 55 valid ones. The odds of winning are 1/55.
The "PICK TWO DIFFERENT" game only disallows tickets where the first and second numbers are the same. There are 10 such tickets, leaving the odds of winning at 1/90.
Finally, the "PICK TWO LIMITED" game disallows an additional 10 tickets from the 45 disallowed in "PICK TWO IN ORDER". The odds of winning this game are 1/45.
1)

????
{"INDIGO: 93 8 T F",
 "ORANGE: 29 8 F T",
 "VIOLET: 76 6 F F",
 "BLUE: 100 8 T T",
 "RED: 99 8 T T",
 "GREEN: 78 6 F T",
 "YELLOW: 75 6 F F"}
Returns: { "RED",  "ORANGE",  "YELLOW",  "GREEN",  "BLUE",  "INDIGO",  "VIOLET" }
Note that INDIGO and BLUE both have the exact same odds (1/186087894300). BLUE is listed first because it comes before INDIGO alphabetically.
2)

????
{}
Returns: { }
Empty case

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

************************************************************************************************/

[Seabook]

8. CorporationSalary From TopCoder, Level 250(Easy)
Good OO vs Good Algorithm

Get Source Code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/corporationsalary

/******************************************************************************************************
Problem Statement
????
You are working in the HR department of a huge corporation. Each employee may have several direct managers and/or several direct subordinates. Of course, his subordinates may also have their own subordinates, and his direct managers may have their own managers. We say employee X is a boss of employee Y if there exists a sequence of employees A, B, ..., D, such that X is the manager of A, A is the manager of B, and so on, and D is the manager of Y (of course, if X is a direct manager of employee Y, X will be a boss of employee Y). If A is a boss of B, then B can not be a boss of A. According to the new company policy, the salary of an employee with no subordinates is 1. If an employee has any subordinates, then his salary is equal to the sum of the salaries of his direct subordinates. You will be given a String[] relations, where the j-th character of the i-th element is 'Y' if employee i is a direct manager of employee j, and 'N' otherwise. Return the sum of the salaries of all the employees.
Definition
????
Class:
CorporationSalary
Method:
totalSalary
Parameters:
String[]
Returns:
long
Method signature:
long totalSalary(String[] relations)

(be sure your method is public)
????

Constraints
-

relations will contain between 1 and 50 elements, inclusive.
-
Each element of relations will contain the same number of characters, which is equal to number of elements in relations.
-
Each element of relations will contain only 'Y' or 'N'.
-
Character i of element i of relations will be 'N' for each i.
-
If A is a boss of B, then B will not be a boss of A.
Examples
0)

????
{"N"}
Returns: 1
Here we've got only one employee so the answer is 1.
1)

????
{"NNYN",
 "NNYN",
 "NNNN",
 "NYYN"}
Returns: 5
There are 4 employees here. 0, 1 and 3 are managers of 2, and also 3 is a manager of 1. So: salary(2) = 1 salary(0) = salary(2) = 1 salary(1) = salary(2) = 1 salary(3) = salary(2) + salary(1) = 2
2)

????
{"NNNNNN",
 "YNYNNY",
 "YNNNNY",
 "NNNNNN",
 "YNYNNN",
 "YNNYNN"}
Returns: 17

3)

????
{"NYNNYN",
 "NNNNNN",
 "NNNNNN",
 "NNYNNN",
 "NNNNNN",
 "NNNYYN"}
Returns: 8

4)

????
{"NNNN",
 "NNNN",
 "NNNN",
 "NNNN"}
Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

******************************************************************************************************/

[Seabook]

9. Nestings From TopCoder, Level 350(Easy)
Qu huanwen's solution is way better. Check it out.

Get Source Code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/nestings

/******************************************************************************************************
Problem Statement
????
Many different technical languages use nestings to convey some sort of meaning. Mathematics uses parentheses and brackets very often in expressions to group values. Your method will test whether a given nesting is valid, and if it is, how deep it goes. To be valid, a nesting must obey the following criteria (quotes for clarity): 1) Every left marker has a CORRECTLY matching right marker (i.e. every '[' has a ']'; described in table below) 2) Nestings cannot be interwoven. (e.g. "{[}]" is not a valid nesting since {} and [] are interwoven) In other words, a right marker must be CORRECTLY matched by the left marker immediately preceding it, which has not already been matched. 3) Every nesting marker in the string must delimit a nesting. All other characters must be letters. For example, "{[}" isn't valid since '[' is a marker that does not delimit a nesting. "asdJLBasdf" is valid since letters can exist anywhere in the string. The CORRECTLY matched nesting markers are:
Left         Right
<             >
(             )
[             ]
{             }
/*            */
If there is an invalid nesting your method will return -1. Otherwise you will return the deepest nesting level in the input. For example: Nesting-wise explanations will use numbers to depict nesting depths throughout the given strings. nested = "" no nestings so deepest nesting level is 0 nested = "<(A)(b)>" nesting-wise this looks like <1(2)1(2)1> so the deepest level would be 2 nested = "<()()>" nesting-wise this looks like <1(2)1(2)1> so the deepest level would be 2 nested = "(/*/)" is invalid(-1) since /* is a valid left marker but the / left over is not a valid marker nested = "(*)" is invalid(-1) since * is not a letter and it isn't used as part of a nesting marker As seen in examples above, the nesting depth at any point in a string measures how many sets of markers you are between. If the nesting is valid, your method returns the highest nesting depth occuring in the input string.  Create a class Nestings that contains the method howDeep, which takes a String nested, and returns an int describing the deepest nesting level or -1 if it is invalid.
Definition
????
Class:
Nestings
Method:
howDeep
Parameters:

String
Returns:
int
Method signature:

int howDeep(String nested)

(be sure your method is public)
????

Constraints
-

nested will have a length between 0 and 50 inclusive
-
nested will only contain letters (A-Z,a-z) or characters from: "<>(){}/*[]" (quotes for clarity)
Examples
0)

????
""
Returns: 0
This example is given above.
1)

????
"<(A)(b)>"
Returns: 2
This example is given above.
2)

????
"(/*/)"
Returns: -1

3)

????
"<<<</**/asdf>>>>"
Returns: 5

4)

????
"abcd(A(B(C(D)C)B)A)abcd"
Returns: 4

5)

????
"([)]"
Returns: -1
No interwoven nesting markers allowed.
6)

????
"([{/**/}])"
Returns: 4

7)

????
"("
Returns: -1

8)

????
"]["
Returns: -1

[Seabook]

Attention:
There are some svn links are not correct linked to the related puzzles.
You can browse the correct link by urself by going to the main svn respo.
http://ds-algorithm.googlecode.com/svn/GoogleGroups/

I still don't know how to update the existing post. So I can't correct it. Please pardon me.

Thanks,
Seabook

[Seabook]

10. ArrayTraverse from Google Interview. Level: 250 (Easy)

Google Interview's question, most of them, are not that difficult, pretty confident that I can do most of them.
However, the difficulty is when you doing the interview, you are not as good as you are doing yourself alone. And hard to find
the exact correct direction in one shot.

Get Source Code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/arraytraversal

Array traversal like this:
Input:
1 2 3
4 5 6
7 8 9
Output:
124753689

[Seabook]

11. Write all the possibilities for the  Parentheses ( ). In the interview is write ((())) all the possibilities.
From Google Interview. Difficulty 250 Medium.

Get Source Code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/parens

[Seabook]

12. From TopCoder Level 1000 (Hard) . It's a great feeling when you complete the hard algorithm
Enjoy to solve this complex algorithm. Maybe it's not the best solution.

Get Source Code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/ruleengine/

/*******************************************************************

Problem Statement
????
PROBLEM STATEMENT:

A rule engine is simply a warehouse of tests.  Based on the result of these
tests, actions are taken.  When a set of rules causes an action to be taken,
the rule set is said to "fire".


EXAMPLE Rule Sets:

Example 1:
If the monkey is hungry and the monkey has a banana in it's hand, then the
monkey eats the banana.  The rule set has two rules:
IF:
    (RULE) monkey is hungry
    (RULE) monkey has banana

THEN:
    (ACTION) monkey eats banana.

Example 2:
If X = 2, and Y is between 10 and 15, and Z = 5, then Z = 4.  The rule set has
three rules:
IF:
    (RULE) X = 2
    (RULE) Y between 10 and 15

    (RULE) Z = 5
THEN:
    (ACTION) set Z = 4

DEFINITION:

It is often very important to know when a given state will cause two different
rule sets to fire.  You will be given two rule sets.  Determine whether there

are any data sets that will cause both rule sets to fire. If so, return the
number of such sets within a set of given bounds.  If not, return "0".
The elements of the rule sets are of the form "<X><comparison>data1,data2" or

"<X><comparison>data1" where <comparison> can be "==", "<", "<=", ">", ">=",
"!=", or "B". <X> is a variable name, a single capital letter 'A'-'Z'. The

element would be TRUE if the comparison of the value in <X> to data1 (or data1
and data2) was true. If all elements of the rule set are TRUE, then the rule
set fires (Double-quotes and angle-brackets are for clarity only).


<comparison> legend:
==    X == data1
<    X < data1
<=    X <= data1
>    X > data1
>=    X >= data1
!=    X != data1
B    X is between data1 and data2, inclusive


X represents an integer variable whose range of possible values are specified
by the below rules.

Method signature: String countSets(String[] ruleSet1, String[] ruleSet2)
Be sure your method is public.


TopCoder will enforce the validity of the inputs.  Inputs are considered valid

if all of the following criteria are met:

  *ruleSet1 and ruleSet2 each have between 1 and 7 elements, inclusive.
*each element of ruleSet1 and ruleSet2 is either of the form

"<X><comparison><data1>" where <comparison> is not the letter "B", or of the
form "<X>B<data1>,<data2>" (quotes and angle-brackets are shown for clarity,

they do not appear in the input).
  *<X> is a letter between 'A' and 'Z', inclusive (upper-case only).
*<data1> and <data2> are integers between -9 and 9, inclusive.  Leading zeros

are possible.
  *<comparison> is one of the following: "==", "<", "<=", ">", ">=", "!=", "B".
*If the <comparison> code is 'B', then <data1> will be less than or equal to

<data2>.

Return the number of distinct data sets made up of values between -10 and 10,
inclusive that will cause both rules to fire.
Format the return value as a String.

WORKED EXAMPLES:

ruleSet1 = { "A<1", "B>2" }, ruleSet2 = { "A>1", "BB1,2" }.

Here ruleSet1 will fire if the value in A is less than 1, and the value in B is
greater than 2.  ruleSet2 will fire if the value in A is greater than 1, and
the value in B is between 1 and 2.  The rule sets are mutually exclusive, for A

cannot be both greater than and less than 1 so return "0".

ruleSet1 = { "A<0" }, ruleSet2 = { "A<0" }.
Both rulesets will fire for any value of A between -10 and -1, inclusive.

There are 10 such values, so return "10".

ruleSet1 = { "A==1", "X>=4", "F<1" }, ruleSet2 = { "X>=5", "ZB2,9" }.
ruleSet1 will fire when A is 1, X is greater or equal to 4, and F is less than

1.  ruleSet2 will fire when X is greater than or equal to 5, and Z is between 2
and 9, inclusive.  Both rule sets will fire when:
A is 1.
X is greater than or equal to 5.
F is less than or equal to 0.
Z is between 2 and 9, inclusive.


Hence, the rule sets are not mutually exclusive, so calculate the number of
distinct data sets that can cause the rule set to fire, in which the values are
between -10 and 10, inclusive:

A can only be 1 (1 possible element).

X can be between 5, and 10 inclusive (6 possible elements).
F can be between -10 and 0 inclusive (11 possible elements). 
Z can be between 2 and 9 inclusive (8 possible elements).

The number of distinct data sets that can cause both rule sets to fire within

the given bounds is: 1 * 6 * 11 * 8 = 528.  Return "528".

TEST CASES:

{ "A<1", "B==2", "C>4", "D>=6", "E<=9", "FB1,2", "J!=6" }, { "E>9" } returns "0".

{ "A<01", "B==2", "C>4", "D>=2", "E<=9", "FB1,2", "J!=6" }, { "A<9", "B>=2" }
returns "475200".
{ "A<=9", "B<=9", "C<=9", "D<=9", "E<=9", "F<=9", "G<=9" }, { "H<=9", "I<=9",

"J<=9", "K<=9", "L<=9", "M<=9", "N<=9" } returns "1638400000000000000".
{ "KB-09,5", "K<3" }, { "Y>4" } returns "72".

Definition
????
Class:
RuleEngine
Method:
countSets
Parameters:
String[], String[]
Returns:
String
Method signature:
String countSets(String[] param0, String[] param1)

(be sure your method is public)

????

This problem statement is the exclusive and proprietary 
property of TopCoder, Inc. Any unauthorized use or reproduction of this 
information without the prior written consent of TopCoder, Inc. is 
strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*******************************************************************/

[Seabook]

13. AllButOneDivisor From TopCoder Level 250(Easy) .
Easy and hard. Easy is because everyone knows the algorithm, hard is need to have good match skills.


Get Source Code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/allbutonedivisor/

/*************************************************************************************************************************************
Problem Statement
????
You are given a int[] divisors containing K elements. Find a positive integer n such that exactly K-1 elements of divisors are exact divisors of n. If there are several such numbers n, return the smallest possible one. If no such number n exists, return -1 instead.
Definition
????
Class:
AllButOneDivisor
Method:
getMinimum
Parameters:
int[]
Returns:
int
Method signature:
int getMinimum(int[] divisors)

(be sure your method is public)
????

Notes
-
A number x is an exact divisor of y if y divided by x yields an integer result.
-
If x is an exact divisor of y then we call y a multiple of x.
Constraints
-
divisors will contain between 2 and 6 elements, inclusive.
-
Each element of divisors will be distinct.
-
Each element of divisors will be between 1 and 15, inclusive.
Examples
0)

????
{2,3,5}
Returns: 6
There are many possible values for n in this case. For example: 6, 15, 75 and 12. 6 is the smallest of them.
1)

????
{2,4,3,9}
Returns: 12

2)

????
{3,2,6}
Returns: -1
Every multiple of 3 and 2 is also a multiple of 6. Every multiple of 6 is also a multiple of 2 and 3.  Therefore, a number that is a multiple of exactly 2 out of the three elements in this array cannot exist.
3)

????
{6,7,8,9,10}
Returns: 360

4)

????
{10,6,15}
Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*************************************************************************************************************************************/

[Seabook]

14. LeaguePicks From TopCoder Level 500 (Medium) .
Easiest Level 500 algorithm.

Get Source Code From:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/leaguepicks/


/****************************************************************************************************************************
Problem Statement
????
You and your friends are setting up a fantasy TopCoder league, where you choose coders to be on your team and score points in the league when any one of your coders wins their room or successfully challenges somebody, etc. To be fair, a system has been developed to choose the order in which picks are distributed. It works like this: first, lots are drawn to choose your position in the league. Then the player with the first position gets first pick, the second player gets second pick, all the way until the last player picks. Then the order reverses: the last player chooses again, then the next to last player, and so on, until you reach the first player again. Then the cycle repeats: the first position chooses again, then the second, and so on.
For example: say you were in the third position on a 6 player league. You would get the 3rd pick, then you'd wait until the 10th pick (the order would be 1,2,you,4,5,6,6,5,4,you), and then the 15th pick, and so on until there were no more coders to choose. If there were 20 total picks, then you would get pick numbers 3,10,15.
Not wanting to miss your chance at a pick, your goal is to write a program that tells you what pick numbers you have in the order that you have them. You will receive three ints indicating your position in the league(1 being the first position), the number of friends that are in the league with you, and the number of picks that are being divvied up among the league. You will return an int[] that indicates the picks that you receive in ascending order.
Definition
????
Class:
LeaguePicks
Method:
returnPicks
Parameters:
int, int, int
Returns:
int[]
Method signature:
int[] returnPicks(int position, int friends, int picks)

(be sure your method is public)
????

Notes
-

Note that your position in the league and the pick numbers start at 1 and not 0. This should be clear from the examples.
Constraints
-
position will be between 1 and friends inclusive.
-
friends will be between 1 and 40 inclusive.
-
picks will be between 1 and 40 * friends inclusive.
Examples
0)

????
3
6
15
Returns: { 3,  10,  15 }
Example from above.
1)

????
1
1
10
Returns: { 1,  2,  3,  4,  5,  6,  7,  8,  9,  10 }
You're the only player, so you get all the picks.
2)

????
1
2
39
Returns:
{ 1,  4,  5,  8,  9,  12,  13,  16,  17,  20,  21,  24,  25,  28,  29,
  32,  33,  36,  37 }
You'll get the 1st and 4th picks in every set of 4.
3)

????
5
11
100
Returns: { 5,  18,  27,  40,  49,  62,  71,  84,  93 }
You'll get the 5th and (2*11-5+1) or 18th picks out of every 2*11 picks.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

****************************************************************************************************************************/

[Seabook]

15. Google Interview Algorithm. 
Give you two infinite positive integer, please calculate their sum. (Can't use JDK BigInteger, Long, etc)
Method Signature: public String calculateSum(String infinitePositiveInteger1, String infinitePositiveInteger2)

That's the algorithm I did in the Google Interview.

Get Source code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/bigintegersum/

[Seabook]

16. Prerequisites From Top Coder. Level 1000 (Difficult)
It's not that hard to think about the solution but it's complicated.

Get Source code from:
https://ds-algorithm.googlecode.com/svn/GoogleGroups/src/prerequisites


/****************************************************************************************************************
Problem Statement
????

***Note:  Please keep programs under 7000 characters in length.  Thank you

Class Name: Prerequisites
Mathod Name: orderClasses
Parameters: String[]
Returns: String[]

You are a student at a college with the most unbelievably complex prerequisite
structure ever. To help you schedule your classes, you decided to put together
a program that returns the order in which the classes should be taken. 

Implement a class Prerequisites which contains a method orderClasses.  The
method takes a String[] that contains the classes you must take and returns a
String[] of classes in the order the classes should be taken so that all
prerequisites are met.

String[] elements will be of the form (and TopCoder will ensure this):
"CLASS: PRE1 PRE2 ..." where PRE1 and PRE2 are prerequisites of CLASS.  CLASS,
PRE1, PRE2, ... consist of a department name (3 or 4 capital letters, A-Z
inclusive) followed by a class number (an integer between 100 and 999,
inclusive).  The department name should be immediately followed by the class
number with no additional characters, numbers or spaces (i.e. MATH217).  It is
not necessary for a class to have prerequisites.  In such a case, the colon is
the last character in the String. 

You can only take one class at a time, therefore, use the following rules to
determine which class to take :
1) Any prerequisite class(es) listed for a class must be taken before the class
can be taken.
2) If multiple classes can be taken at the same time, you take the one with the
lowest number first, regardless of department.
3) If multiple classes with the same number can be taken at the same time, you
take the department name which comes first in alphabetical order. 
4) If the inputted course schedule has errors, return a String[] of length 0.
There is an error if it is impossible to return the classes in an order such
that all prerequisites are met, or if a prerequisite is a course that does not
have its own entry in the inputted String[].

Examples of valid input Strings are:
"CSE111: CSE110 MATH101"
"CSE110:"

Examples of invalid input Strings are:
"CS117:" (department name must consist of 3 - 4 capital letters, inclusive)
"cs117:" (department name must consist of 3 - 4 capital letters, inclusive)
"CS9E11:" (department name must be letters only)
"CSE110: " (no trailing spaces allowed)
"CSE110: CSE101 " (no trailing spaces allowed)
"MATH211: MAM2222" (class number to large)
"MATH211: MAM22" (class number to small)
"ENGIN517: MATH211" (department name to large)

Here is the method signature (be sure your method is public):
String[] orderClasses(String[] classSchedule);

TopCoder will make sure classSchedule contains between 1 and 20 Strings,
inclusive, all of the form above.  The Strings will have between 1 and 50
characters, inclusive.  TopCoder will check that the syntax of the Strings are
correct: The Strings will contain a valid class name, followed by a colon,
possibly followed by a series of unique prerequisite classes separated by
single spaces.  Also, TopCoder will ensure that each class has at most one
entry in the String[].

Examples:
If classSchedule={
"CSE121: CSE110",
"CSE110:",
"MATH122:",
}
The method should return: {"CSE110","CSE121","MATH122"}

If classSchedule={
"ENGL111: ENGL110",
"ENGL110: ENGL111"
}
The method should return: {}

If classSchedule=[
"ENGL111: ENGL110"
}
The method should return: {}

If classSchedule={
"CSE258: CSE244 CSE243 INTR100"
"CSE221: CSE254 INTR100"
"CSE254: CSE111 MATH210 INTR100"
"CSE244: CSE243 MATH210 INTR100"
"MATH210: INTR100"
"CSE101: INTR100"
"CSE111: INTR100"
"ECE201: CSE111 INTR100"
"ECE111: INTR100"
"CSE243: CSE254"
"INTR100:"
}
The method should return:
{"INTR100","CSE101","CSE111","

ECE111","ECE201","MATH210","CSE254","CSE221","CSE2
43","CSE244","CSE258"}
Definition
????
Class:
Prerequisites
Method:
orderClasses
Parameters:

String[]
Returns:
String[]
Method signature:

String[] orderClasses(String[] param0)

(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*****************************************************************************************************************************/

[Seabook]

17. Prerequisites From Top Coder. Level 1000 (Difficult)
Awesome solution from Qu huanwen. I tried as well, but my algorithm is way stupid and cause OOM in extreme situation.
There is always a hidden rule or math model behind a problem.

Get Source code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/alephnull


/************************************************************************************************************************************

Problem Statement
????
PROBLEM STATEMENT

The logician Charles Sanders Pierce proposed a procedure for generating and
ordering all of the positive rational numbers. A rational number is an integer
divided by an integer (n/m where both n and m are integers and m does not equal
zero).

The procedure proceeds as follows. Start with the two rationals 0/1 and 1/0
(disregarding the fact that 1/0 is not a valid number). Call this generation 1.
To produce the next generation, insert a new rational in between each pair of
rationals in the current generation by summing the numerators (the number being
divided) of the adjacent rationals to produce the new numerator, and by summing
the denominators (the number doing the dividing) of the adjacent rationals to
produce the new denominator. By repeating this procedure indefinitely, all of
the positive rational numbers will be produced in order in their simplest
rational form.

The first few generations proceed as follows:

G1: 0/1 1/0
G2: 0/1 1/1 1/0
G3: 0/1 1/2 1/1 2/1 1/0
G4: 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
G5: 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0

Code a method that given a generation number and a zero based index, returns
the numerator and denominator of the rational number at the position indicated
by the index within the generation. If the index is not within the range of
values for the given generation, return the special error value having zero for
both the numerator and denominator.

DEFINITION
Class: AlephNull
Parameters: int, int
Returns: int[]
Method signature: int[] rational(int generation, int item)

(be sure your method is public)

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of

the following criteria are met:

* generation is from 1 to 30 inclusive.
* item is from 0 to 999999999 inclusive.

HINT
The number of elements in a given generation can be computed as follows:
elements = (2 ^ (generation - 1)) + 1. (The '^' symbol indicates
exponentiation. For example:
Generation 1: 2^0 + 1 = 2
Generation 2: 2^1 + 1 = 3
Generation 3: 2^2 + 1 = 5
Generation 4: 2^3 + 1 = 9
Generation 9: 2^8 + 1 = 257

EXAMPLES
E1:  1,0        ==> [0,1]
E2:  1,1        ==> [1,0]
E3:  1,2        ==> [0,0]      //error value
E4:  4,1        ==> [1,3]
E5:  4,6        ==> [2,1]
E6:  5,11       ==> [5,3]
E7:  8,70       ==> [9,7]
E8:  10,467     ==> [43,12]
E9:  23,4190316 ==> [438,43]
E10: 30,100     ==> [7,157]
Definition
????
Class:
AlephNull
Method:
rational
Parameters:

int, int
Returns:
int[]
Method signature:

int[] rational(int param0, int param1)

(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

***************************************************************************************************************************/

[Seabook]

17. SameGame From Top Coder. Level 1000 (Difficult)
Qu huawen provided the solution again. He is awesome. Interesting Algorithm and good to conquer this one.

Get Source code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/samegame

/**************************************************************************************************************************
Problem Statement
????
SameGame is a game with a grid of colored blocks. If there are two or more blocks of the same color, all of which are connected, these form a group. More formally, a group is a set of 2 or more blocks, each of which has the same color, in which all pairs of blocks are connected by a sequence of horizontal or vertical steps, each of which moves to a block in the group. A group may be removed only if it is not a subset of some larger group. When a group is removed, all of the blocks above the removed blocks "fall down", meaning that any blocks that are immediately above an empty space move down until they are resting in the bottom row, or immediately above another block. If any entirely empty columns are created then columns to the right of the empty columns shift to the left until all of the empty columns are on the right side. As blocks are removed, points are accumulated based on the number of blocks removed each time. Each time a group of blocks is removed, the point total is increased by n*(n-1)/2 where n is the number of blocks in the group. Additionally, if every single block has been removed from the grid by the end of the game, the final score is multiplied by 4.  The input will be formatted as a String[], board, where each element represents a row of blocks, and each character tells which color a given block is.  For example, {"RBB","RRR","RBB"} represents:
        RBB
        RRR
        RBB
Where 'R' and 'B' are the only two colors present.  One possible sequence of moves would be to first remove the five 'R's, which are all connected and form a group. This would give us 10 points (5*4/2) and make the board look as follows: (where '-' represents empty space):
        -BB
        ---
        -BB
Now the pieces fall down and shift to the left, giving:
        ---
        BB-
        BB-
If we then remove the group of 4 B's, we get an additional 6 points. This removes all of the blocks so we multiply the total (16) by 4, and our final score is 64.  If the board is small enough, we can simply use brute force to find the optimal sequence of groups to remove to obtain the highest score. However, as the number of blocks grows, brute force quickly becomes infeasible. Thus, in order to write a program that plays well, we must use some intelligent technique to remove pieces - albeit a sub-optimal one. One important observation to make in trying to come up with a good strategy is that the number of points grows non-linearly, and we get more points per block if we remove larger groups. This suggests that we should save one color for last, and remove smaller groups first. Your task is to implement the following strategy:  You will be given a String, order, defining an ordering on the colors. You should always remove groups whose color appears earlier in order. So, if order were "RB", we would never remove a group of 'B's if there were a group of 'R's we could remove. When there are many groups of the same color, remove groups with less blocks in them first. If there is a tie, remove the group which extends into (has at least one character in) the lower indexed element of the board. If there is still a tie, remove the group which contains the lower indexed character in the lowest indexed element that both groups extend into. Using this method, continue removing groups until there are none left and then return the final score.
Definition
????
Class:
SameGame
Method:
getScore
Parameters:
String[], String
Returns:
int
Method signature:
int getScore(String[] board, String order)

(be sure your method is public)
????

Constraints
-
board will contain between 1 and 50 elements, inclusive.
-
Each element of board will contain between 1 and 50 characters, inclusive.
-
Each element of board will contain the same number of characters.
-
Each character of each element of board will be an uppercase letter ('A'-'Z').
-
order will contain between 1 and 26 uppercase letters, inclusive.
-
No character will occur more than once in order.
-
Each character in board will also be in order.
Examples
0)

????
{"RBB",
 "RRR",
 "RBB"}
"RB"
Returns: 64
This is the example from the problem statement.
1)

????
{"ABCD",
 "ABCD",
 "ABCD",
 "ABCD"}
"ABCD"
Returns: 96
Here, we end up removing one column at a time, starting with the 'A's, and ending with the 'D's. After we remove each column, the remaining ones shift to the left. Each column gives us 4*3/2 points, for a total of 24 points. Since we can remove all of the blocks, we get a final score of 96.
2)

????
{"ABCD"}
"ABCD"
Returns: 0

3)

????
{"ACCAA",
 "ABAAA",
 "ABBBA",
 "AAACD"}
"EABCD"
Returns: 28
First, we remove the 'L' shaped group of six 'A's, drop the blocks over empty space, and then shift left to get the following ('-' denotes empty space):
    --AA-
    CCAA-
    BABA-
    BBCD-
Next, we remove the group of 5 'A's and end up with:
    -----
    CC---
    BAB--
    BBCD-
Finally, we remove the 3 'B's and get this board, which contains no groups:
    -----
    -----
    -CB--
    CACD-
4)

????
{"ABABABABABABABABABAB",
 "ABABABABABABABABABAB",
 "CDCDCDCDCDCDCDCDCDCD",
 "CDCDCDCDCDCDCDCDCDCD",
 "EFEFEFEFEFEFEFEFEFEF",
 "EFEFEFEFEFEFEFEFEFEF",
 "GHGHGHGHGHGHGHGHGHGH",
 "GHGHGHGHGHGHGHGHGHGH",
 "IJIJIJIJIJIJIJIJIJIJ",
 "IJIJIJIJIJIJIJIJIJIJ",
 "KLKLKLKLKLKLKLKLKLKL",
 "KLKLKLKLKLKLKLKLKLKL",
 "MNMNMNMNMNMNMNMNMNMN",
 "MNMNMNMNMNMNMNMNMNMN",
 "OPOPOPOPOPOPOPOPOPOP",
 "OPOPOPOPOPOPOPOPOPOP",
 "QRQRQRQRQRQRQRQRQRQR",
 "QRQRQRQRQRQRQRQRQRQR",
 "STSTSTSTSTSTSTSTSTST",
 "STSTSTSTSTSTSTSTSTST",
 "UVUVUVUVUVUVUVUVUVUV",
 "UVUVUVUVUVUVUVUVUVUV",
 "WXWXWXWXWXWXWXWXWXWX",
 "WXWXWXWXWXWXWXWXWXWX",
 "YZYZYZYZYZYZYZYZYZYZ",
 "YZYZYZYZYZYZYZYZYZYZ",
 "WXWXWXWXWXWXWXWXWXWX",
 "WXWXWXWXWXWXWXWXWXWX",
 "UVUVUVUVUVUVUVUVUVUV",
 "UVUVUVUVUVUVUVUVUVUV",
 "STSTSTSTSTSTSTSTSTST",
 "STSTSTSTSTSTSTSTSTST",
 "MNMNMNMNMNMNMNMNMNMN",
 "MNMNMNMNMNMNMNMNMNMN",
 "QRQRQRQRQRQRQRQRQRQR",
 "QRQRQRQRQRQRQRQRQRQR",
 "OPOPOPOPOPOPOPOPOPOP",
 "OPOPOPOPOPOPOPOPOPOP",
 "KLKLKLKLKLKLKLKLKLKL",
 "KLKLKLKLKLKLKLKLKLKL",
 "IJIJIJIJIJIJIJIJIJIJ",
 "IJIJIJIJIJIJIJIJIJIJ",
 "GHGHGHGHGHGHGHGHGHGH",
 "GHGHGHGHGHGHGHGHGHGH",
 "EFEFEFEFEFEFEFEFEFEF",
 "EFEFEFEFEFEFEFEFEFEF",
 "CDCDCDCDCDCDCDCDCDCD",
 "CDCDCDCDCDCDCDCDCDCD",
 "ABABABABABABABABABAB",
 "ABABABABABABABABABAB"}
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
Returns: 2720

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved

***************************************************************************************************************************/

[Seabook]

19. SpeedRadar From Top Coder. Level 500(Medium)
The easiest Level 500 algorithm we've ever met.

Get Source code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/speedradar

/***************************************************************************************************************************
Problem Statement
????
A speed radar is installed in a highway zone where the maximum speed limit is maxLimit mph, and the minimum speed limit is minLimit mph. Any reading that is strictly above or below this interval is an infringement.
Periodically, the radar readings are analyzed to make sure that the sensors are working properly. It is assumed that most drivers obey speed limits, and therefore, the radar will be considered faulty if more than 10% of its readings are infringements.
Given the radar readings over a period of time, return the average speed of all cars that are driving within the speed limits. If the radar is faulty, return 0.0.
Definition
????
Class:
SpeedRadar
Method:
averageSpeed

Parameters:
int, int, int[]
Returns:

double
Method signature:
double averageSpeed(int minLimit, int maxLimit, int[] readings)

(be sure your method is public)
????

Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
maxLimit will be between 1 and 200, inclusive.
-
minLimit will be between 1 and maxLimit, inclusive.
-
readings will contain between 1 and 50 elements, inclusive.
-
Each element of readings will be between 1 and 200, inclusive.
Examples
0)

????
1
50
{45, 40, 50}
Returns: 45.0
With all drivers within the speed limits, the return value is just the average speed.
1)

????
1
50
{42,43,44,45,46,47,48,49,50,

51}
Returns: 46.0
There is only one driver infringing the limit, and it represents 10% of the total readings. The average speed of the other readings is 46.0.
2)

????
1
50
{42,46,48,50,52}
Returns: 0.0
Only one reading is outside the given limits, but it represents 20% of the total number of readings. We therefore assume that the radar is not working and return 0.0.
3)

????
20
60
{25,45,45,43,24,9,51,55,60,34,61,23,40,40,47,49,33,23,47,54,54}
Returns: 41.68421052631579

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
**************************************************************************************************************************/

[Seabook]

LAST BUT NOT LEAST BEFORE GOOGLE INTERVIEW ALGORITHM.
THE THREAD WILL BE CLOSED AFTER THIS ONE. AND I WILL OPEN A NEW ONE FOR THE NEW ALGORITHMS.

20. PackageShipping From Top Coder. Level 500(Medium)
Not sure whether it's correct, may have some bugs.

Get Source code from:
http://ds-algorithm.googlecode.com/svn/GoogleGroups/src/packageshipping

/*****************************************************************************************************************************
Problem Statement
????
Shipping is a complicated business, particularly when you are shipping fragile items. To do well, you need to deliver packages quickly, at a low cost, and without breaking them. To this end, you would like software to help you send a package, given the package's cost and the maximum delivery time. There are a number of different routes that are continually traversed by your fleet of trucks. Each route takes a certain amount of time, and it costs a certain amount to send a package along that route. Furthermore, there is a probability associated with each route indicating the percent chance that a package will be damaged along that route.  As the shipping company, you must pay the cost of an item if it is damaged during shipping. Your goal is to find the way to ship an item with the lowest expected cost. For example, if one shipping plan has a cost of X, but a 50% probability of damaging an item, it might end up with a higher expected cost than a plan that has a cost of 2X but only a 5% chance of damaging an item.  You will be given a String[], routes, each element of which represents a single route and will be formatted as "ORIGIN DESTINATION TIME COST PROBABILITY" where ORIGIN and DESTINATION are city codes (sequences of uppercase letters), TIME is an integer between 1 and 50, COST is an integer between 1 and 20, and PROBABILITY is a real number between 0 and 10, all ranges inclusive. The inputs origin and destination are the starting and ending points for the package to be delivered. time is the maximum allowed delivery time, and is in the same units as TIME in routes. cost is the cost of the package, and is in the same units as COST in routes. You should find the shipping plan with the lowest expected cost, and return that cost as a double.
Definition
????
Class:
PackageShipping
Method:
ship
Parameters:
String[], String, String, int, int
Returns:
double
Method signature:
double ship(String[] routes, String origin, String destination, int time, int packageCost)

(be sure your method is public)
????

Notes
-

A route from A to B does not imply a route from B to A.
-
You may assume that there is no waiting time when a package is transferred from one route to another.
-
You won't know that a package is damaged until it reaches its destination, so you must still send it all the way to the destination, even if it is damaged at the beginning of the trip.
Constraints
-
routes will contain between 1 and 50 elements, inclusive.
-
Each element of routes will be formatted as "ORIGIN DESTINATION TIME COST PROBABILITY", with no double, leading or trailing spaces.
-
Each element of routes will contain between 9 and 50 characters, inclusive.
-
ORIGIN and DESTINATION will each be sequences of uppercase letters ('A'-'Z')
-
In no element of routes will ORIGIN equal DESTINATION.
-
TIME will be an integer between 1 and 50, inclusive, with no leading zeros.
-
COST will be an integer between 1 and 20, inclusive, with no leading zeros.
-
PROBABILITY will be between 0 and 10, inclusive, and will be formatted as a sequence of 1 or more digits ('0'-'9') and an optional decimal point (extra leading/trailing zeros allowed).
-
origin will be a sequence of uppercase letters matching an ORIGIN in some element of routes.
-
destination will be a sequence of uppercase letters matching a DESTINATION in some element of routes.
-
time will be between 1 and 100, inclusive.
-
packageCost will be between 1 and 1,000,000,000, inclusive.
-
There will be some way to deliver the package in the given amount of time or less.
-
No two elements of routes will have the same origin and destination.
-
origin and destination will not be the same.
Examples
0)

????
{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
100
100
Returns: 7.392000000000005
There are two possibilities here. We can ship the package through either CHICAGO or MEMPHIS. If we ship the package through CHICAGO, it will cost us 5, and there will be a 2.392% chance that it will be damaged. If we ship through MEMPHIS, it will cost 11, but there will only be a 1.099% chance of damage. Since the package has a cost of 100, the first option will have an expected cost of 7.392, while the second will have an expected cost of 12.099.
1)

????
{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
100
10000
Returns: 120.90000000000055
Here we have the same shipping routes as example 0, but for a more expensive package. Shipping through CHICAGO will have an expected cost of 5 + 239.2 = 244.2, while MEMPHIS will have an expected cost of 11 + 109.9 = 120.9.
2)

????
{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
36
10000
Returns: 244.20000000000053
In this case, the time constraint forces us to send the package along the more expensive route through CHICAGO.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*********************************************************************************************************************************/

[Seabook]

I took some time to arrange all the algorithms we did for the Google Interview. And commit them in the SVN.
http://ds-algorithm.googlecode.com/svn/GoogleGroups/

Glad to see there are more than 20 algorithms we've been finished and some of them are really tough. But it's a
good fun to convert your thoughts to programming language and help you to resolve the issue.

I will close this thread as it's lengthy enough and i will re-open a thread to collect the new algorithms after a while.

Thanks,
Seabook