adapted to new storage location
[feisty_meow.git] / 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 }