[20.6] find the largest 1 million numbers in 1 billion numbers

1. Example

[1,2,3,4,5,6,7,8,9]

find 3 largest
[7,8,9]


2. Implementation

Approach1: Sorting, Time:O( n log n)

Sort the elements and then take the first million from that.  

Approach2: Max Heap, TimeO( n log m), n numbers and each heapify O( log m)

1. Create a Min Heap with the first million numbers
2. For each remaining number, insert it in the Min Heap and then delete the minimum value from the heap
3. The heap now contains the largest million numbers
4. This algorithm is O( n log m ), where m is the number of vlaues we are looking for

Approach3: Selection Rank Algorithm, Time:O(n)
Find the ith smallest(or largest) element in an array in expected linear time.

1. Pick a random element in the array and use it as a pivot. Move all elements smaller than that element to one side of the array , and all elments larger than to the other side.
2. If there are exactly i elements on the right, then you find the smallest  element on this side.
3. Otherwise, if the right side is bigger than i, repeat teh algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i - right.size()
Given this algorithm,
you can either 
1. Tweak it to use the existing partitions to find the largest i elements (where i = one million)
2 .Or, once you find the ith largest element, run throguh the array again to return all elements greater than or equal to it

3. Similar Ones http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html https://github.com/monkeylyf/interviewjam/blob/master/searching/cap_Find_Largest_k_numbers_in_n_Numbers.java

[20.5] Find the sortest distance between two words in the file

1. Example

"I am so awesome,so awesome, so awesome, so cool , so .."
so awesome = > 0 ! shortest
so "..." awesome => 4

Searching operation in O(1) ? Space Complexity?


2. Implementation
Q1: find the two word,  outer inward?
A1: frist last first = word1and last = word2
Q1: does word order matter word1,-word2 or word2- word1 counts?
A1: consider order doesn't matter here

public int shortest(String[] words, String word1, String word2)
{



        int min = Integer.MAX_VALUE;
        int word1_pos = -min;     // since word1_pos - word2_pos if word1_pos has value
        int word2_pos = -min;


        // validate the input
        if ( words == null || word1 == null || word2 == null )
          return min;


 


        for (int i = 0; i < words.length; i++)
        {
               String current_word = words[i];
               if (current_word.equals(word1))
               {
                      word1_pos = i;
                      int distance = word1_pos - word2_pos;
                      if (min > distance)
                          min = distance;
               }
               else if ( current_word.equals(word2))
               {
                      word2_pos = i;
                      int distance = word2_pos - word1_pos;
                      if (min > distance)
                          min = distance;
               }

      
        }


      
       return min;

 

}

To solve this problem in less time (But more space), we can create a hash table with each word and the locations where it occurs.
We then just need to find the minimum (arithmetic) difference in the locations (e.g., abs(   word0.loc[1] - word1.loc[5]  ))


To find the minimum arithmetic difference, we take each location for word1,e.g., {0,3} and do a modified binary search for it in word2's location list, return the closest number. our search for 3, for example, in {2,7,9} would return 1. The minimum of all these binary searches is the shortest distance.

http://weihungleetcodearray.blogspot.com/2015/08/searchbinary-search-search-insert.html

3 .Similar Ones

[20.4] Count the number of 2s between 0 and n

1. Example

LeetCode: Number of Digit One

      1,2,3,4,5,6,7,8,9,10,
   11,12,........
20,..,29,
30,...32,39,..
      ..42,.
      ..52,..
       .92,.
    ..102, ,
120,129..
      .192,...
200,...299...

>2   => first digit, with 2X, at least power 52 = 20~29[power =10], 513=200~299[power = 100]  
==2 => first, digit, with 2x, at lest remainder+1 25=[20-25][remainder +1=6], 279=[200-279][reminder +1=80]

all other digit power-1  + reminder
Recursive MSB->LSB, maximum power you got200~299, first digit and remainder, first digit >2 power or ==2 remainder +1 AND first*f(power-1)20~29,22-92 + f(reminder)
513 = 100,5,13
32 = 10,3,2
f(513) =  100 + 5*f(99) + f(13)

           =  100 + 5* 20    + 2 
           = 202

