Cracking the Coding Interview Moderate: 2015

Monday, October 5, 2015

[19.11] two sum, print all pairs

1. Example

s={1,3,5,6,7}
sum = 8 => {1,7} and {3,5}

2. Implementation

public List> void printPairsSums(int[] array, int sum)
{

    


      List> res = new ArrayList>();




      // validate the input
      //if ( array == null || array.length == 0)
      if ( array == null || array.length < 2 )
           return res;




      Arrays.sort(array);




     
      int l = 0; 
      int r = array.length-1;
      while(  l < r )
      {

           if (array[l] + array[r] == sum )
           {  
                List item = new ArrayList<>();
                 item.add(array[l]);
                 item.add(array[r]);
                 res.add(item);
                 l++;
                 r--;
                 // avoid duplicate
                 //while( l < array.length && array[l] == array[l-1] )
                 while ( l < r && array[l] == array[l-1] )
                     l++;
                 //while( r >= 0 && array[r] == array[r+1] )
                 while ( l < r && array[r] == array[r+1]  )
                     r--;
           }
           else if ( array[l] + array[r] > sum )
               r--;
           else 
               l++;
      } 



      return res;



}

3. Similar Ones

[19.10] Implement rand7() using rand5()

1. Example
rand7()
(0-6)+1 =(1-7)
Generate 0~6 from rand5()

rand2()
-> 1/2 probability to be 0
-> 1/2 probability to be 1

(0-1)+1 = (1-2)

rand7()
(0-6)+1 =(1-7)

(0,6) <= (1-21)%7=1,2,3,4,5,6,0,1,...21%7=0 = > 0~6

rand2() to generate 3 the probability is 3 since it should be as random as rand3()
rand3()

2. Implementation

public static int rand7()
{
     while (true)
     {
           // 5* (0~4) + (0~4) = (0~20)+(0~4) = (0~24)
           int num = 5*( rand5() -1 ) + ( rand5() -1 );
           if (  num < 21 )
           {
                // ( 0~20 ) %7
                //   0,1,2,3,4,5,6,0,1,2,3,4,5.....18%7=4,19%7=5,20%7=6
                return (num%7+1);
           }
     }
}

3. Similar ones

[19.9] Compress XML (encoding XML)

1. Example

<family lastName="McDowell" state="CA">
<person firstName="Gayle">Some Message</person>

</family>

Element --> Tag Attributes END(tag head end) Children END(tag tail end)

Attribute --> Tag Value

END --> 0

Tag --> some predefined mapping to int

Value --> string value END()

family -> l, person ->2, frstName ->3, LastName -> 4j state -> 5).

<person firstName="Gayle">Some Message</person>

</family>

Becomes:

1 4 McDowell 5 CA 0 2 3 Gayle 0 Some Message 0 0

// 1. Read tag name // Image

// 2. Read attributes
// 3. End of TagHead

// 4. End of tag , /> OR >
// 1. TagHead

// 2. Attribute

// 3. TagHead End

// 4. Tag Value

// 5. Tag's Children

// 6. TagTail End
<note>
<to>Tove</to>
<from>Jani</from>
<heading>Reminder</heading>
<body>Don't forget me this weekend!</body>
</note>

02
03Tove 01
04Jani 01
05Reminder 01
06Don't forget me this weekend! 01
01

<note date="12/11/2007">
<to>Tove</to>
<from>Jani</from>
</note>

http://chimera.labs.oreilly.com/books/1234000001805/ch24.html#the_butler_did_it

@XmlRootElement
public class Person {
    public String name;
    public Address address;
    public int age;
}
public class Address {
    public String city, street;
    public int number, zip;
}

<person>
    <name>Pat Niemeyer</name>
    <address>
        <city>St. Louis</city>
        <street>Java St.</street>
        <number>1234</number>
        <zip>54321</zip>
    </address>
    <age>42</age>
</person>

<!-- Simple -->
<Sentence>This is text.</Sentence>

<!-- Element -->
<Paragraph><Sentence>This is text.</Sentence></Paragraph>

