Tech Life On The Way

/*** There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Would you rather go first or second? Does it matter? Assume that you go first, describe an algorithm to compute the maximum amount of money you can win. eg. int a[] = { 3, 2, 2, 3, 1, 2 } Note: 1. array is unsorted 2. the guaranteed win strategy compute the sum of odd and the sum of even (the index of coin) if even > odd, every round, only picked the even coin otherwise, only picked the odd coin 3. the maximum amount of money you can win (different with 2.) Recursive, consider the way to compute subset sum http://leetcode.com/2011/02/coins-in-line.html ***/ #include <iostream> using namespace std; int maxWin( int * a , int index_x , int index_y , int sum ) {        //base cas...

/*** Implement regular expression matching with support for ‘.’ and ‘*’. "." can be any single character "x*" can represent any # of preceding character, eg "xxx","xx"... 1. API: s and p are char linked list? 2. both s and p can contain matching character".""*", or just p if *s = *p (check next p is '*') http://leetcode.com/2011/09/regular-expression-matching.html ***/ #include <iostream> #include <string> using namespace std; bool isMatch( const char * s , const char * p ) {        //base case        if (* s == '\0' && * p == '\0' )               return true ;        // p next is not '*'        if (*( p +1) != '*' ) {               if (* s != * p &...

/*** Word Break Problem ***/ #include <iostream> #include <string> #include <vector> using namespace std; #define MAX_LEN 8 bool dictionaryContains( string word ) {        string dictionary[] = { "mobile" , "samsung" , "sam" , "sung" , "man" , "mango" ,               "icecream" , "and" , "go" , "i" , "like" , "ice" , "cream" };        int size = sizeof (dictionary)/ sizeof (dictionary[0]);        for ( int i = 0; i < size; i++)               if (dictionary[i].compare( word ) == 0)                      return true ;        return false ; } void split_word( string...

/*** Rat in a Maze A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down. In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination. Note that this is a simple version of the typical Maze problem. For example, a more complex version can be that the rat can move in 4 directions and a more complex version can be with limited number of moves. IDEA: Similar with Robot walking. Start from maze[N-1][N-1], find the path back to maze[0][0]. check the validation before move. maze[m][n], two direction,maze[m-1][n] and maze[m][n-1]. ***/ #include <iostream> #include <vector> using namespace std; #define N 4 //width of Maze struct point {   ...