[7.19-7.23] Generics

1. Implementation

Specifics
---------------------------------------------------------------------------

public interface IntegerOperation { 

    Integer performOperation(Integer value); 

}
public class AddOneOperation implements IntegerOperation { 

    @Override 

    public Integer performOperation(Integer value) { 

        return value+1; 

   } 

}

-------------------------------------------------------------------------

Generics

-------------------------------------------------------------------------

// work with a list of any type, and return a list of a different type

// E.g., turning a String parameter into an Integer

public interface GenericOperation<A, B> {

              B performOperation(A value);

}

public class StringLengthOperation implements GenericOperation<String, Integer>

{

         @Override

         public Integer performOperation (String value)

              return value.length();

}

------------------------------------------------------------------------

for (final Integer number: numbers){
res.add(op.performOperation(number));
}

// 7-19 Write a method that replicates a list of Itnegers, with 1 added to each element. 

public static List addOne(final List numbers)
{
       final List res = new ArrayList(numbers.size());
       for ( final Integer number: numbers)
       {
          res.add(number+1);
       }


       return res;

}

// To allow any Integer operation, you can define a new 
// interface, IntegerOperation, which has one
// method, taking an Integer, and returning an Integer

public interface IntegerOperation
{
      Integer performOperation(Integer value);
}

public class AddOneOperation implements IntegerOperation
{
      @Override 
      public Integer performOperation(Integer value)
      {
           return value+1;
      }
}



// 7-20  Performa any integer operation on a list

public static List updateList(final List numbers, final IntegerOperation op)
{
         final List res = new ArrayList<>(number.size());
         for (final Integer number: numbers)
         {
              res.add(op.performOperation(number));
         }

         
         return res;


}


// 7-21 Testing the updateList method

@ Test
public void positiveList()
{
      final List numbers = Arrays.asList(4,7,2,-2,8,-5,-7)
      final List expected = Arrays.asList(4,7,2,2,8,5,7);


      final List actual = Lists.updateList(nubmers, new IntegerOperation()
{
         @Override
         public Integer performOperation(Integer value)
               return Math.abs(value);
});


     assertEquals(expected, actual);
}

// 7-22 Mapping a list into a different type

public static  List mapList(final List values, final GenericOperation op )
{


       final List res = new ArrayList<>(values.size());
       for (final A a: values)
            res.add(op.performOperation(a));


       return res;


}


// 7-23 Testing the list mapping functionality

@Test
public void stringLengths()
{

      final List strings = Arrays.asList("acing", "the", "java", "interview" );
      final List expected = Arrays.asList(5,3,4,9);
      final List actual = List.mapList(strings, new StringLengthOepration()  );
      assertEquals(expected, actual);

}

[7.16-7.18] collapses a list of Iterators into a single Iterator

1. Implementation

// NOTE: This means that the currentIterator
// reference could potentially advance several iterators before
// finding one where the hasNext method
// returns true, but the recursion will take care of that.

public boolean hasNext() {

if(!currentIterator.hasNext()) {

if (!listIterator.hasNext()) {

return false;

}

currentIterator = listIterator.next();

hasNext();

}

return true;

}

final Iterator<Integer> a = Arrays.asList(1, 2, 3, 4, 5).iterator();

final Iterator<Integer> b = Arrays.asList(6).iterator();

final Iterator<Integer> c = new ArrayList<Integer>().iterator();

final Iterator<Integer> d = new ArrayList<Integer>().iterator();

final Iterator<Integer> e = Arrays.asList(7, 8, 9).iterator();

assertTrue(signleIterator.hasNext() );

 for (Integer i = 1; i < =9 ; i++) 

    assertEquals( i, singleIterator.next() ); 

assertFalse( singleIterator.hasNext() );

public interface Iterator
{
      boolean hasNext();
      E next();
      void remove();
}



//public static  Iterator singleIterator( final //List> iteratorList)
//{
//}



// Main function listIterator operates as a single iterator
// Implement Iterator interface 
public static class ListIterator implements Iterator
{



     // boolean hasNext();
     // E next();
     // void remove();