<!-- Mixed -->
<Paragraph>
        <Sentence>This <verb>is</verb> text.</Sentence>
</Paragraph>

<!-- Empty -->
<PageBreak></PageBreak>

Attributes

<Document type="LEGAL"id="42">...</Document>
<Image name="truffle.jpg"/>

2. Implementation

Part1: Encoding



private Map tagMap; // tag gets mapped to a pre-defined integer value
private static final Byte[] END={0,1};
private List tokens;
private int currentTokenIndex;




byte[] encode(char[] input) throws IOException
{
     


     // STEP1:   Process Input      
     tokenize(input);
     currentTokenIndex = 0;





     // STEP2:   Encode processed input
     ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
     encodeTokens(outputStream);
   


}
void encodeTokens(ByteArrayOutputStream output)
{



     
     // 
     nextToken("<");



  
     // 1. Read tag name // Image
     String tagName = nextToken();
     output.write( getTagCode(tagName)  );




     // 2. Read attributes
     while ( !hasNextToken(">") &&  !hasNextTokens("/", ">")    )
     {



          // read next attribute
          String key = nextToken();   // name
          nextToken("=");             // =
          String value = nextToken(); // "truffle.jpg"



          
          output.write(  getTagCode(key)  );
          for(char c: vlaue.toCharArray() )
              output.write(c);
          // NOTE: after attribute value, it is the End
          output.write(END[0]);
          output.write(END[1]);
                


     }     




     // 3. End of TagHead
     output.write(END[0]);
     output.write(END[1]);    




     // 4. End of tag ,  /> OR >
     // CASE1: Attribute End like 
     if ( hasNextTokens("/", ">")) //  />
     {
          nextToken("/");
          nextToken(">");
     }
     // CASE2: Tag End like Gambardella, Matthew
     else 
     {




          nextToken(">");




          while(  !hasNextTokens("<","/"))
              encodeTokens(output); // Encode child
    


    
          // Encoding tag, 
nextToken("<");
          nextToken("/");
          nextToken(tagName);
          nextToken(">");




     }





     // NOTE: end of tag
     output.write(END[0]); 
     output.write(END[1]);





     

}

      Ralls, Kim
      Midnight Rain
      Fantasy
      5.95
      2000-12-16
      A former architect battles corporate zombies, 
      an evil sorceress, and her own childhood to become queen 
      of the world.

Part2: Compress further

You can treat file as a general stream of characters and use any number of comparison techniques: Shannon-Fano coding, Huffman coding or Arithmetic coding

//assuming a mapping of 
// family -> 1, 
// person ->2, 
// firstName -> 3
// lastName -> 4
// state -> 5
//                                       
// 
//    Some Message
// 
// Becomes:
//    1 4 McDowell 5 CA 0 2 3 Gayle 0 Some Message 0 0.




void encode(Element root, StringBuffer sb)
{

     // validate the input
     if (root == null)
          return;



     // 1. TagHead 
     encode(root.getTagName(), sb);




     // 2. Attribute
     for (Attribute a: root.attributes())
     {
          encode(a, sb);
     }



     // 3. TagHead End
     encode("0",sb);
     


     // 4. Tag Value
     if ( root.hasValue())
         encode(root.getVlaue(), sb);


   
     // 5. Tag's Children
     for (Element e: root.children())
     {
         encode(e, sb);
      }



     // 6. TagTail End
     encode("0", sb);



}



void encode(String s, StringBuffer sb)
{
     sb.append(s).append(" ");
}




void encode(Attribute a, StirngBuffer sb)
{
     encode(a.getTagName(), sb);
     encode(a.getValue(), sb);
}





class Element
{
     String getTagNmae() {return null;}
     Attribute[] attributes() {return null;}
     Element[] children() {return null;}
     String getValue() {return null;}
     boolena hasValue() {return false;}
}
class Attribute
{
     String getTagName() {return null;}
     String getValue() {return null;}
}

3. Similar Ones
https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap17/Q10.java

[19.8] Find the frequency of occurrences of any given word in a book

1. Example

