Repository: keon/algorithms (python)

Issue:
separate test module
Since we now have tests in most of the algorithms, I think it is a good idea to have a separate `test_module.py` file in each module. We can move all the tests from one module to it, and any further algorithms must have their tests in this file. It will make the repo easy to manage.
@keon what do you think? I can start working on this.

Pull request:
Separate test for search, and add some problem
PR for separating test for search, and add some problem.
Fix #162 

Patch:
diff --git a/README.md b/README.md
index 7db62fb..c14d6bb 100644
--- a/README.md
+++ b/README.md
@@ -161,6 +161,11 @@ To run the tests, clone the repo and run :
     - [binary_search](search/binary_search.py)
     - [first_occurance](search/first_occurance.py)
     - [last_occurance](search/last_occurance.py)
+    - [search_insert](search/search_insert.py)
+    - [two_sum](search/two_sum.py)
+    - [search_range](search/search_range.py)
+    - [find_min_rotate](search/find_min_rotate.py)
+    - [search_rotate](search/search_rotate.py)
 - [set](set)
     - [randomized_set](set/randomized_set.py)
     - [set_covering](set/set_covering.py)
@@ -188,7 +193,9 @@ To run the tests, clone the repo and run :
     - [remove_min](stack/remove_min.py)
     - [is_sorted](stack/is_sorted.py)
 - [strings](strings)
+    - [delete_reoccurring_characters](strings/delete_reoccurring_characters.py)
     - [strip_url_params](strings/strip_url_params.py)
+    - [validate_coordinates](strings/validate_coordinates.py)
     - [domain_extractor](strings/domain_extractor.py)
     - [merge_string_checker](strings/merge_string_checker.py)
     - [add_binary](strings/add_binary.py)
diff --git a/search/binary_search.py b/search/binary_search.py
index b47bae1..644f98f 100644
--- a/search/binary_search.py
+++ b/search/binary_search.py
@@ -4,8 +4,6 @@
 #       increasing order.
 # T(n): O(log n)
 #
-
-
 def binary_search(array, query):
     lo, hi = 0, len(array) - 1
     while lo <= hi:
@@ -19,19 +17,13 @@ def binary_search(array, query):
             hi = mid - 1
     return None
 
-
-def main():
-    array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6]
-    print(array)
-    print("-----SEARCH-----")
-    print("found: ", 5, " in index:", binary_search(array, 5))
-    print("-----SEARCH-----")
-    print("found: ", 6, " in index:", binary_search(array, 6))
-    print("-----SEARCH-----")
-    print("found: ", 7, " in index:", binary_search(array, 7))
-    print("-----SEARCH-----")
-    print("found: ", -1, " in index:", binary_search(array, -1))
-    print("-----SEARCH-----")
-
-if __name__ == "__main__":
-    main()
+def binary_search_recur(array, low, high, val):
+    if low > high:       # error case
+        return -1
+    mid = (low + high) // 2
+    if val < array[mid]:
+        return binary_search_recur(array, low, mid - 1, val)
+    elif val > array[mid]:
+        return binary_search_recur(array, mid + 1, high, val)
+    else:
+        return mid
diff --git a/search/find_min_rotate.py b/search/find_min_rotate.py
new file mode 100644
index 0000000..1afc4ee
--- /dev/null
+++ b/search/find_min_rotate.py
@@ -0,0 +1,28 @@
+"""
+Suppose an array sorted in ascending order is rotated at some pivot unknown
+to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
+
+Find the minimum element. The complexity must be O(logN)
+
+You may assume no duplicate exists in the array.
+"""
+def find_min_rotate(array):
+    low = 0
+    high = len(array) - 1
+    while low < high:
+        mid = (low + high) // 2
+        if array[mid] > array[high]:
+            low = mid + 1
+        else:
+            high = mid
+
+    return array[low]
+
+def find_min_rotate_recur(array, low, high):
+    mid = (low + high) // 2
+    if mid == low:
+        return array[low]
+    elif array[mid] > array[high]:
+        return find_min_rotate_recur(array, mid + 1, high)
+    else:
+        return find_min_rotate_recur(array, low, mid)
diff --git a/search/first_occurance.py b/search/first_occurance.py
index f4d8c75..addf170 100644
--- a/search/first_occurance.py
+++ b/search/first_occurance.py
@@ -3,10 +3,7 @@
 # Approach- Binary Search
 # T(n)- O(log n)
 #
