[9.7] largest possible number of people u=in in circus tower

1. Example

NOTE: NOT must be start from the beginning, probably the longest start from the middle

(1,4)(2,3)(3,4)(5,6)
start from: (1,4)(5,6), 
(2,3) unfit
start from: (2,3)(3,4)(5,6) , the longest

      C     50 5' 5
A        B
80 6'   70  5' 9


2. Implementation
Input (ht, wt)=(inch, lb): (65,100)  (70,150)  (56,90)  (75,190)  (60,95)  (68,110)
Output: the longest tower: (56,90)   ( 60,95) (65,100)  (68,110)   (70,150)  (75,190)
1. sorted ht,wt
sort ht, if ht same, sort wt
check wt is larger than previous ht

public class Question 
{




    ArrayList items;
    ArrayList lastFoundSeq;
    ArrayList maxSeq;




      
    // Returns longer sequence
    ArrayList seqWithMaxLength(ArrayList seq1, ArrayList seq2)
    {

         return seq1.size() > seq2.size() ? seq1:seq2;

    }





    // Fills next seq w decreased wt & returns index of 1st unfit item
    int fillNextSeq(int startFrom, ArrayList seq)
    {


          int fristUnfitItem = strartFrom;
          int count = 0;


          if ( startFrom < item.size() ) 
          {


              for ( int i = 0; i < items.size(); i++ ) 
              {
                      HtWt item = items.get(i);
                      if ( i== 0  || items.get(i-1).isBefore(item) )
                           seq.add(item);
                      else  
                      {
                          if (count == 0)
                          {
                              firstUnfitItem = i;
                              count++;
                          }
                      }
              }


          }
         

      
          return firstUnfitItem;


          
    }
   




    // Find the maximum length of sequence
    void findMaxSeq()
    {




           Collections.sort(items);




           int currentUnfit = 0;
           while (currentUnfit   < items.size())
           {



                // NOTE: get New unfit index and New seq
                ArrayList nextSeq = new ArrayList();
                int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
                



                maxSeq = seqWithMaxLEngth(maxSeq, nextSeq);
           



                //NOTE: new unfit index
                if (nextUnfit == currentUnfit)
                     break;
                else
                     currentUnfit = nextUnfit;     



           }


    }


}

3. Similar Ones

[9.6] Find an element in sorted matrix

1. Example


// RIGHT MOST => LARGER next row.

// => LESS left col
123
456
789

find 5, ROW should be 1
m = 0+2 /2 = 1, 4 < 5, l = 1+1 =2
m= 2+2  /2 =2, 7 > 5, r = 2-1 =1, l > r , STOP
1,4,7
4=> 4,5,6


find 3 , ROW should be 0
m=0+2 /2 =1 , 4 > 3 , r = m-1 = 0
m = 0+ 0  /2 = 0, 1 < 3 , l = 0+1 =1 , l >r, STOP

find 9, ROW should be 2
m=0+2 /2 = 1 , 4 < 9, l = m+1 = 2
m = 2+2 /2  =2 , 7 < 9, l = 2+1 =3, l > r=2 , STOP



2. Implementation

public boolean FindElem(int[][] matrix, int target, int M, int N)
{



    
      // validate the input
      if (  target == null  )
         return true;
      if ( matrix == null || matrix.length == 0 || matrix[0].length == 0)
         return false;





      int l = 0;
      int r = M;
      //while ( l < r)
      while( l <= r)
      {
           int m = (l+r)/2;
           if (  martix[m][0] == target)
              return true;
           if ( matrix[m][0] < target )
                 l = m+1;
           else
                 r = m-1;
      }
      



      // NOTE: 
      //int row = l;
      if ( r < 0)
             return false;
      int row = r;




      int l = 0;
      int r = N;
      while ( l <= r)
      {
            int m = (l+r)/2;
           if ( matrix[row][m] == target)
                return true;
           if ( matrix[row][m] < target)
                l = m+1;
            else
                r = m-1;
      }


   
     
       return false;



} 

// RIGHT MOST => LARGER next row.
//            => LESS left col
public boolean FindElem(int[][] matrix, int target, int M, int N)
{


     int row = 0; 
     int col = N-1;

  


     while ( row < M && col >=0 )
     {
          if (  matrix[row][col] == target  )
               return true; 
          else if (   martix[row][col] > target ) //1,2,3=> 3 > 2
               col--;
          else // 1,4,7 
          {
               row++
          }
     }  



     return false;



}

3. Similar Ones

[9.5] Find string in sorted array of strings

1. Example

SORTED array of strings => Binary Search

find "ball" in ["at","","","","ball","","","car","","","dad","",""] will return 4
find "ballcar" in ["at","","","","","ball","car","","","dad","",""] will return -1


2. Implementation
Use ordinary binary search
1. hit an empty string, advance to the next non-empty string
2. If there is no next non-empty string, search the left half