HahsMap
key => toLowerCase, trim()
// validate the input

if (book == null || book.length == 0 || word == null)

return -1;

"Book description is date ,Book description is date , is date ,"

"book" , 2
"description", 2
"date", 3
"is", 3

// validate the input

if (book == null || book.length == 0 || word == null)

return -1;

str = str.toLowerCase();
if ( str.trim() != "" )
{

2. Implementation

// Solution: Single query
// Time:O(n)
Count the number of times a word appears

public int getWordFrequency (String[] book, String word)
{




     // validate the input
     if (book == null || book.length == 0 || word == null)
         return -1;




    HAshMap map =  wordFrequency(book);
    word = word.toLowerCase;
    if (   map.containsKey(word) )
    {
           return map.get(word);
    }




     return 0;

 

}
//public void WordFrequencyTable(String[] book)
public HashMap wordFrequency(String[] book)
{



     HashMap  map = new HashMap<>();



     // validate the input
     if (book == null || book.length == 0)
         return map;



     for (int i =0 ; i< book.length;i++)
     {
          String str = book[i];
          str = str.toLowerCase();
          if ( str.trim() != ""  )
          {
               if (  !map.containsKey(str) )
                     map.put(str,1);
               else
                     map.put(str, map.get(str)+1);
          }
     }
    

     
     return map;



}

3. Similar Ones

[19.7] Find the continuous sequence with the largest sum

1. Example

Input :{2,-8,3,-2,4,-10}
Output: the largest sum is 5 <=== {3,-2,4}

{-3,-10,-5}
A) -3
B) 0
c) Minimum_Int
==> B

2. Implementation

public int getMaxSum(int[] a)
{





     // vlaidate the input
     if ( a== null || a.length == 0)
         return Integer.MIN_VALUE;




     int local = a[0];
     int global = a[0];
     




     for (int i =1; i < a.length;i++)
     {
          local = Math.max(local+a[i],a[i]);
          global = Math.max(local, global);
     }



     

     return global;




}

 l=2, g =2, s= 2
i =1 , -8
 l = max(s-8, -8) = -6
 g = max(-6,2) = 2
i=2, 3
 l = max(-6+3, 3) = 3
 g = max(2, 3)   = 3
i=3,-2
 s = -7
 l=max(3+-2, -2) = 1
 g = max(3,-2) = 3
i=4, 4
  l = max(1+4,4) = 5
  g = max(5,3) = 5

3. Similar ones

[19.6] Number to English Words

1. Example

Prepend initialize string as " One" with space ahead.
1.static final level2= {""," Thousand"," Million"," Billion"}

while( num != 0)

if ( num % 1000 != 0) {
s = covert(num%1000) + level2[level] + s;

}
level++;
num/=1000;

static final level0 = {"", " One"," Two"," Three"," Four"," Five"," Six"," Seven"," Eight"," Nine"," Ten"," Eleven"," Twelve"," Thirteen"," Fourteen"," Fifteen"," Sixteen"," Seventeen"," Eighteen"," Nineteen"}

static final level1 = {" Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"}

if ( num > 99 ) {

res = leve0[num/100] + " Hundred";

}

num%= 100;

if ( num < 20 )

res = res + level0[num];

else

res = res + level1[num/10 -2] + level0[num%10];

1,234 => "One Thousand, Two Hundred and Thirty Four"
1,000,999 => "One Million Nine Hundred Ninety Nine"
2,147,483,647 => "Two Billion 147 Million 483 Thousand 647"

// NOTE :1 000 999

if ( num % divisor != 0) {

s = covert(num%divisor) + level2[level] + s;

}

2. Implementation