-
-import unittest
-
-def firstOccurance(array, query):
+def first_occurance(array, query):
     lo, hi = 0, len(array) - 1
     while lo <= hi:
         mid = (lo + hi) // 2
@@ -19,22 +16,3 @@ def firstOccurance(array, query):
             hi = mid
     if array[lo] == query:
       return lo
-
-class TestSuite(unittest.TestCase):
-
-    def test_firstOccurance(self):
-        def helper(array, query):
-            idx = array.index(query) if query in array else None
-            return idx
-        array = [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
-        self.assertEqual(firstOccurance(array, 1), helper(array, 1))
-        self.assertEqual(firstOccurance(array, 3), helper(array, 3))
-        self.assertEqual(firstOccurance(array, 5), helper(array, 5))
-        self.assertEqual(firstOccurance(array, 6), helper(array, 6))
-        self.assertEqual(firstOccurance(array, 7), helper(array, 7))
-        self.assertEqual(firstOccurance(array, -1), helper(array, -1))
-
-
-if __name__ == '__main__':
-
-    unittest.main()
diff --git a/search/last_occurance.py b/search/last_occurance.py
index e9b705d..b8ee4fa 100644
--- a/search/last_occurance.py
+++ b/search/last_occurance.py
@@ -3,9 +3,7 @@
 # Approach- Binary Search
 # T(n)- O(log n)
 #
-
-
-def lastOccurance(array, query):
+def last_occurance(array, query):
     lo, hi = 0, len(array) - 1
     while lo <= hi:
         mid = (hi + lo) // 2
@@ -16,32 +14,3 @@ def lastOccurance(array, query):
             lo = mid + 1
         else:
             hi = mid - 1
-
-
-def main():
-    array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
-    print(array)
-    print("-----SEARCH-----")
-    query = 3
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 5
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 7
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 1
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-    print("-----SEARCH-----")
-    query = -1
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 9
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 6
-    print("found last: ", query, " in index:", lastOccurance(array, query))
-
-if __name__ == "__main__":
-    main()
diff --git a/search/search_insert.py b/search/search_insert.py
new file mode 100644
index 0000000..b10eb7d
--- /dev/null
+++ b/search/search_insert.py
@@ -0,0 +1,20 @@
+"""
+Given a sorted array and a target value, return the index if the target is
+found. If not, return the index where it would be if it were inserted in order.
+
+For example:
+[1,3,5,6], 5 -> 2
+[1,3,5,6], 2 -> 1
+[1,3,5,6], 7 -> 4
+[1,3,5,6], 0 -> 0
+"""
+def search_insert(array, val):
+    low = 0
+    high = len(array) - 1
+    while low <=  high:
+        mid = low + (high - low) // 2
+        if val > array[mid]:
+            low = mid + 1
+        else:
+            high = mid - 1
+    return low
diff --git a/search/search_range.py b/search/search_range.py
new file mode 100644
index 0000000..116d8f5
--- /dev/null
+++ b/search/search_range.py
@@ -0,0 +1,33 @@
+"""
+Given an array of integers nums sorted in ascending order, find the starting
+and ending position of a given target value. If the target is not found in the
+array, return [-1, -1].
+
+For example:
+Input: nums = [5,7,7,8,8,8,10], target = 8
+Output: [3,5]
+Input: nums = [5,7,7,8,8,8,10], target = 11
+Output: [-1,-1]
+"""
+def search_range(nums, target):
+    """
+    :type nums: List[int]
+    :type target: int
+    :rtype: List[int]
+    """
+    low = 0
+    high = len(nums) - 1
+    while low <= high:
+        mid = low + (high - low) // 2
+        if target < nums[mid]:
+            high = mid - 1
+        elif target > nums[mid]:
+            low = mid + 1
+        else:
+            break
+
+    for j in range(len(nums) - 1, -1, -1):
+        if nums[j] == target:
+            return [mid, j]
+
+    return [-1, -1]
diff --git a/search/search_rotate.py b/search/search_rotate.py
new file mode 100644
index 0000000..ade0270
--- /dev/null
+++ b/search/search_rotate.py
@@ -0,0 +1,78 @@
+"""
+Search in Rotated Sorted Array
+Suppose an array sorted in ascending order is rotated at some pivot unknown
+to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
+
+You are given a target value to search. If found in the array return its index,
+otherwise return -1.
+
+Your algorithm's runtime complexity must be in the order of O(log n).
+---------------------------------------------------------------------------------
+Explanation algorithm:
+
+In classic binary search, we compare val with the midpoint to figure out if
+val belongs on the low or the high side. The complication here is that the
+array is rotated and may have an inflection point. Consider, for example:
+
+Array1: [10, 15, 20, 0, 5]
+Array2: [50, 5, 20, 30, 40]
+
+Note that both arrays have a midpoint of 20, but 5 appears on the left side of
+one and on the right side of the other. Therefore, comparing val with the
+midpoint is insufficient.
+
+However, if we look a bit deeper, we can see that one half of the array must be
+ordered normally(increasing order). We can therefore look at the normally ordered
+half to determine whether we should search the low or hight side.
+
+For example, if we are searching for 5 in Array1, we can look at the left element (10)
+and middle element (20). Since 10 < 20, the left half must be ordered normally. And, since 5
+is not between those, we know that we must search the right half
+
+In array2, we can see that since 50 > 20, the right half must be ordered normally. We turn to
+the middle 20, and right 40 element to check if 5 would fall between them. The value 5 would not
+Therefore, we search the left half.
+
+There are 2 possible solution: iterative and recursion.
+Recursion helps you understand better the above algorithm explanation
+"""
+def search_rotate(array, val):
+    if not array:
+        return -1
+
+    low, high = 0, len(array) - 1
+    while low <= high:
+        mid = (low + high) // 2
+        if val == array[mid]:
+            return mid
+
+        if array[low] <= array[mid]:
+            if array[low] <= val <= array[mid]:
+                high = mid - 1
+            else:
+                low = mid + 1
+        else:
+            if array[mid] <= val <= array[high]:
+                low = mid + 1
+            else:
+                high = mid - 1
+
+    return -1
+
+# Recursion technique
+def search_rotate_recur(array, low, high, val):
+    if low >= high:
+        return -1
+    mid = (low + high) // 2
+    if val == array[mid]:       # found element
+        return mid
+    if array[low] <= array[mid]:
+        if array[low] <= val <= array[mid]:
+            return search_rotate_recur(array, low, mid - 1, val)    # Search left
+        else:
+            return search_rotate_recur(array, mid + 1, high, val)   # Search right
+    else:
+        if array[mid] <= val <= array[high]:
+            return search_rotate_recur(array, mid + 1, high, val)   # Search right
+        else:
+            return search_rotate_recur(array, low, mid - 1, val)    # Search left
diff --git a/search/two_sum.py b/search/two_sum.py
new file mode 100644
index 0000000..4251e53
--- /dev/null
+++ b/search/two_sum.py
@@ -0,0 +1,51 @@
+"""
+Given an array of integers that is already sorted in ascending order, find two
+numbers such that they add up to a specific target number. The function two_sum
+should return indices of the two numbers such that they add up to the target,
+where index1 must be less than index2. Please note that your returned answers
+(both index1 and index2) are not zero-based.
+You may assume that each input would have exactly one solution and you
+may not use the same element twice.
+
+Input: numbers = [2, 7, 11, 15], target=9
+Output: index1 = 1, index2 = 2
+
+Solution:
+two_sum: using binary search
+two_sum1: using dictionary as a hash table
+two_sum2: using two pointers
+"""
+# Using binary search technique
+def two_sum(numbers, target):
+    for i in range(len(numbers)):
+        second_val = target - numbers[i]
+        low, high = i+1, len(numbers)-1
+        while low <= high:
+            mid = low + (high - low) // 2
+            if second_val == numbers[mid]:
+                return [i + 1, mid + 1]
+            elif second_val > numbers[mid]:
+                low = mid + 1
+            else:
+                high = mid - 1
+
+# Using dictionary as a hash table
+def two_sum1(numbers, target):
+    dic = {}
+    for i, num in enumerate(numbers):
+        if target - num in dic:
+            return [dic[target - num] + 1, i + 1]
+        dic[num] = i
+
+# Using two pointers
+def two_sum2(numbers, target):
+    p1 = 0                      # pointer 1 holds from left of array numbers
+    p2 = len(numbers) - 1       # pointer 2 holds from right of array numbers
+    while p1 < p2:
+        s = numbers[p1] + numbers[p2]
+        if s == target:
+            return [p1 + 1, p2 + 1]
+        elif s > target:
+            p2 = p2 - 1
+        else:
+            p1 = p1 + 1
diff --git a/strings/delete_reoccurring.py b/strings/delete_reoccurring.py
new file mode 100644
index 0000000..131a953
--- /dev/null
+++ b/strings/delete_reoccurring.py
@@ -0,0 +1,19 @@
+"""
+QUESTION: Given a string as your input, delete any reoccurring 
+character, and return the new string.
+
+This is a Google warmup interview question that was asked duirng phone screening
+at my university. 
+"""
+
+# time complexity O(n)
+def delete_reoccurring_characters(string):
+    seen_characters = set()
+    output_string = ''
+    for char in string:
+        if char not in seen_characters:
+            seen_characters.add(char)
+            output_string += char
+    return output_string
+
+    
\ No newline at end of file
diff --git a/strings/validate_coordinates.py b/strings/validate_coordinates.py
new file mode 100644
index 0000000..8ae2dfb
--- /dev/null
+++ b/strings/validate_coordinates.py
@@ -0,0 +1,67 @@
+""""
+Create a function that will validate if given parameters are valid geographical coordinates.
+Valid coordinates look like the following: "23.32353342, -32.543534534". The return value should be either true or false.
+Latitude (which is first float) can be between 0 and 90, positive or negative. Longitude (which is second float) can be between 0 and 180, positive or negative.
+Coordinates can only contain digits, or one of the following symbols (including space after comma) -, .
+There should be no space between the minus "-" sign and the digit after it.
+
+Here are some valid coordinates:
+-23, 25
+43.91343345, 143
+4, -3
+
+And some invalid ones:
+23.234, - 23.4234
+N23.43345, E32.6457
+6.325624, 43.34345.345
+0, 1,2
+
+"""
+# I'll be adding my attempt as well as my friend's solution (took us ~ 1 hour)
+
+# my attempt
+import re
+def is_valid_coordinates_0(coordinates):
+    for char in coordinates:
+        if not (char.isdigit() or char in ['-', '.', ',', ' ']):
+            return False
+    l = coordinates.split(", ")
+    if len(l) != 2:
+        return False
+    print(l)
+    try:
+        latitude = float(l[0])
+        longitude = float(l[1])
+    except:
+        return False
+    print(latitude, longitude)
+    return -90 <= latitude <= 90 and -180 <= longitude <= 180
+
+# friends solutions
+def is_valid_coordinates_1(coordinates):
+    try:
+        lat, lng = [abs(float(c)) for c in coordinates.split(',') if 'e' not in c]
+    except ValueError:
+        return False
+
+    return lat <= 90 and lng <= 180
+
+# using regular expression
+def is_valid_coordinates_regular_expression(coordinates):
+    return bool(re.match("-?(\d|[1-8]\d|90)\.?\d*, -?(\d|[1-9]\d|1[0-7]\d|180)\.?\d*$", coordinates))  
+
+import unittest
+class TestSuite(unittest.TestCase):
+	def test_valid(self):
+		valid_coordinates = ["-23, 25","4, -3","90, 180","-90, -180"]
+		for coordinate in valid_coordinates:
+			self.assertTrue(is_valid_coordinates_0(coordinate))
+
+	def test_invalid(self):
+		invalid_coordinates = ["23.234, - 23.4234","99.234, 12.324","6.325624, 43.34345.345","0, 1,2","23.245, 1e1"]
+		for coordinate in invalid_coordinates:
+			self.assertFalse(is_valid_coordinates_0(coordinate))
+
+
+if __name__ == "__main__":
+    unittest.main()  


Test patch:
diff --git a/search/test_search.py b/search/test_search.py
new file mode 100644
index 0000000..851f8a6
--- /dev/null
+++ b/search/test_search.py
@@ -0,0 +1,91 @@
+from binary_search import binary_search, binary_search_recur
+from first_occurance import first_occurance
+from last_occurance import last_occurance
+from search_insert import search_insert
+from two_sum import two_sum, two_sum1, two_sum2
+from search_range import search_range
+from find_min_rotate import find_min_rotate, find_min_rotate_recur
+from search_rotate import search_rotate, search_rotate_recur
+
+import unittest
+
+class TestSuite(unittest.TestCase):
+
+    def test_first_occurance(self):
+        def helper(array, query):
+            idx = array.index(query) if query in array else None
+            return idx
+        array = [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
+        self.assertEqual(first_occurance(array, 1), helper(array, 1))
+        self.assertEqual(first_occurance(array, 3), helper(array, 3))
+        self.assertEqual(first_occurance(array, 5), helper(array, 5))
+        self.assertEqual(first_occurance(array, 6), helper(array, 6))
+        self.assertEqual(first_occurance(array, 7), helper(array, 7))
+        self.assertEqual(first_occurance(array, -1), helper(array, -1))
+
+    def test_binary_search(self):
+        array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6]
+        self.assertEqual(10, binary_search(array, 5))
+        self.assertEqual(11, binary_search(array, 6))
+        self.assertEqual(None, binary_search(array, 7))
+        self.assertEqual(None, binary_search(array, -1))
+        # Test binary_search_recur
+        self.assertEqual(10, binary_search_recur(array, 0, 11, 5))
+        self.assertEqual(11, binary_search_recur(array, 0, 11, 6))
+        self.assertEqual(-1, binary_search_recur(array, 0, 11, 7))
+        self.assertEqual(-1, binary_search_recur(array, 0, 11, -1))
+
+    def test_last_occurance(self):
+        array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
+        self.assertEqual(5, last_occurance(array, 3))
+        self.assertEqual(10, last_occurance(array, 5))
+        self.assertEqual(None, last_occurance(array, 7))
+        self.assertEqual(0, last_occurance(array, 1))
+        self.assertEqual(13, last_occurance(array, 6))
+
+    def test_search_insert(self):
+        array = [1,3,5,6]
+        self.assertEqual(2, search_insert(array, 5))
+        self.assertEqual(1, search_insert(array, 2))
+        self.assertEqual(4, search_insert(array, 7))
+        self.assertEqual(0, search_insert(array, 0))
+
+    def test_two_sum(self):
+        array = [2, 7, 11, 15]
+        # test two_sum
+        self.assertEqual([1, 2], two_sum(array, 9))
+        self.assertEqual([2, 4], two_sum(array, 22))
+        # test two_sum1
+        self.assertEqual([1, 2], two_sum1(array, 9))
+        self.assertEqual([2, 4], two_sum1(array, 22))
+        # test two_sum2
+        self.assertEqual([1, 2], two_sum2(array, 9))
+        self.assertEqual([2, 4], two_sum2(array, 22))
+
+    def test_search_range(self):
+        array = [5, 7, 7, 8, 8, 8, 10]
+        self.assertEqual([3, 5], search_range(array, 8))
+        self.assertEqual([1, 2], search_range(array, 7))
+        self.assertEqual([-1, -1], search_range(array, 11))
+
+    def test_find_min_rotate(self):
+        array = [4, 5, 6, 7, 0, 1, 2]
+        self.assertEqual(0, find_min_rotate(array))
+        array = [10, 20, -1, 0, 1, 2, 3, 4, 5]
+        self.assertEqual(-1, find_min_rotate(array))
+        # Test find min using recursion
+        array = [4, 5, 6, 7, 0, 1, 2]
+        self.assertEqual(0, find_min_rotate_recur(array, 0, 6))
+        array = [10, 20, -1, 0, 1, 2, 3, 4, 5]
+        self.assertEqual(-1, find_min_rotate_recur(array, 0, 8))
+
+    def test_search_rotate(self):
+        array = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]
+        self.assertEqual(8, search_rotate(array, 5))
+        self.assertEqual(-1, search_rotate(array, 9))
+        self.assertEqual(8, search_rotate_recur(array, 0, 11, 5))
+        self.assertEqual(-1, search_rotate_recur(array, 0, 11, 9))
+
+if __name__ == '__main__':
+
+    unittest.main()