kona/src/org/feistymeow/algorithms/SumFinder.java

   1 package org.feistymeow.algorithms;
   2
   3 import java.util.HashSet;
   4
   5 /**
   6  * example algorithms from google interview videos. these focus on finding a number as a sum within a list of numbers.
   7  */
   8 class SumFinder
   9 {
  10         /*
  11          * spec notes:
  12          *
  13          * the numbers are ints, both positive and negative.
  14          *
  15          * don't worry about overflow for math ops involving the sum or list members.
  16          *
  17          * the input list is not necessarily sorted.
  18          *
  19          * the result is just a boolean of whether the requested sum was found or not. it would be easy enough to return a pair though, with the
  20          * two numbers that added to the sum.
  21          *
  22          * this solution assumes that the list fits in memory.
  23          */
  24         boolean findSumInList(int sum, int list[])
  25         {
  26                 HashSet<Integer> wanting = new HashSet<Integer>();
  27                 for (int curr : list) {
  28                         if (wanting.contains(curr)) {
  29                                 // we found a match for the complement we had stored earlier, so return true.
  30                                 return true;
  31                         }
  32                         wanting.add(sum - curr);
  33                 }
  34                 return false;
  35         }
  36
  37         /*
  38          * implement more general case also that can use any number of numbers in the set to sum?
  39          *
  40          * e.g. if the number itself equals the sum, fine and dandy. or if three numbers sum to it, that's also a match. this should return a set
  41          * of all matches, where a match is a collection of ints that add to the sum.
  42          */
  43         // returning from this other method...
  44         // return = new ArrayList<Integer>(Arrays.asList(curr, sum - curr));
  45
  46         // test app for above methods...
  47
  48         public static void main(String argv[])
  49         {
  50                 SumFinder finder = new SumFinder();
  51
  52                 int list_1[] = { 7, 5, 8, 2, 9, 4, 1, 2 };
  53                 int sum_1 = 8;
  54
  55                 if (!finder.findSumInList(sum_1, list_1)) {
  56                         System.out.println("FAILURE: ON TEST CASE 1");
  57                 } else {
  58                         System.out.println("OKAY: ON TEST CASE 1");
  59                 }
  60
  61                 //////////////
  62
  63                 int list_2[] = { 1, 9, 3, 2, 4, 4, 1 };
  64                 int sum_2 = 8;
  65
  66                 if (!finder.findSumInList(sum_2, list_2)) {
  67                         System.out.println("FAILURE: ON TEST CASE 2");
  68                 } else {
  69                         System.out.println("OKAY: ON TEST CASE 2");
  70                 }
  71
  72                 //////////////
  73
  74                 int list_3[] = { 1, 9, 3, 2 };
  75                 int sum_3 = 8;
  76
  77                 if (finder.findSumInList(sum_3, list_3)) {
  78                         System.out.println("FAILURE: ON TEST CASE 3");
  79                 } else {
  80                         System.out.println("OKAY: ON TEST CASE 3");
  81                 }
  82         }
  83 }