public static String numToString(int num)
{





       static final level0 = {"", " One"," Two"," Three"," Four"," Five"," Six"," Seven"," Eight"," Nine"," Ten"," Eleven"," Twelve"," Thirteen"," Fourteen"," Fifteen"," Sixteen"," Seventeen"," Eighteen"," Nineteen"}
       static final level1 = {" Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"}
       //static final level2= {"Thousand ","Million ","Billion "}
       // NOTE: loop every time, so we need to set up first unit as ""
       static final level2= {""," Thousand"," Million"," Billion"}






      // validate the input
      if (num == 0)
            return "Zero";






      int divisor = 1000;
      //int val = num % divisor;
      //String s = convert(val);
      String res = "";
      int level = 0;
      //while (num / divisor > 0)
      while( num != 0)
      {
           // NOTE :1 000 999
           if (  num % divisor != 0)
           {
                res = covert(num%divisor) + level2[level] + res;
           }
           num/= divisor;     
      } 




       return res.trim();



}

private String convert(int num)
{




       String res="";
       if ( num > 99 )
       {
            res = leve0[num/100] + " Hundred";
       }



       num%= 100;



       
       if ( num < 20 )
            res = res + level0[num];
       else 
            res = res + level1[num/10 -2] + level0[num%10];

 


       return res;




}

3. Simialr ones

[19.5] Game of Master Mind

1. Example
Bit Vector STORE alphabet into corresponding pos
Return more than two variables = > create a class

R Y G B

Case1: R G G B
Gues1: Y R G B

p-hit hit hit
=> ONLT told : 1 p-hit and 2 hits

check color and position =>
current hit = 0;
if color match and position match => current hit =2 ( hit)

if color match => current hit = 1 (p-hit)
O(n^2) => O(n) bit vector, int has 32 bit enough for 26 alphabets,

2. Implementation

// Assume all Capital

public static class Result
{
    public int hits; 
    public int pseudoHits;
}

public static Result estimate(String guess, String solution)
{





    Result res = new Result();

   



    // validate the input
    if (guess == null || solution == null)
       return res;




    int solution_mask = 0;
    for (int i = 0; i < 4; i++ )
    {
         int val = solution.charAt(i) - 'A'; // 'A'->0, 'B'->1, 'C'->2
         // NOTE :Set bits
         solution_mask |= 1<<(1+val);// 'A'->1, 'B'->2, 'C'->3, 26 aplhabets
    }


    

    for (int i = 0 ; i < 4 ; i ++)
    {
          if (guess.charAt(i) == solution.charAt(i))
               ++res.hits;
          // NOTE: Test bits
          else if (  (solution_mask  &  ( 1<< (1+guess.charAt(i) - 'A') )) >=1  )      
               ++res.pseudoHits;
    }



    return res;



}

3. similar Ones

[19.4] Find the maximum of two numbers WIHTOUT if-else or any other comparison operator

1. Example
int a,b
Math.max(a,b)
Input: 5,10
Output: 10

1. 5<10 X, can not have <
2. 5 -10 =-5 <0 X, can not have <
3. 5 - 10 = -5 = -101 => 010 + 1 = 011 => 1111 1111 .....1011
Negative means the most significant bit is 1
4. 5-10 = -5 ==> 5 - (-5) = 10-> Max
=== =======> a - sigBit*(a-b)
5. E.g., 10,5 ===> 10 - 0*(10-5) = 10
E.g., 5, 10===> 5 - 1*(5-10) = 10

2. Implementation

public int getMax(int a , int b)
{
       int c = a-b;
       int sigBit = (c >> 31) & 0x1;
       int max = a - sigBit*c;
       return max;
}

3. Similar ones

[19.3] the number of trailing zeros in N factorial

1. Example

5! = 1*2*3*4*5 = 120 -> 1 zero -> depends on # of 5s
O 1
26! = 1*2*3*4*5...*10*....*15*..*20*..*25
1 1 1 1 2

int count = 0;

for (int i = 5; N / i > 0; i*=5 )

{

count += N / i;

}
2. Implementation

public static int numZeros(int N)
{




    // validate the input
    if ( N < 0 )
    {
       System.out.println("Factorial is not defined for < 0");
       return 0;
    }
           




    int count = 0;
    for (int i = 5; N / i > 0; i*=5 )
    {
         count += N / i;// 45 = 5*9, (5,10,15,20,25,30,35,40,45)
    }




    return count;




}

3. Similar Ones Rule up front so that you can implement this correctly