Iterative    LSB->MSB, LSB as first digit power or remainder, remainder for next digit,
digit*pos*power/10[like 5*f(99)] digit*previous count
f(513) = f(3)  3*0*1/10     + [3>2, count+=1]       = 0 + 1 

              f(1)  1*1*10/10   + [1<2, count+=0]       = 1 + 0 

              f(5)  5*2*100/10 + [5>2, count+=100]   = 100 +100

          = 202

// NOTE: accumulate from previous
count+= digit*pos*power/10;

remainder = digit * power + remainder;






f(2) = 1st digit       1  [2]

                al other digit        0
2 = 2* 1 + 0
f(52)     =  1st digit                10  [20,..29]
                al other digit        f(2)
52 = 5* 10 + 2
f(513) =  1st digit           100  [200-299]
                all other digit 5*f(99) + f(13)
513 = 5 *100 + 13
f(279) =  1st digit           80  [200-279]
                all other digit 2*f(99) + f(79)
279 = 2*100 + 79
int nTwoFirst = 0;

if (first > 2 )

 nTwoFrist += power; 

else if (first == 2) 

nTwoFirst += reminder + 1; 

// Count 2s from all other digits

 int nTwoOther = first*count2s(power -1) + count2s(remainder);

f(279) = 2*f(99) + f(79)  + 79+1[200-279] 
2 in the first digit ,in the second digit, in the third digit[the last digit]
There are X2     between 0 and 99   [2,12,32,43,52,62,72,82,92] = > 10 Twos
                2X     between 0 and 99   [ 20,   21,...  29]                    = > 10 Twos
There are 2X     between 0 and 199 [  20,   21,...  29
                                                       120, 121, ..129] => 20 Twos
There are 2XX  between 0 and 299 [ 200,201,.....299 ] => 100 Twos
                                                         [    20,21,,,,29,
                                                             120,  .....129,
                                                             220, ... ...229]  => 30 Twos
  0     1      2 ....  9
  10   11   12     19
  20
  30....
...
110 111          119
The last digit repeat every 10 numbers, 0,10,20,30..
The last two digit repeated every 10^2 numbers, 10, 110, 210,..
The last three digit repeated every 10^3 numbers, 110, 1110,..

  0     1      2 ....  9      => one 2
  10   11   12     19    => one 2
  20                           => one 2 from 2'2'+ ten 2 from 2X
  30....
...
110 111          119  => one 2

210.................219  => one 2 from 12 + ten 2 from 2XX

f(513) = the last digit 2 [2,12,22,32,...512] + the last 2 digit 2X[2x, 12x,22x, ..42x] + the last three digit 2xx[2xx]
          = (512-2)/10+1   +    (420-20)/100+1 + 1
          = 52 + 5 + 1

2. Implementation

public static int count2s(int n)
{




      //validate the input
      // Base Case
      if ( n == 0 )
            return 0;
        
 


       int power =1; 
       while ( 10 * power < n )  power*=10;  // power =100
       int first = n / power ;               // first = 5
       int remainder = n % power;            // remainder = 13




       // Count 2s from the first digit
       int nTwoFirst = 0;
       if (first > 2 ) nTwoFrist += power;
       else if (first == 2) nTwoFirst += reminder + 1;

       
       


       // Count 2s from all other digits
       int nTwoOther = first*count2s(power -1) + count2s(remainder);





       return nTwoFirst + nTwoOther;

 


}

public static int count2s(int n)
{




     
       int count =0;
       int digit = 0;
       int j = num; 
  

       int power     = 1;
       int remainder = 0;
       int pos = 0;

     

       // maintaining this value instead of calling pow() is an 6x 
       // perfgain
       // 513 = 51*10 + 3
       //  51 = 5*10  + 1
       //   5 = 0*10  + 5
       while (  j > 0 )
       {




            digit = j % 10;
            


            // NOTE: accumulate from previous
            count+= digit*pos*power/10;




            // NOTE: Seen it as First digit
            if (digit ==2 )
            {
                 // NOTE: First digit count =  reminder +1 
                 // 250 = 2*100 +50 = [200,..250] => 50+1
                 // 25 = 2*10 + 5= [20,..25]      => 5+1
                 // 2  = 2*1 + 0 = [2]            => 0+1
                 count += remainder +1;                 
            }
            else if ( digit > 2)
            {
                 // NOTE: First digit count =  power 
                 // 500 = 5*100 = [200,..299]
                 // 50 = 5*10= [20,..29]
                 // 5  = 5*1 = [2]            
                 count += power; 
            }

  

            
            j  = j / 10;
            remainder = digit * power + remainder;
            power *= 10; 
            pos ++;


       }





       return countOf2s;





}

