PR to add some problem. (keon#375)

Hai Hoang Dang · goswami-rahul · commit 77054e71123a · 2018-07-18T15:01:03.000+05:30
* Add next_greatest_letter to search

* Move top sort test into test_sort

* Add min_distance to string

* Add binary_gap to bit
diff --git a/README.md b/README.md
@@ -112,6 +112,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [has_alternative_bit](algorithms/bit/has_alternative_bit.py)
     - [insert_bit](algorithms/bit/insert_bit.py)
     - [remove_bit](algorithms/bit/remove_bit.py)
+    - [binary_gap](algorithms/bit/binary_gap.py)
 - [calculator](algorithms/calculator)
     - [math_parser](algorithms/calculator/math_parser.py)
 - [dfs](algorithms/dfs)
@@ -226,6 +227,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [find_min_rotate](algorithms/search/find_min_rotate.py)
     - [search_rotate](algorithms/search/search_rotate.py)
     - [jump_search](algorithms/search/jump_search.py)
+    - [next_greatest_letter](algorithms/search/next_greatest_letter.py)
 - [set](algorithms/set)
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
@@ -292,6 +294,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [contain_string](algorithms/strings/contain_string.py)
     - [count_binary_substring](algorithms/strings/count_binary_substring.py)
     - [repeat_string](algorithms/strings/repeat_string.py)
+    - [min_distance](algorithms/strings/min_distance.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/algorithms/bit/__init__.py b/algorithms/bit/__init__.py
@@ -15,3 +15,4 @@
 from .remove_bit import *
 from .count_flips_to_convert import *
 from .flip_bit_longest_sequence import *
+from .binary_gap import *
diff --git a/algorithms/bit/binary_gap.py b/algorithms/bit/binary_gap.py
@@ -0,0 +1,27 @@
+"""
+Given a positive integer N, find and return the longest distance between two
+consecutive 1' in the binary representation of N.
+If there are not two consecutive 1's, return 0
+
+For example:
+Input: 22
+Output: 2
+Explanation:
+22 in binary is 10110
+In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
+The first consecutive pair of 1's have distance 2.
+The second consecutive pair of 1's have distance 1.
+The answer is the largest of these two distances, which is 2
+"""
+def binary_gap(N):
+    last = None
+    ans = 0
+    index = 0
+    while N != 0:
+        if N & 1:
+            if last is not None:
+                ans = max(ans, index - last)
+            last = index
+        index = index + 1
+        N = N >> 1
+    return ans
diff --git a/algorithms/search/__init__.py b/algorithms/search/__init__.py
@@ -8,3 +8,4 @@
 from .find_min_rotate import *
 from .search_rotate import *
 from .jump_search import *
+from .next_greatest_letter import *
diff --git a/algorithms/search/next_greatest_letter.py b/algorithms/search/next_greatest_letter.py
@@ -0,0 +1,60 @@
+'''
+Given a list of sorted characters letters containing only lowercase letters,
+and given a target letter target, find the smallest element in the list that
+is larger than the given target.
+
+Letters also wrap around. For example, if the target is target = 'z' and
+letters = ['a', 'b'], the answer is 'a'.
+
+Input:
+letters = ["c", "f", "j"]
+target = "a"
+Output: "c"
+
+Input:
+letters = ["c", "f", "j"]
+target = "c"
+Output: "f"
+
+Input:
+letters = ["c", "f", "j"]
+target = "d"
+Output: "f"
+
+Reference: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/
+'''
+
+import bisect
+
+"""
+Using bisect libarary
+"""
+def next_greatest_letter(letters, target):
+    index = bisect.bisect(letters, target)
+    return letters[index % len(letters)]
+
+"""
+Using binary search: complexity O(logN)
+"""
+def next_greatest_letter_v1(letters, target):
+    if letters[0] > target:
+        return letters[0]
+    if letters[len(letters) - 1] <= target:
+        return letters[0]
+    left, right = 0, len(letters) - 1
+    while left <= right:
+        mid = left + (right - left) // 2
+        if  letters[mid] > target:
+            right = mid - 1
+        else:
+            left = mid + 1
+    return letters[left]    
+
+"""
+Brute force: complexity O(N)
+"""
+def next_greatest_letter_v2(letters, target):
+    for index in letters:
+        if index > target:
+            return index
+    return letters[0]
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
@@ -28,4 +28,5 @@
 from .contain_string import *
 from .count_binary_substring import *
 from .repeat_string import *
-from .text_justification import *
+from .text_justification import *
+from .min_distance import *
diff --git a/algorithms/strings/min_distance.py b/algorithms/strings/min_distance.py
@@ -0,0 +1,28 @@
+"""
+Given two words word1 and word2, find the minimum number of steps required to
+make word1 and word2 the same, where in each step you can delete one character
+in either string.
+
+For example:
+Input: "sea", "eat"
+Output: 2
+Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
+
+Reference: https://leetcode.com/problems/delete-operation-for-two-strings/description/
+"""
+
+def min_distance(word1, word2):
+    return len(word1) + len(word2) - 2 * lcs(word1, word2, len(word1), len(word2))
+
+def lcs(s1, s2, i, j):
+    """
+    The length of longest common subsequence among the two given strings s1 and s2
+    """
+    if i == 0 or j == 0:
+        return 0
+    elif s1[i - 1] == s2[j - 1]:
+        return 1 + lcs(s1, s2, i - 1, j - 1)
+    else:
+        return max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1))
+
+# TODO: Using dynamic programming
diff --git a/tests/graph/__init__.py b/tests/graph/__init__.py
diff --git a/tests/graph/test_topsort.py b/tests/graph/test_topsort.py
diff --git a/tests/test_bit.py b/tests/test_bit.py
@@ -15,7 +15,8 @@
     find_difference,
     has_alternative_bit, has_alternative_bit_fast,
     insert_one_bit, insert_mult_bits,
