X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=kona%2Fsrc%2Forg%2Ffeistymeow%2Falgorithms%2FSumFinder.java;fp=kona%2Fsrc%2Forg%2Ffeistymeow%2Falgorithms%2FSumFinder.java;h=533880c017b56d71db12b2dedeacc3465291ee75;hb=1f6e7f7c3be3f2198df8211bf14b15856d9853a8;hp=0000000000000000000000000000000000000000;hpb=31731a0098657ef95424d46f8f973d50904ca8a0;p=feisty_meow.git

diff --git a/kona/src/org/feistymeow/algorithms/SumFinder.java b/kona/src/org/feistymeow/algorithms/SumFinder.java
new file mode 100644
index 00000000..533880c0
--- /dev/null
+++ b/kona/src/org/feistymeow/algorithms/SumFinder.java
@@ -0,0 +1,83 @@
+package org.feistymeow.algorithms;
+
+import java.util.HashSet;
+
+/**
+ * example algorithms from google interview videos. these focus on finding a number as a sum within a list of numbers.
+ */
+class SumFinder
+{
+	/*
+	 * spec notes:
+	 * 
+	 * the numbers are ints, both positive and negative.
+	 * 
+	 * don't worry about overflow for math ops involving the sum or list members.
+	 * 
+	 * the input list is not necessarily sorted.
+	 * 
+	 * 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
+	 * two numbers that added to the sum.
+	 * 
+	 * this solution assumes that the list fits in memory.
+	 */
+	boolean findSumInList(int sum, int list[])
+	{
+		HashSet<Integer> wanting = new HashSet<Integer>();
+		for (int curr : list) {
+			if (wanting.contains(curr)) {
+				// we found a match for the complement we had stored earlier, so return true.
+				return true;
+			}
+			wanting.add(sum - curr);
+		}
+		return false;
+	}
+
+	/*
+	 * implement more general case also that can use any number of numbers in the set to sum?
+	 *
+	 * 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
+	 * of all matches, where a match is a collection of ints that add to the sum.
+	 */
+	// returning from this other method...
+	// return = new ArrayList<Integer>(Arrays.asList(curr, sum - curr));
+
+	// test app for above methods...
+
+	public static void main(String argv[])
+	{
+		SumFinder finder = new SumFinder();
+
+		int list_1[] = { 7, 5, 8, 2, 9, 4, 1, 2 };
+		int sum_1 = 8;
+
+		if (!finder.findSumInList(sum_1, list_1)) {
+			System.out.println("FAILURE: ON TEST CASE 1");
+		} else {
+			System.out.println("OKAY: ON TEST CASE 1");
+		}
+
+		//////////////
+
+		int list_2[] = { 1, 9, 3, 2, 4, 4, 1 };
+		int sum_2 = 8;
+
+		if (!finder.findSumInList(sum_2, list_2)) {
+			System.out.println("FAILURE: ON TEST CASE 2");
+		} else {
+			System.out.println("OKAY: ON TEST CASE 2");
+		}
+
+		//////////////
+
+		int list_3[] = { 1, 9, 3, 2 };
+		int sum_3 = 8;
+
+		if (finder.findSumInList(sum_3, list_3)) {
+			System.out.println("FAILURE: ON TEST CASE 3");
+		} else {
+			System.out.println("OKAY: ON TEST CASE 3");
+		}
+	}
+}