3. Similar Ones

[20.3] Generate a set of m integers from an array of size n, chosen equally likely

1. Example
Equal probability


Inclusive 

(int) ( Math.random() *(higher-lower+1) ) + lower


1/n 1/n 1/n


[1] [2] [3].....[n]pick m itnegers

DON'T PICK UP TWICE => swap => the index in the subset indicating
the elements before that index has been chosen and CANNOT be  chosen again

delete element from the array=> shrinking / shifting => O(n)
subset[0] <- array[k]
==> SWAP array[0] and array[k]
subset[1]<= array[k-3]
==> SWAP array[1] and array[k-3]
...
2. Implementation

/*Random number between lower and higher, inclusive*/
/*Inclusive so we higher - lower +1 , include both end */
public static int rand(int lower, int higher)
{




    return (int) (   Math.random() *(higher-lower+1)   )   + lower;




}

/*Pick M elements from the original array. Clone original array so htat we don't destroy the input*/
public static int[] pickMRandomly(   int[] original, int m)
{




    int[] subset = new int[m];
    int[] array = original.clone();





    for (int i = 0 ; i < m; i++)
    {
         int pickIndex = rand(i, array.length -1);
         subset[i] = array[pickIndex];
         array[pickIndex] = array[i]; // array[i] is dead
    }



    return subset;

   
}

3. Similar Ones

[20.2] Perfect shuffle a deck of cards

1. Example


Not Inclusive 

(int) ( Math.random() *(higher-lower) ) + lower

Equally likely=>rand(), 
Iterating and SWAP prevent the same card being selected 
52! permutations of the deck has to be equally likely
==> cannot pick the same card twice
[1] [2] [3] [4] [5]
[4]
[1] [2] [3] [X] [5]


Iter1: Swap [1] and [21]
[1][2][3].......[52]
[21][2][3]......[1].....[52]
Iter2: Swap [2] and [31]
[1][2][3].......[52]
[21][31][3]......[31].....[52]

Math.random()=>  [0.0, 1.0)
(int)  (  Math.random() * (card.length - i)  ) + i
i = 5 
[0,1) * (52-5) + 5 = [5, 52) including current index and len-2 index

2. Implementation

public static void shuffleArray(  int[] cards )
{
      int temp, pickIndex;
      for (int i = 0 ; i < cards.length; i++)
      {
          pickIndex = (int)  (  Math.random() * (card.length - i)  ) + i;
          temp = cards[pickIndex];
          cards[pickIndex] = cards[i];
          cards[i] = tmp;
      } 
} 

3. Similar Ones

[20.1] Add two number without + or any other arithmetic operators

1. Example

Add each digit, and carry the one as necessary
Sum ONLY:
759
674
___
323

9  = 1001
4  = 0100
----------
13 = 1101  = 9^4
====> XOR

 carry ONLY:
 7 5 9
 6 7 4
____
1110

9  = 1001
4  = 0100
----------
0 = 0000  = 9&4
====> AND


  2 = 0010
10 = 1010
-------------
12 = 1100
2^10 = 1000 =8
2&10= 0010 
0010 << 1 = 0100 =4

8^4 =  1000^0100 = 1100 = 12

2. Implementation

public int addTwoNumber_No_Arithm(int a, int b)
{
      if (b==0) return a; // no carry
      int sum = a^b;        // add without carrying
      int carry = (a&b)<<1; // carry, but no add
      return addTwoNumber_No_Arithm(sum, carry); 
}

3.Similar Ones