Sunday, October 4, 2015

[19.2] Won a tic-tac-toe game

1. Example

O won = >
row 0 => matrix[0][0] ='O'
matrix[0][1] ='O'
matrix[0][2] ='O' => return 'O'
row 1 => matrix[1][0] ='X'
matrix[1][1] ='X'
matrix[1][2] ='' => return EMPTY
row 2 => matrix[2][0] ='X'
matrix[2][1] ='' => return EMPTY
matrix[2][2] =''

OOO
XX
X

2. Implementation
1. Call Once :

2. Call Multiple Times: amortizing the cost by designing your own data storage system for the tic-tac-board

// Approach#1 : If hasWon is called many times
// There are only 3^9, or about twenty thousand tic-tac-toe boards
// every cell has O, X or empty choices. There are 9 cells and so there
// are 3^9 boards
// We can represent our tic-tac-toe board as an int, with each digit 
// representing a piece (0 menas Empty, 1 means Red, 2 means Blue)
// We set up a hashtable or array in advance with all possible boards
// as keys, and the values are 0,1 and 2. Our function then is simply 
// this
// OOO
// XX
// 
// => O Won= > O means 1
int hasWon(int board)
{
    return winnerHashtable[board];
}

// Approach#2: If hasWon is called only once
// check every column, row, diagonal, reverse diagonal, if any of 
// Piece continue
enum Piece{Empty, Red, Blue}
enum Check {Row ,Column, Diagonal, ReverseDiagonal}

Piece getIthColor(Piece[][] board, int RowOrColindex, int offset, Check check)
{
       if ( check == Check.Row ) return board[RowOrColindex][offset];
       else if ( check == Check.column ) return board[offset][RowOrColindex];
       else if ( check == Check.Diagonal ) return board[offset][offset];
       else if ( check == Check.ReverseDiagonal ) return board[offset][board.length -1 - offset];

       return Piece.Empty;
}


Piece getWinner(Piece[][] board, int RowOrColindex, Check check)
{

     // STEP1 : get the first cell's piece
     Piece color = getIthColor(board, RowOrColindex, 0, check);
     if ( color == Piece.Empty ) return Piece.Empty;
     // STEP2 : get the rest cell's piece and compare
offset =1; offset < board.length; offset++)
     {
           if ( color != getIthColor(board, RowOrColindex, offset, check) )
           {
               return Piece.Empty;
           }
     }
     return color;
}


Piece hasWon(Piece[][] board)
{




     int N = board.length;
     Piece winner = Piece.Empty;





     // Case1: check rows and columns
     for (int i = 0; i < N ; i++)
     {
          



            winner = getWinner(board, i , Check.Row);
            if (  winner != Piece.Empty  )
               return winner;





            winner = getWinner(board, i, Check.Column);
            if (  winner != Piece.Empty )
               return winner;




     }






     // Case2: check diagonal
     winner = getWinner(board, -1, Check.Diagonal);
     if (  winner != Piece.Empty  )
        return winner;







     // Case3: check reverse diagonal
     winner = getWinner(board, -1, Check.ReverseDiagonal);
     if (  winner != Piece.Empty )
         return winner;


      


     return Piece.Empty;




}

3. Similar Ones
1. O(N) with the addition of row and column count arrays( and two sums for the diagonals)
2. A common follow up (or tweak) to this question is to write this code for an NxN board

[19.1] SWap a number without temporary variables

1. Example

ab
=> ba

2. Implementation

public static void swap(int a , int b)
{
       // 5,9 ===> 9,5
       a = b-a; // SECOND - ONE = DIFF = 9-5=4
       b = b-a; // SECOND - DIFF = ONE = 9-4 =5
       a = a+b; // DIFF + ONE = SECOND = 4 + 5 = 9
}

public static void swap (int a , int b)
{
       // 5, 9 => 9,5
       a = a^b; // 0101 ^ 1001 = 1100
       b = a^b; // 1100 ^ 1001 = 0101 = original a
       a = a^b; // 1100 ^ 0101 = 1001 = original b
}

3. Similar Ones