From 1f6e7f7c3be3f2198df8211bf14b15856d9853a8 Mon Sep 17 00:00:00 2001 From: Chris Koeritz Date: Mon, 2 Jan 2017 16:28:38 -0500 Subject: [PATCH] added another code example --- graphiq/.settings/language.settings.xml | 2 +- ...l => feisty_meow-cpp_style-2013_03_07.xml} | 0 ... => feisty_meow-java_style-2017-01-02.xml} | 518 +++++++++--------- .../org/feistymeow/algorithms/SumFinder.java | 83 +++ .../feistymeow/textual/SimpleDictionary.java | 73 +-- nucleus/.settings/language.settings.xml | 2 +- 6 files changed, 386 insertions(+), 292 deletions(-) rename infobase/configuration/eclipse/{cpp-fredstyle_2013_03_07.xml => feisty_meow-cpp_style-2013_03_07.xml} (100%) rename infobase/configuration/eclipse/{java_style-fredstyle_2013_04_02.xml => feisty_meow-java_style-2017-01-02.xml} (97%) create mode 100644 kona/src/org/feistymeow/algorithms/SumFinder.java diff --git a/graphiq/.settings/language.settings.xml b/graphiq/.settings/language.settings.xml index c06ebfe7..55a7071d 100644 --- a/graphiq/.settings/language.settings.xml +++ b/graphiq/.settings/language.settings.xml @@ -5,7 +5,7 @@ - + diff --git a/infobase/configuration/eclipse/cpp-fredstyle_2013_03_07.xml b/infobase/configuration/eclipse/feisty_meow-cpp_style-2013_03_07.xml similarity index 100% rename from infobase/configuration/eclipse/cpp-fredstyle_2013_03_07.xml rename to infobase/configuration/eclipse/feisty_meow-cpp_style-2013_03_07.xml diff --git a/infobase/configuration/eclipse/java_style-fredstyle_2013_04_02.xml b/infobase/configuration/eclipse/feisty_meow-java_style-2017-01-02.xml similarity index 97% rename from infobase/configuration/eclipse/java_style-fredstyle_2013_04_02.xml rename to infobase/configuration/eclipse/feisty_meow-java_style-2017-01-02.xml index 71b50e8e..6afa0a7e 100644 --- a/infobase/configuration/eclipse/java_style-fredstyle_2013_04_02.xml +++ b/infobase/configuration/eclipse/feisty_meow-java_style-2017-01-02.xml @@ -1,291 +1,295 @@ - - - - - - - - - - - - - - - - - - - - - + + + + + + + - - - - - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - + + + + + + + + + + + + - - - - - - - - - - - - - - - - + + + + + - - - + + + + + + - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - - - - - - - - - - - + - + + + + + + + + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - + + + - - - - - - - - - - - - - - - - - - - - - - - - - + + + + + + + + + + + - - - - - - - - - - - - - - - - - - - - - - + - - - + + + + + + + - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + - - - - - - - - + + + + + + + + + + - - - + + + + + + + + + + - - - - - - + + + + + + + + - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + + + - - - - - - + + + + + + + + + + + + + + + + + + + + + + + + - - - - + + + + + + - - - - - - - + + + + + + + + - - - - - + - - - - - - + + + + + + + + + + + + + + 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 wanting = new HashSet(); + 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(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"); + } + } +} diff --git a/kona/src/org/feistymeow/textual/SimpleDictionary.java b/kona/src/org/feistymeow/textual/SimpleDictionary.java index 6d71f9b8..9008ac97 100644 --- a/kona/src/org/feistymeow/textual/SimpleDictionary.java +++ b/kona/src/org/feistymeow/textual/SimpleDictionary.java @@ -4,39 +4,46 @@ import java.util.HashSet; import java.util.Set; public class SimpleDictionary extends HashSet -//or alternatively, BinaryTree -//=> what is BST implem for java! is it balanced? +// or alternatively, BinaryTree +// => what is BST implem for java! is it balanced? { - public SimpleDictionary (Set words) { - addAll(words); - computeLongestWord(); - } - - public SimpleDictionary (String words[]) { - for (String word : words) { - add(word); + + private static final long serialVersionUID = 1L; + + public SimpleDictionary(Set words) + { + addAll(words); + computeLongestWord(); } - computeLongestWord(); - } - - public int computeLongestWord() { - previouslyComputedLongestWord = 1; - - //hmmm: iterate on set to find longest. - -//kludge implem placeholder. -previouslyComputedLongestWord = 100; - return previouslyComputedLongestWord; - } - - public boolean lookup(String toFind) { - return contains(toFind); - } - - public int longestWord() { - return previouslyComputedLongestWord; - } - - int previouslyComputedLongestWord; -} + public SimpleDictionary(String words[]) + { + for (String word : words) { + add(word); + } + computeLongestWord(); + } + + public int computeLongestWord() + { + previouslyComputedLongestWord = 1; + + // hmmm: iterate on set to find longest. + + // kludge implem placeholder. + previouslyComputedLongestWord = 100; + return previouslyComputedLongestWord; + } + + public boolean lookup(String toFind) + { + return contains(toFind); + } + + public int longestWord() + { + return previouslyComputedLongestWord; + } + + int previouslyComputedLongestWord; +} diff --git a/nucleus/.settings/language.settings.xml b/nucleus/.settings/language.settings.xml index 2d5ebe3a..661a8589 100644 --- a/nucleus/.settings/language.settings.xml +++ b/nucleus/.settings/language.settings.xml @@ -5,7 +5,7 @@ - + -- 2.34.1