     // Field
     private final Iterator> listIterator;
     private Iterator currentIterator;






     // Constructor: make list iterator into Iterator>
     public ListIterator( List> iterators)
     {
          this.listIterator = iterators.iterator();
          this.currentIterator = listIterator.next();
     }






// NOTE: This means that the currentIterator
// reference could potentially advance several iterators before 
// finding one where the hasNext method
// returns true, but the recursion will take care of that.
     @Override
     public boolean hasNext()
     {
          // CurrentIterator has no next
          if ( !currentIterator.hasNext() )
          {  
               // set up next iterator as currentIterator
               if ( !listIterator.hasNext()  )
                     return false;
               currentIterator = listITerator.next();
               // NOTE: recurse to check if next still has no next
               hasNext();
          }


          return true;


     }
     //public  next()
     public T next()
     {
          hasNext();
          return currentIterator.next();
     }
     // public boolean remove()
     public void remove()
     {
          hasNext();
          currentIterator.remove();
     }






}

@Test
public void multipleIteratorsTest()
{




      final Iterator a = Arrays.asList(1,2,3,4,5).iterator();
      final Iterator b= Arrays.asList(6).iterator();
      final Iterator c = new ArrayList().iterator();
      final Iterator d = new ArrayList().iterator();
      final Iterator e = Arrays.asList(7,8,9).iterator();
      




      final Iterator singleIterator = Iterators.singleIterator( Arrays.asList(a,b,c,d,e));
      assertTrue(signleIterator.hasNext() );
      for (Integer i = 1; i < =9 ; i++)
           assertEquals( i, singleIterator.next()  );

      assertFalse(  singleIterator.hasNext() );



} 

[7.14,7.15] A palindrome hcecker

1. Implementation

You can reuse your reverse method, leading to a one-line method: The fewer lines of code you need

to write, the fewer places you can introduce bugs. Assuming the reverse method is fully tested,

writing unit tests for this method will be very, very simple

public static boolean isPalindrome(final String s)
{
   
     final String toCheck = s.toLowerCase();
     int left = 0; 
     int right = toCheck.length()-1;



     while (left < right)
     {




          // Not a Character
          while( left < toCheck.length() && !Character.isLetter(toCheck.charAt(i)))
          {
              left++;
          }
          // Not a Character
          while( right > 0 && !Character.isLetter(toCheck.charAt(right)))
          {
              right--;
          }
          // Sanity check since left and right could have been updated
          if ( left > toCheck.length() || right < 0  )
              return false;
           




          if ( toCheck.charAt(left)  != toCheck.charAt(right) )
              return false;




          
          left++;
          right--;




     }



     return true;


}


public static boolean strictPalindorme(final String s)
{
      return s.euqals( reverse(s)  );
}

[7.11-7.13] Reverse a linked List

1. Implementation

One ->Two-> Three-> ø

One         

Two-> Three-> ø

            Two   

            Three-> ø

            Three-> two

 Three-> two-> one

// How do you reverse a linked list in place?


@Test
public void reverseLinkeDLsitTest()
{
    final LinkedList three= new LinkedList<>("3", null);
    final LinkedList two = new LinkedList<>("2", three)
    final LinkedLsit one = new LinkedList<>("1", two);


    final LinkedList reversed = LinkeDLsit.reverse(one);


    assertEquals("3", reversed.getElement() );
    assertEquals("2", reversed.getNext().getElement());
    assertEquals("1", reversed.getNExt().getNExt().getElement());
)

    
}


// #1 Iterative 


public void reverseLinkedList( ListNode head)
{

        // validate the output
        if ( head == null )
            return;
 

        ListNode p = head;
        ListNode q ;
        ListNode end = null;


        while ( p != null )
        {
             // tmp
             q = p.next;
              
             p.next = end;
             end = p;


             // assign tmp 
             p = q;
        }
}


// # 2 Recursive

