rabin karp water and jug

sherxon · Jan 13, 2017 · f31af2a · f31af2a
1 parent 92aa4a1
commit f31af2a
Show file tree

Hide file tree

Showing 6 changed files with 90 additions and 17 deletions.
diff --git a/README.md b/README.md
@@ -15,8 +15,8 @@ Interview Questions package include 3 text files (_1easy, 2medium and 3Hard_) an
 3) [Find Peak Element](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/medium/FindPeakElement.java)  
 4) [Maximum Subarray](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/medium/MaximumSubarray.java)  
 5) [Kth Largest Element in an Array](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/medium/KthLargestElementinanArray.java)  
-6) [Find All Duplicates in an Array]()
-[And many other array problems](https://github.com/sherxon/AlgoDS/tree/master/src/interviewquestions)
+6) [Find All Duplicates in an Array](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/medium/FindAllDuplicatesinanArray.java)  
+[And many other array problems](https://github.com/sherxon/AlgoDS/tree/master/src/interviewquestions)  
 
 ###Linked List
 1) [Delete Node in a Linked List](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/easy/DeleteNodeSingleLinkedList.java)  
@@ -55,7 +55,9 @@ Interview Questions package include 3 text files (_1easy, 2medium and 3Hard_) an
 2) [Reverse Bits](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/easy/ReverseBits.java)   
 3) [Palindrome Number](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/easy/PalindromeNumber.java)  
 4) [Math.pow](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/medium/Pow.java)  
+5) [Jug and Water Problem](https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/medium/WaterAndJugProblem.java)  
 
+
 ##Algorithms
 
 ###Sorting And Searching:    
@@ -78,6 +80,8 @@ Interview Questions package include 3 text files (_1easy, 2medium and 3Hard_) an
 0)[Introduction](https://github.com/sherxon/AlgoDS/blob/master/src/algo/DPIntroduction.md)  
 1)Fibonacci Numbers  
 
+###String
+1)[Rabin Karp Subsequence search](https://github.com/sherxon/AlgoDS/blob/master/src/algo/string/RabinKarpSubsequenceSearch.java)   
 
 ##Data Structure:      
 

diff --git a/src/algo/graph/TopologicalSorting.java b/src/algo/graph/TopologicalSorting.java
@@ -37,12 +37,12 @@ List<T> topSort(){
     }
 
     private void dfs(Vertex<T> source, List<T> list) {
-        list.add(source.getValue());
         source.setVisited(true);
         for (Vertex<T> vertex : source.getNeighbors()) {
             if(!vertex.isVisited()){
                 dfs(vertex, list);
             }
         }
+        list.add(source.getValue());
     }
 }
diff --git a/src/algo/string/RabinKarpSubsequenceSearch.java b/src/algo/string/RabinKarpSubsequenceSearch.java
@@ -0,0 +1,61 @@
+package algo.string;
+
+/**
+ * Created by sherxon on 1/12/17.
+ */
+
+/**
+ * This is Rabin Karp substring match algorithm. Time complexity is O(MxN), where m is length of string
+ * to be matched and N is substring length. Worst case happens when all hash codes are the same and string
+ * equal method checks all combinations. This is very rare if good hash function is used.
+ * The idea is simple, calculating hash code of substring and text at length of substring
+ * and check if these hashes are equal and substrings are also the same. To optimize hashing each sub-sequence
+ * we can use rolling hash function which is constant time hash generation algorithm
+ */
+
+public class RabinKarpSubsequenceSearch {
+    int prime = 31;
+
+    public static void main(String[] args) {
+        RabinKarpSubsequenceSearch rks = new RabinKarpSubsequenceSearch();
+        System.out.println(rks.searchPattern("Sherxon".toCharArray(), "n".toCharArray()));
+        System.out.println(rks.searchPattern("Sherxon".toCharArray(), "xon".toCharArray()));
+        System.out.println(rks.searchPattern("Sherxon".toCharArray(), "hs".toCharArray()));
+        System.out.println(rks.searchPattern("Sherxon".toCharArray(), "erx".toCharArray()));
+        System.out.println(rks.searchPattern("Sherxon".toCharArray(), "S".toCharArray()));
+    }
+
+    public int searchPattern(char[] text, char[] pattern) {
+        int m = text.length;
+        int n = pattern.length;
+        int textHash = hash(text, n);
+        int patternHash = hash(pattern, n);
+        for (int i = 0; i <= m - n; i++) {
+            if (patternHash == textHash && equal(text, pattern, i)) return i;
+            if (i < m - n) textHash = reHash(textHash, text[i], text[i + n], n);
+
+        }
+        return -1;
+    }
+
+    private int reHash(int textHash, char first, char last, int length) {
+        int h = (textHash - first) / prime;
+        h += Math.pow(prime, length - 1) * last;
+        return h;
+    }
+
+    private boolean equal(char[] text, char[] pattern, int from) {
+        for (int i = 0; i < pattern.length; i++)
+            if (text[i + from] != pattern[i])
+                return false;
+        return true;
+    }
+
+    private int hash(char[] s, int to) {
+        int h = 0;
+        for (int i = 0; i < to; i++) {
+            h += Math.pow(prime, i) * s[i];
+        }
+        return h;
+    }
+}
diff --git a/src/interviewquestions/1Easy.md b/src/interviewquestions/1Easy.md
@@ -156,7 +156,7 @@ Given "egg", "add", return true.
 Given "foo", "bar", return false.
 Given "paper", "title", return true.
 
-29)** Linked List Cycle**
+29)**Linked List Cycle**
 Given a linked list, determine if it has a cycle in it.
 Can you solve it without using extra space?
 
@@ -172,7 +172,7 @@ For example,
 Given 1->1->2, return 1->2.
 Given 1->1->2->3->3, return 1->2->3.
 
-33)** Remove Linked List Elements**
+33)**Remove Linked List Elements**
 Remove all elements from a linked list of integers that have value val.
 Example
 Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6

diff --git a/src/interviewquestions/medium/FindAllDuplicatesinanArray.java b/src/interviewquestions/medium/FindAllDuplicatesinanArray.java
@@ -9,18 +9,6 @@
 
 public class FindAllDuplicatesinanArray {
 
-    public static void main(String[] args) {
-        int n=43261596;
-        String padding = "00000000000000000000000000000000";
-        String result = padding + Integer.toBinaryString(n);
-        result = result.substring(result.length() - 32, result.length());  // take the right-most 64 digits
-        char[] a=result.toCharArray();
-        StringBuilder sb= new StringBuilder();
-        for(int i=a.length-1; i>=0; i--)
-            sb.append(a[i]);
-        System.out.println(Integer.parseUnsignedInt(sb.toString(), 2));
-    }
-
     /**
     * This find all duplicate elements from array. The idea is to negate previous elements. if the previous element
     * is already negative this element is duplicate. Time complexity is O(N) and in-place.

diff --git a/src/interviewquestions/medium/WaterAndJugProblem.java b/src/interviewquestions/medium/WaterAndJugProblem.java
@@ -0,0 +1,20 @@
+package interviewquestions.medium;
+
+/**
+ * Created by sherxon on 1/12/17.
+ */
+public class WaterAndJugProblem {
+
+
+    boolean canMeasureWater(int x, int y, int z) {
+        if (x == z || y == z) return true;
+        if (x == 0 || y == 0 || x + y < z) return false;
+        int a = getGCD(x, y);
+        return z % a == 0;
+    }
+
+    int getGCD(int x, int y) {
+        if (y == 0) return x;
+        return getGCD(y, x % y);
+    }
+}