-    remove_bit
+    remove_bit,
+    binary_gap
 )
 
 import unittest
@@ -238,6 +239,16 @@ def test_remove_bit(self):
         self.assertEqual(5, remove_bit(21, 4))
         self.assertEqual(10, remove_bit(21, 0))
 
+    def test_binary_gap(self):
+        # 22 = 10110
+        self.assertEqual(2, binary_gap(22))
+        # 6 = 110
+        self.assertEqual(1, binary_gap(6))
+        # 8 = 1000
+        self.assertEqual(0, binary_gap(8))
+        # 145 = 10010001
+        self.assertEqual(4, binary_gap(145))
+
 
 if __name__ == '__main__':
     unittest.main()
diff --git a/tests/test_search.py b/tests/test_search.py
@@ -8,7 +8,8 @@
     search_range,
     find_min_rotate, find_min_rotate_recur,
     search_rotate, search_rotate_recur,
-    jump_search
+    jump_search,
+    next_greatest_letter, next_greatest_letter_v1, next_greatest_letter_v2
 )
 
 import unittest
@@ -46,7 +47,7 @@ def test_last_occurrence(self):
         self.assertEqual(None, last_occurrence(array, 7))
         self.assertEqual(0, last_occurrence(array, 1))
         self.assertEqual(13, last_occurrence(array, 6))
-        
+
     def test_linear_search(self):
         array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
         self.assertEqual(6, linear_search(array, 4))
@@ -103,7 +104,24 @@ def test_jump_search(self):
         self.assertEqual(2, jump_search(array, 3))
         self.assertEqual(-1, jump_search(array, 7))
         self.assertEqual(-1, jump_search(array, -1))