public static  LinkedList reverse (final LinkedList ori)
{
      // validate the input
      if ( ori == null )
         throw new NullPointerException("cannot reverse a null list");
      
      // only one element
      if ( ori.getNext() == null )
          return ori;

      
      // Separate First   2->3->null == 2->null  3->nyll
      final LinkedList next = original.next;
      original.next = null;

     
      // Separate the Rest  3->null return
      final LinkedList otherReversed = reverse(next); // first return is only one element left

      // Rest -> First 3->null==> 3->2->null
      next.next = original;



      return otherReversed;
      


}


public class LinkedList {

     // Field
     private T value
     private LinkedList next;


     // constructor
     public LinkedList( T value, LinkedList<
T> next)      
     {
        this.value = value; 
        this.next = next;
     }


      public T getValue()
     {
        return value;
     }

     public LinkedList getNext()
     {
          return next;
     }
} 

[7.10] Reverse a String

1. Implementation

This approach, while fine, does require a large amount of memory. It needs to hold the original

String and the StringBuilder in memory. This could be problematic if you were reversing some

data of several gigabytes in size

// #1

public static String reverse(final String s)
{
    final StirngBuilder sb = new StringBuilder (s.length());
    for (int i = s.length() -1 ; i >=0; i--)
        sb.append(s.charAt(i));

 
     return sb.toStirng();

}


// #2

// Time:O(n), Space:O(n) char[]

public static reverse (final String s)
{
     char[] charArray = s.toCharArray();
     reverse( charArray, 0 , charArray.length-1); 
     return new String( charArray );
}
// time :O(n)
private reverse( char[] chararr, int l, int r)
{ 
   while ( l < r)
   {
         char tmp = chararr[l];
         chararr[l] = chararr[r];
         chararr[r] = tmp;
         l++; 
         r--;
   }   
}

// #3
public static String inPlaceReverse(final string s)
{
     final StringBuidler sb= new StringBuidler(s); 
     for (int i =0; i < sb.length()/2; i++)
     {
           final char tmp = sb.charAt(i);
           final int otherEnd = sb.length()-i-1;
           sb.setchatAt(i, sb.charAt(otherEnd));
           sb.setCharAt(otherEnd, tmp);
     }

     
     return sb.toString();

    
}

[7.9] anagram finder

1. Implementation

// Given a list of words, produce an algorithm that will return 
// a list of all anagrams
// for a specific word.


public class Anagram
{

 

   final Map> lookup = new HashMap<>();
    

   // Constructor - create the dictionary map
   public Anagrams (final List words)
   {
          for ( final String word: words)
          {
               final String signature = alphabetize(word);
               if (   loopup.containsKey(signature) )
                  lookup.get( signature ).add( word );
               else
               {
                  final List item = new ArrayList<>();
                  item.add(word);
                  lookup.put(signature, item);
               }
          } 
   }



   private String alphabetize(final String word)
   {
          final byte[] bytes = word.getBytes();
          Arrays.sort(bytes);
          return new String(bytes);
   }


   
   public List getAnagrams(final String word)
   {


          if (word == null)
                reutrn new ArryaList<>();   
          

          final String signature = alphbetize(word);         
          final List anagrams  = lookup.get(signature);
          return anagrams == null ? new ArrayList(); anagrams;

   }
 

}

[7.8] Factorial

1. Implementation

Be aware that with factorials the calculated value grows large extremely quickly, which is why this

method returns a long. You could even make a case for returning a BigInteger instance here.

BigInteger objects have no upper bound; they allow for numerical integer values of any size.

// An iterative implementation of a factorial
public static long factorial (int n)
{
      if (n < 1)
         throw new IllegalArgumentExcpetion("n must be greater than zero");


      long res =1;
      for (int i =1; i < =n ; i++)
         res*=i;
    

      return res;




}

[7.3-7.7] fibonacci sequence

1. Implementation
O(n^n)no cache VS O(n) memoization

Quite an improvement: from 19 seconds to 0.000311 seconds.

When the result of a method call is cached to save recalculating the result again later, this is called

memoization.

 Using return with if Statemen ts

Whenever you have a return statement inside an if statement, you do not need

to provide an else clause. If an if statement condition is false, the code execution

continues after the block. If the statement is true, the method execution will finish

with the return statement.

This has the advantage that your code does not need an extra level of indentation

due to the redundant else block:

