updated Trie problem

ssdash · Apr 26, 2017 · 9b6ef0f · 9b6ef0f
1 parent 4bc5d0b
commit 9b6ef0f
Show file tree

Hide file tree

Showing 9 changed files with 108 additions and 89 deletions.
diff --git a/30 Days of Code/Day 23 - BST Level-Order Traversal/Solution.java b/30 Days of Code/Day 23 - BST Level-Order Traversal/Solution.java
@@ -15,23 +15,25 @@ class Node {
 }
 
 class Solution {
-    static void levelOrder(Node root){
-        ArrayDeque<Node> deque = new ArrayDeque<>(); // use deque as a queue
-        if (root != null) {
-            deque.add(root);
+    static void levelOrder(Node root) {
+        if (root == null) {
+            return;
         }
+        ArrayDeque<Node> deque = new ArrayDeque<>(); // use deque as a queue
+        deque.add(root);
         while (!deque.isEmpty()) {
-            Node n = deque.remove();
+            Node n = deque.removeFirst();
             System.out.print(n.data + " ");
             if (n.left != null) {
-                deque.add(n.left);
+                deque.addLast(n.left);
             }
             if (n.right != null) {
-                deque.add(n.right);
+                deque.addLast(n.right);
             }
         }
     }
 
+
     public static Node insert(Node root,int data){
         if (root == null) {
             return new Node(data);

diff --git a/Algorithms/Bit Manipulation/Counter game/Solution.java b/Algorithms/Bit Manipulation/Counter game/Solution.java
@@ -37,8 +37,6 @@
 // Original Number: 10110100
 //     Number - 1 : 10110011   and the number of 1s is 5
 
-// We use a BigInteger instead of a long since we can't easily read in an UNSIGNED long.
-
 public class Solution {
     public static void main(String [] args) {
         Scanner scan = new Scanner(System.in);

diff --git a/Algorithms/Greedy/Luck Balance/Solution.java b/Algorithms/Greedy/Luck Balance/Solution.java
@@ -30,7 +30,7 @@ public static void main(String [] args) {
         scan.close();
 
         /* Compete in "important" contests */
-        quickselect(contest, 0, contest.size() - 1, contest.size() - K);
+        quickselect(contest, contest.size() - K);
         for (int i = 0; i < contest.size(); i++) {
             if (i < contest.size() - K) {
                 savedLuck -= contest.get(i); // win contest
@@ -49,24 +49,20 @@ public static void main(String [] args) {
      *    Our formula above is a geometric series with "r = 1/2", which would converge to 1/(1-r) for infinite geometric series
      *  - O(n^2) worst-case run-time is if we consistently pick a bad pivot
      */
-    private static Integer quickselect(ArrayList<Integer> list, int start, int end, int n) {
-        if (n < 0 || n >= list.size() || start < 0 || start >= list.size() || end < 0 || end >= list.size()) {
-            return null;
-        }
-
-        if (start == end) { // a 1-element list is our base case
-            return list.get(start);
-        }
-        int pivotIndex = partition(list, start, end);
-
-        /* Recurse on only 1 side, until found */
-        if (n == pivotIndex) {
-            return list.get(pivotIndex);
-        } else if (n < pivotIndex) {
-            return quickselect(list, start, pivotIndex - 1, n);
-        } else {
-            return quickselect(list, pivotIndex + 1, end, n);
+    private static Integer quickselect(ArrayList<Integer> list, int n) {
+        int start = 0;
+        int end = list.size() - 1;
+        while (start <= end) {
+            int pivotIndex = partition(list, start, end);
+            if (pivotIndex == n) {
+                return list.get(n);
+            } else if (pivotIndex < n) {
+                start = pivotIndex + 1;
+            } else {
+                end = pivotIndex - 1;
+            }
         }
+        return null;
     }
 
     /* Partitions list into 2 parts. 

diff --git a/Cracking the Coding Interview/Data Structures/Tries - Contacts/Solution.java b/Cracking the Coding Interview/Data Structures/Tries - Contacts/Solution.java
@@ -6,56 +6,69 @@
 import java.util.HashMap;
 
 public class Solution {
-
-    private static TrieNode root = new TrieNode();
-
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         int n = scan.nextInt();
+        Trie trie = new Trie();
         for (int i = 0; i < n; i++) {
             String operation = scan.next();
             String contact   = scan.next();
             if (operation.equals("add")) {
-                add(contact);
+                trie.add(contact);
             } else if (operation.equals("find")) {
-                System.out.println(find(contact));
+                System.out.println(trie.find(contact));
             }
         }
         scan.close();
     }
+}
+
+/* Based loosely on tutorial video in this problem */
+class TrieNode {
+    private HashMap<Character, TrieNode> children = new HashMap<>();
+    public int size = 0; // this was the main trick to decrease runtime to pass tests.
+
+    public void putChildIfAbsent(char ch) {
+        children.putIfAbsent(ch, new TrieNode());
+    }
+
+    public TrieNode getChild(char ch) {
+        return children.get(ch);
+    }
+}
+
+class Trie {
+    TrieNode root = new TrieNode();
 
-    private static void add(String str) {
+    Trie(){} // default constructor
+
+    Trie(String[] words) {
+        for (String word : words) {
+            add(word);
+        }
+    }
+
+    public void add(String str) {
         TrieNode curr = root;
         for (int i = 0; i < str.length(); i++) {
             Character ch = str.charAt(i);
-            curr.addChildIfAbsent(ch);
-            curr = curr.children.get(ch);
+            curr.putChildIfAbsent(ch);
+            curr = curr.getChild(ch);
             curr.size++;
         }
     }
-
-    private static int find(String prefix) {
+    
+    public int find(String prefix) {
         TrieNode curr = root;
 
         /* Traverse down tree to end of our prefix */
         for (int i = 0; i < prefix.length(); i++) {
             Character ch = prefix.charAt(i);
-            if (!curr.children.containsKey(ch)) {
+            curr = curr.getChild(ch);
+            if (curr == null) {
                 return 0;
-            } else {
-                curr = curr.children.get(ch);
             }
         }
         return curr.size;
     }
-
-    /* This implementation is somewhat based off the tutorial video in this problem */
-    public static class TrieNode { // must be a nested class since it's "static"
-        public HashMap<Character, TrieNode> children = new HashMap<>();
-        public int size = 0; // this was the main trick to decrease runtime to pass tests.
-
-        public void addChildIfAbsent(Character ch) {
-            children.putIfAbsent(ch, new TrieNode());
-        }
-    }
 }
diff --git a/Data Structures/Trie/Contacts/Solution.java b/Data Structures/Trie/Contacts/Solution.java
@@ -6,56 +6,69 @@
 import java.util.HashMap;
 
 public class Solution {
-
-    private static TrieNode root = new TrieNode();
-
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         int n = scan.nextInt();
+        Trie trie = new Trie();
         for (int i = 0; i < n; i++) {
             String operation = scan.next();
             String contact   = scan.next();
             if (operation.equals("add")) {
-                add(contact);
+                trie.add(contact);
             } else if (operation.equals("find")) {
-                System.out.println(find(contact));
+                System.out.println(trie.find(contact));
             }
         }
         scan.close();
     }
+}
+
+/* Based loosely on tutorial video in this problem */
+class TrieNode {
+    private HashMap<Character, TrieNode> children = new HashMap<>();
+    public int size = 0; // this was the main trick to decrease runtime to pass tests.
+
+    public void putChildIfAbsent(char ch) {
+        children.putIfAbsent(ch, new TrieNode());
+    }
+
+    public TrieNode getChild(char ch) {
+        return children.get(ch);
+    }
+}
+
+class Trie {
+    TrieNode root = new TrieNode();
 
-    private static void add(String str) {
+    Trie(){} // default constructor
+
+    Trie(String[] words) {
+        for (String word : words) {
+            add(word);
+        }
+    }
+
+    public void add(String str) {
         TrieNode curr = root;
         for (int i = 0; i < str.length(); i++) {
             Character ch = str.charAt(i);
-            curr.addChildIfAbsent(ch);
-            curr = curr.children.get(ch);
+            curr.putChildIfAbsent(ch);
+            curr = curr.getChild(ch);
             curr.size++;
         }
     }
-
-    private static int find(String prefix) {
+    
+    public int find(String prefix) {
         TrieNode curr = root;
 
         /* Traverse down tree to end of our prefix */
         for (int i = 0; i < prefix.length(); i++) {
             Character ch = prefix.charAt(i);
-            if (!curr.children.containsKey(ch)) {
+            curr = curr.getChild(ch);
+            if (curr == null) {
                 return 0;
-            } else {
-                curr = curr.children.get(ch);
             }
         }
         return curr.size;
     }
-
-    /* This implementation is somewhat based off the tutorial video in this problem */
-    public static class TrieNode { // must be a nested class since it's "static"
-        public HashMap<Character, TrieNode> children = new HashMap<>();
-        public int size = 0; // this was the main trick to decrease runtime to pass tests.
-
-        public void addChildIfAbsent(Character ch) {
-            children.putIfAbsent(ch, new TrieNode());
-        }
-    }
 }
diff --git a/Java/Advanced/Java Visitor Pattern/Solution.java b/Java/Advanced/Java Visitor Pattern/Solution.java
@@ -151,12 +151,7 @@ public static Tree solve() {
         Scanner scan = new Scanner(System.in);
         int numNodes = scan.nextInt();
 
-        /* Handle 1-node tree */
-        if (numNodes == 1) {
-            return new TreeLeaf(values[0], colors[0], 0);
-        }
-
-        /* Read and save nodes and colors */
+        /* Save nodes and colors */
         values = new int[numNodes];
         colors = new Color[numNodes];
         map = new HashMap<>(numNodes);
@@ -190,6 +185,11 @@ public static Tree solve() {
         }
         scan.close();
 
+        /* Handle 1-node tree */
+        if (numNodes == 1) {
+            return new TreeLeaf(values[0], colors[0], 0);
+        }
+
         /* Create Tree */
         TreeNode root = new TreeNode(values[0], colors[0], 0);
         addChildren(root, 1);

diff --git a/Java/Data Structures/Java Dequeue/Solution.java b/Java/Data Structures/Java Dequeue/Solution.java
@@ -27,7 +27,7 @@ public static void main(String [] args) {
         for (int i = 0; i < n; i++) {
             /* Remove old value (if necessary) */
             if (i >= m) {
-                int old = deque.remove();
+                int old = deque.removeFirst();
                 if (map.get(old) == 1) {
                     map.remove(old);
                 } else {
@@ -37,7 +37,7 @@ public static void main(String [] args) {
 
             /* Add new value */
             int num = scan.nextInt();
-            deque.add(num);
+            deque.addLast(num);
             map.merge(num, 1, Integer::sum);
 
             max = Math.max(max, map.size());

diff --git a/Java/Data Structures/Java Priority Queue/Solution.java b/Java/Data Structures/Java Priority Queue/Solution.java
@@ -64,10 +64,9 @@ public static void main(String[] args) {
 }
 
 class StudentComparator implements Comparator<Student> {
-    double epsilon = 0.001; // since we shouldn't use "==" with doubles
     @Override
     public int compare(Student s1, Student s2) {
-        if (Math.abs(s1.getCgpa() - s2.getCgpa()) > epsilon) {
+        if (Double.compare(s1.getCgpa(), s2.getCgpa()) != 0) {
             return s1.getCgpa() < s2.getCgpa() ? 1 : -1; // descending order
         } else if ( ! s1.getFname().equals(s2.getFname())) {
             return s1.getFname().compareTo(s2.getFname());

diff --git a/Java/Data Structures/Java Subarray/Solution.java b/Java/Data Structures/Java Subarray/Solution.java
@@ -4,16 +4,15 @@
 
 import java.util.Scanner;
 
-// Our subarray must be contiguous, so we have O(n^2) contiguous subarrays
+// A subarray must be contiguous. There are O(n^2) contiguous subarrays.
 
 //  Time Complexity: O(n^2)
 // Space Complexity: O(1)
 public class Solution {
     public static void main(String[] args) {
-        /* Save input */
         Scanner scan = new Scanner(System.in);
         int size     = scan.nextInt();
-        int [] array = new int[size];        
+        int[] array = new int[size];        
         for (int i = 0; i < size; i++) {
             array[i] = scan.nextInt();
         }
@@ -22,17 +21,16 @@ public static void main(String[] args) {
         System.out.println(negativeSubarrays(array));
     }
 
-    private static int negativeSubarrays(int [] array) {
+    private static int negativeSubarrays(int[] array) {
         int count = 0;
-        int sum   = 0;
         for (int i = 0; i < array.length; i++) {
+            int sum = 0;
             for (int j = i; j < array.length; j++) {
                 sum += array[j];
                 if (sum < 0) {
                     count++;
                 }
             }
-            sum = 0;
         }
         return count;
     }