-        
+
+    def test_next_greatest_letter(self):
+        letters = ["c", "f", "j"]
+        target = "a"
+        self.assertEqual("c", next_greatest_letter(letters, target))
+        self.assertEqual("c", next_greatest_letter_v1(letters, target))
+        self.assertEqual("c", next_greatest_letter_v2(letters, target))
+        letters = ["c", "f", "j"]
+        target = "d"
+        self.assertEqual("f", next_greatest_letter(letters, target))
+        self.assertEqual("f", next_greatest_letter_v1(letters, target))
+        self.assertEqual("f", next_greatest_letter_v2(letters, target))
+        letters = ["c", "f", "j"]
+        target = "j"
+        self.assertEqual("c", next_greatest_letter(letters, target))
+        self.assertEqual("c", next_greatest_letter_v1(letters, target))
+        self.assertEqual("c", next_greatest_letter_v2(letters, target))
+
 if __name__ == '__main__':
 
     unittest.main()
diff --git a/tests/test_sort.py b/tests/test_sort.py
@@ -16,6 +16,7 @@
     radix_sort,
     gnome_sort,
     cocktail_shaker_sort,
+    top_sort, top_sort_recursive
 )
 
 import unittest
@@ -25,15 +26,15 @@ class TestSuite(unittest.TestCase):
     def test_bogo_sort(self):
         self.assertEqual([1, 5, 23],
                          bogo_sort([1, 23, 5]))
-    
+
     def test_bitonic_sort(self):
         self.assertEqual([1, 2, 3, 5, 23, 57, 65, 1232],
                          bitonic_sort([1, 3, 2, 5, 65, 23, 57, 1232]))
         self.assertEqual([1, 2, 3, 5, 23, 57, 65, 1232],
                          bitonic_sort([1, 3, 2, 5, 65, 23, 57, 1232],False))
         self.assertEqual([1232, 65, 57, 23, 5, 3, 2, 1],
-                         bitonic_sort([1, 2, 3, 5, 65, 23, 57, 1232],True))  
-   
+                         bitonic_sort([1, 2, 3, 5, 65, 23, 57, 1232],True))
+
     def test_bubble_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          bubble_sort([1, 5, 65, 23, 57, 1232]))
@@ -69,7 +70,7 @@ def test_merge_sort(self):
     def test_pancake_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          pancake_sort([1, 5, 65, 23, 57, 1232]))
-        
+
     def test_quick_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          quick_sort([1, 5, 65, 23, 57, 1232]))
@@ -85,19 +86,38 @@ def test_bucket_sort(self):
     def test_shell_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                         shell_sort([1, 5, 65, 23, 57, 1232]))
-                                          
+
     def test_radix_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                         radix_sort([1, 5, 65, 23, 57, 1232]))
-    
+
     def test_gnome_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          gnome_sort([1, 5, 65, 23, 57, 1232]))
-                                          
+
     def test_cocktail_shaker_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                         cocktail_shaker_sort([1, 5, 65, 23, 57, 1232]))
 
+class TestTopSort(unittest.TestCase):
+    def setUp(self):
+        self.depGraph = {
+                            "a" : [ "b" ],
+                            "b" : [ "c" ],
+                            "c" :  [ 'e'],
+                            'e' : [ 'g' ],
+                            "d" : [ ],
+                            "f" : ["e" , "d"],
+                            "g" : [ ]
+                        }
+
+    def test_topsort(self):
+        res = top_sort_recursive(self.depGraph)
+        #print(res)
+        self.assertTrue(res.index('g') < res.index('e'))
+        res = top_sort(self.depGraph)
+        self.assertTrue(res.index('g') < res.index('e'))
+
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_strings.py b/tests/test_strings.py
@@ -31,7 +31,8 @@
     contain_string,
     count_binary_substring,
     repeat_string,
-    text_justification
+    text_justification,
+    min_distance
 )
 
 import unittest
@@ -469,6 +470,11 @@ def test_text_justification(self):
                                             , 16)
                          )
 
+class TestMinDistance(unittest.TestCase):
+    def test_min_distance(self):
+        self.assertEqual(2, min_distance("sea", "eat"))
+        self.assertEqual(6, min_distance("abAlgocrithmf", "Algorithmmd"))
+
 
 if __name__ == "__main__":
     unittest.main()