if (condition) {

// code for condition == true

return valueIfTrue;

}

// more code for condition == false

return valueIfFalse;

// Write a method that returns a Fibonacci sequence from 1 to n.
// n the number of sequence integer

// Iterative - a,b,c

public static List fibonacci (int n)
{
     if (n < 0)
         throw new IllegalArgumentException("n must not be less htan zero");
     if ( n ==0 )
          return new ArrayList<>();
     if ( n ==1)
          return Arrays.asList(0);// 1 number 
     if ( n ==2)
          return Arrays.asList(0,1);// 2 numbers



     final List seq = new ArrayList(n);// n numbers
     seq.add(0);
     n = n-1;
     seq.add(1);
     n = n-1;
 
      
     while ( n > 0 )
     {
          int a = seq.get( seq.size()-1 );
          int b = seq.get( seq.size()-2 );
          seq.add(a+b);
          n = n-1;
     }


     return seq;
     
}

@Test
public void finbonacciseqTest()
{
     fibonacci(-1);
     assertEquals(0, fibonacci(0).size());
     assertEquals(Arrays.asList(0) , fibonacci(1);
     assertEquals(Arrays.asList(0,1), fibonacci(2);
     assertEquals(Arrays.asList(0,1,1), fibonacci(3);
     assertEquals(Arrays.asList(0,1,1,2), fibonacci(4);
     assertEquals(Arrays.asList(0,1,1,2,3), fibonacci(5);
     assertEquals(Arrays.asList(0,1,1,2,3,5), fibonacci(6);
     assertEquals(Arrays.asList(0,1,1,2,3,5,8), fibonacci(7);
     assertEquals(Arrays.asList(0,1,1,2,3,5,8,13), fibonacci(8);
}

// Write a method that returns the nth value of the Fibonacci sequence

// 1. previous method return seq.get(seq.size()-1)



public static int fibN(int n)
{
    if (  n < 0 )
          throw new IllegalArgumentException("n must be not less than zero");
    if ( n ==1 ) return 1;
    if ( n ==0 ) return 0;


    return fibN(n-1) + fibN(n-2);


}

// Caching previously computed Fibonacci numbers
public class Solution {


private Map fibCache = new Map<>();


public int cacheFibN(int n)
{
      if (n < 0 )
           throw IllegalArgumentException("n must be less than zero");
     fibcache.put(0,0);
     fibcache.put(1,1);
     return recursiveCachedFibN(n);
}


private int recursiveCachedFibN(int n)
{
     if (fibCache.constiansKey(n))
        return fibCache.get(n);

     

     int value = recursiveCachedFibN(n-1)+ recursiveCachedFibN(n-2);
     fiCache.put(n, value);
     


     return value;
    

}


}


@Test
public void largeFib()
{
     final long nonCachedStart = System.nanoTime();
     assertEquals(1134903170, fib(45));
     final long nonCachedFinish = System.nanoTime();

     assertEquals(1134903170, cachedFibN(45));
     final long cachedFinish = System.nanoTime();


     System.out.printf("", nonChacedFinish- nonCachedStart );

}

[7.1,7.2] fizzbuzz

1. Implementation

private static String toWord(final int divisor, final int value, final String word)
{
      return value%divisor == 0? word :"";
}
public static List fizzBuzz(final int n)
{

      final List res = new ArrayList<>(n);

      for (int i =1; i <= n; i++)
      {
          final String word = toWord(3,i,"Fizz") + toWord(5,i,"Buzz");
          if (StringUtils.isEmpty(word))
                res.add(Integer.toString(i));//String.valueOf(i)
          else
                res.add(word);
      }


      return res;


}

public static List fizzBuzz(final int n)
{

     final List res = new ArrayList(n);

     // validate the input
     if ( n < = 0 )
         return res;

     for (int i =1 ; i < = n ; i++)
     {
         if (i%15==0)
              res.add("FizzBuzz");
         else if ( i%3 == 0)
              res.add("Fizz");
         else if ( i%5 == 0)
              res.add("Buzz");
         else 
              res.add(Integer.toString(i));
     }

     
     return res;

}