Cracking the interview 19.11

gistfile1.txt

import java.util.Hashtable;
import java.util.Arrays;

public class Question1911
{
  //hashtable implementation, needs to figure out the repeated printout pair and collision
  public static void findpair(int sum, int[] a) {
    Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
    for(int i = 0; i < a.length; i++) {
      if( !table.containsKey(a[i])) {
        table.put(a[i], i);
      } else {
        System.out.println("Collision!");
      }
    }
    for( int i =0; i < a.length; i++){
      int complement = sum - a[i];
      if( table.containsKey(complement) && table.containsKey(a[i])) {
        
        System.out.println("Pairs is : " + a[table.get(complement)] + " and " + a[i]);
      }
    }
    
  }
  
  //Sort solution
  public static void findpair2(int sum, int[] a) {
    Arrays.sort(a);
    int first = 0;
    int last = a.length - 1;
    while (first < last) {
      int tmpsum = a[first] + a[last];
      if ( tmpsum < sum ) {
        ++first;
      } else if ( tmpsum > sum) {
        --last;
      } else {
        System.out.println("Pairs is : " + a[first++] + " and " + a[last--]);
      }
    }
  }
  
  public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
    int sum = 10;
    //findpair(sum, a);
    findpair2(sum, a);
    
  }
}