Cracking the Coding Interview Moderate

[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

Monday, October 5, 2015