if (str=="") 

{ 

     for ( int i=0; i < strings.length; i++ ) 

     {

           if (strings[i] == "") return i; 

     } 

     return -1; 

}

public int search(String[] strings, String str)
{




    // validate the input
    if ( strings == null || str == null )
       return -1;




    if (str=="")
    {
          for ( int i=0; i < strings.length; i++ ) 
          {
              if (strings[i] == "") return i;
          }


          return -1;



    }




    return search(strings, str, 0, strings.length - 1);



}

public int search(String[] strings, String target, int l, int r)
{
   
    
    while( l <= r  )
    {
 

         

          // Ensure there is something at the end
          while ( l  <= r && strings[r] == "" )
                --r;
          // The block was empty, so fail
          if ( r < l)
                return -1;




          int m = (l+r)/2;
          



          while (strings[m] == "")
                ++m;



          // NOTE: binary Search
          int r = strings[m].compareTo(target);
          if ( r == 0 )
               return m;
          if ( r < 0)// at < ball(target)
               l = m+1;
          else   // ball(target) < car
               r = m-1;




    }



    return -1;



}

3.Similar Ones

[9.4] Sort the 2GB file

1. Example

0. 2GB file -  don't want you to bring all the data into memory
1. One string per line
2. Sorting algorithm

2. Implementation

When an interviewer gives a size of limit of 2GB, it should tell you something
- in this case, it suggests that they don't want you to bring all the data into memory.

So what do you do? We only bring part of the data into memory..

Algorithm:

How much memory so we have available? Let's assume we have X MB of memory available.



1. Divide the file into K chunks, where K*X MB = 2 GB. Bring each chunk into memory and sort the lines as usual using any O(n log n) algorithm. Save the lines back to the file.
2. Now bring the next chunk into memory and sort.
3. Once we're done, merge them one by one.

The above algorithm is also known as external sort.
Step3 is knows as N-way merge

The rationale behind using external sort is the size of data.
Since the data is too huge and we can't bring it all into memory, we need to go for a disk based sorting algorithm.

3. Similar Ones

[9.3] Find an element ain rotated sorted array

1. Example

Make sure only SORTED side can use Binary Search

For example, if the array is [2,2,2,2,2,2,2,2,3,2,2,2,2,2,2,2,2,2,2], there is no way to find element 3 until you do a linear search.

s= {15,16,19,20,1,3,4,5,7,10,14}
Find 5 in array s
Output : 8 (the index of 5 in the array)


2. Implementation

public static int search(int[] a, int l, int r, int target)
{





     if ( a == null || a.length == 0)
        return -1;






     while ( l <= r )
     {






         int m = (l+r) /2 ;
         if (  a[m] == x )
              return m;






         if ( a[l] < a[m]  )
         {





               //if (a[m]  >  x)
               // NOTE: consider another side with "="
               if ( a >= a[l] && a < a[m] )
                     r = m-1;






               else 
                     l = m+1;
               
         }
         else if ( a[l] > a[m] )
         {






               // NOTE: consider another side with "="
               if ( x > a[m] && x <= a[r] )
                   l= m+1;





               else
                   r = m-1;
               //if ( a[m] > x )
               //     r = m-1;
               //else 
               //     l = m+1;     
               
         }  
         else 
         {
              l = l +1;
         }





     }



     return -1;



}

3. Similar Ones

[9.2] Sort an array of strings by anagrams

1. Example

s= {"water","cold","bottle","retaw", "dloc"}

s= {"water, "retaw", "cold","dloc","bottle"}


2. Implementation

// Next to each other -1, 1, 0
// 
public class AnagramComparator implements Comparator
{



     public String sortChars(String s)
     {
           char[] charArr = s.toCharArray();
           Arrays.sort(charArr);
           return new String(charArr);
     }




     public int compare(String s1, String s2)
     {
           // compareTo: ASCII natural order
           return sortChars(s1).compareTo(sortChars(s2));
     }



     
}



Arrays.sort(   array,  new AnagramComparator()   );

3. Similar ones

[9.1] Merge tow sorted array

1. Example

a = {1,2,3,10}
b= {4,5,6,7}

c= merge a and b = {1,2,3,4,5,6,7,10}




2. Implementation

// Assume a has a large enough buffer 
// 
public void merge( int[] a , int[] b, int m , int n)
{
    


     //validate the input
     // if (  a!=null && b==null   )
     //     return;
     // if (  a ) 
     // a == null
     // b == null
     



     int k = m + n -1;
     int i = m - 1;
     int j = n - 1;



     
     while (  i >= 0 && j >= 0 )
     {
           if ( a[i] >  b[j]  )
           {
               a[k--] = a[i--];
           }
           else 
           {
               a[k--] = b[j--];
           }
     }





     while (  j >= 0 )
     {
           a[k--] = b[j--];
     }


     

}

3. Similar ones