Repository: keon/algorithms
Pull request #378 (2018-07-23 04:07:26)

PR to add some problem
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [x] **If creating a new file :**
  - [x] added links to it in the README files ?
  - [x] included tests with it ?
  - [x] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


coveralls: ## Pull Request Test Coverage Report for [Build 686](https://coveralls.io/builds/18109020)

* **39** of **43**   **(90.7%)**  changed or added relevant lines in **2** files are covered.
* **2** unchanged lines in **1** file lost coverage.
* Overall coverage increased (+**0.1%**) to **71.455%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/strings/longest_common_prefix.py](https://coveralls.io/builds/18109020/source?filename=algorithms%2Fstrings%2Flongest_common_prefix.py#L34) | 31 | 35 | 88.57%
<!-- | **Total:** | **39** | **43** | **90.7%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/sort/top_sort.py](https://coveralls.io/builds/18109020/source?filename=algorithms%2Fsort%2Ftop_sort.py#L41) | 2 | 90.38% |
<!-- | **Total:** | **2** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/18109020/badge)](https://coveralls.io/builds/18109020) |
| :-- | --: |
| Change from base [Build 685](https://coveralls.io/builds/18059853): |  0.1% |
| Covered Lines: | 3890 |
| Relevant Lines: | 5444 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index c736a42..7bb2689 100644
--- a/README.md
+++ b/README.md
@@ -295,6 +295,10 @@ If you want to uninstall algorithms, it is as simple as:
     - [count_binary_substring](algorithms/strings/count_binary_substring.py)
     - [repeat_string](algorithms/strings/repeat_string.py)
     - [min_distance](algorithms/strings/min_distance.py)
+    - [longest_common_prefix](algorithms/strings/longest_common_prefix.py)
+    - [rotate](algorithms/strings/rotate.py)
+    - [first_unique_char](algorithms/strings/first_unique_char.py)
+    - [repeat_substring](algorithms/strings/repeat_substring.py)     
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
@@ -350,6 +354,8 @@ If you want to uninstall algorithms, it is as simple as:
         - [simplify_path](algorithms/unix/path/simplify_path.py)
 - [union-find](algorithms/union-find)
     - [count_islands](algorithms/union-find/count_islands.py)
+- [machine-learning](algorithms/machine-learning)
+    - [nearest neighbor classification](algorithms/machine-learning/nearest_neighbor.py)
 
 ## Contributors
 The repo is maintained by
diff --git a/algorithms/map/__init__.py b/algorithms/map/__init__.py
new file mode 100644
index 0000000..a663c8a
--- /dev/null
+++ b/algorithms/map/__init__.py
@@ -0,0 +1,2 @@
+from .hashtable import *
+from .separate_chaining_hashtable import *
diff --git a/algorithms/map/hashtable.py b/algorithms/map/hashtable.py
index 1c98ee2..f579c0b 100644
--- a/algorithms/map/hashtable.py
+++ b/algorithms/map/hashtable.py
@@ -1,6 +1,3 @@
-from unittest import TestCase
-import unittest
-
 class HashTable(object):
     """
     HashMap Data Type
@@ -120,93 +117,3 @@ class ResizableHashTable(HashTable):
         for key, value in zip(keys, values):
             if key is not self._empty and key is not self._deleted:
                 self.put(key, value)
-
-
-class TestHashTable(TestCase):
-    def test_one_entry(self):
-        m = HashTable(10)
-        m.put(1, '1')
-        self.assertEqual('1', m.get(1))
-
-    def test_add_entry_bigger_than_table_size(self):
-        m = HashTable(10)
-        m.put(11, '1')
-        self.assertEqual('1', m.get(11))
-
-    def test_get_none_if_key_missing_and_hash_collision(self):
-        m = HashTable(10)
-        m.put(1, '1')
-        self.assertEqual(None, m.get(11))
-
-    def test_two_entries_with_same_hash(self):
-        m = HashTable(10)
-        m.put(1, '1')
-        m.put(11, '11')
-        self.assertEqual('1', m.get(1))
-        self.assertEqual('11', m.get(11))
-
-    def test_get_on_full_table_does_halts(self):
-        # and does not search forever
-        m = HashTable(10)
-        for i in range(10, 20):
-            m.put(i, i)
-        self.assertEqual(None, m.get(1))
-
-    def test_delete_key(self):
-        m = HashTable(10)
-        for i in range(5):
-            m.put(i, i**2)
-        m.del_(1)
-        self.assertEqual(None, m.get(1))
-        self.assertEqual(4,m.get(2))
-
-    def test_delete_key_and_reassign(self):
-        m = HashTable(10)
-        m.put(1, 1)
-        del m[1]
-        m.put(1, 2)
-        self.assertEqual(2, m.get(1))
-
-    def test_assigning_to_full_table_throws_error(self):
-        m = HashTable(3)
-        m.put(1, 1)
-        m.put(2, 2)
-        m.put(3, 3)
-        with self.assertRaises(ValueError):
-            m.put(4, 4)
-
-    def test_len_trivial(self):
-        m = HashTable(10)
-        self.assertEqual(0, len(m))
-        for i in range(10):
-            m.put(i, i)
-            self.assertEqual(i + 1, len(m))
-
-    def test_len_after_deletions(self):
-        m = HashTable(10)
-        m.put(1, 1)
-        self.assertEqual(1, len(m))
-        m.del_(1)
-        self.assertEqual(0, len(m))
-        m.put(11, 42)
-        self.assertEqual(1, len(m))
-
-    def test_resizable_hash_table(self):
-        m = ResizableHashTable()
-        self.assertEqual(ResizableHashTable.MIN_SIZE, m.size)
-        for i in range(ResizableHashTable.MIN_SIZE):
-            m.put(i, 'foo')
-        self.assertEqual(ResizableHashTable.MIN_SIZE * 2, m.size)
-        self.assertEqual('foo', m.get(1))
-        self.assertEqual('foo', m.get(3))
-        self.assertEqual('foo', m.get(ResizableHashTable.MIN_SIZE - 1))
-        
-    def test_fill_up_the_limit(self):
-        m = HashTable(10)
-        for i in range(10):
-            m.put(i,i**2)
-        for i in range(10):
-            self.assertEqual(i**2,m.get(i))
-
-if __name__ == "__main__":
-    unittest.main()
\ No newline at end of file
diff --git a/algorithms/map/separate_chaining_hashtable.py b/algorithms/map/separate_chaining_hashtable.py
index 5feb50a..fecb251 100644
--- a/algorithms/map/separate_chaining_hashtable.py
+++ b/algorithms/map/separate_chaining_hashtable.py
@@ -82,62 +82,3 @@ class SeparateChainingHashTable(object):
 
     def __setitem__(self, key, value):
         self.put(key, value)
-
-
-class TestSeparateChainingHashTable(unittest.TestCase):
-    def test_one_entry(self):
-        m = SeparateChainingHashTable(10)
-        m.put(1, '1')
-        self.assertEqual('1', m.get(1))
-
-    def test_two_entries_with_same_hash(self):
-        m = SeparateChainingHashTable(10)
-        m.put(1, '1')
-        m.put(11, '11')
-        self.assertEqual('1', m.get(1))
-        self.assertEqual('11', m.get(11))
-
-    def test_len_trivial(self):
-        m = SeparateChainingHashTable(10)
-        self.assertEqual(0, len(m))
-        for i in range(10):
-            m.put(i, i)
-            self.assertEqual(i + 1, len(m))
-
-    def test_len_after_deletions(self):
-        m = SeparateChainingHashTable(10)
-        m.put(1, 1)
-        self.assertEqual(1, len(m))
-        m.del_(1)
-        self.assertEqual(0, len(m))
-        m.put(11, 42)
-        self.assertEqual(1, len(m))
-
-    def test_delete_key(self):
-        m = SeparateChainingHashTable(10)
-        for i in range(5):
-            m.put(i, i**2)
-        m.del_(1)
-        self.assertEqual(None, m.get(1))
-        self.assertEqual(4, m.get(2))
-
-    def test_delete_key_and_reassign(self):
-        m = SeparateChainingHashTable(10)
-        m.put(1, 1)
-        del m[1]
-        m.put(1, 2)
-        self.assertEqual(2, m.get(1))
-
-    def test_add_entry_bigger_than_table_size(self):
-        m = SeparateChainingHashTable(10)
-        m.put(11, '1')
-        self.assertEqual('1', m.get(11))
-
-    def test_get_none_if_key_missing_and_hash_collision(self):
-        m = SeparateChainingHashTable(10)
-        m.put(1, '1')
-        self.assertEqual(None, m.get(11))
-
-
-if __name__ == '__main__':
-    unittest.main()
diff --git a/algorithms/ml/nearest_neighbor.py b/algorithms/ml/nearest_neighbor.py
new file mode 100644
index 0000000..d0fabab
--- /dev/null
+++ b/algorithms/ml/nearest_neighbor.py
@@ -0,0 +1,41 @@
+import math
+
+def distance(x,y):
+    """[summary]
+    HELPER-FUNCTION
+    calculates the (eulidean) distance between vector x and y.
+
+    Arguments:
+        x {[tuple]} -- [vector]
+        y {[tuple]} -- [vector]
+    """
+    assert len(x) == len(y), "The vector must have same length"
+    result = ()
+    sum = 0
+    for i in range(len(x)):
+        result += (x[i] -y[i],)
+    for component in result:
+        sum += component**2
+    return math.sqrt(sum)
+
+
+def nearest_neighbor(x, tSet):
+    """[summary]
+    Implements the nearest neighbor algorithm
+
+    Arguments:
+        x {[tupel]} -- [vector]
+        tSet {[dict]} -- [training set]
+
+    Returns:
+        [type] -- [result of the AND-function]
+    """
+    assert isinstance(x, tuple) and isinstance(tSet, dict)
+    current_key = ()
+    min_d = float('inf')
+    for key in tSet:
+        d = distance(x, key)
+        if d < min_d:
+            min_d = d
+            current_key = key
+    return tSet[current_key]
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
index d7ae4b6..98306f6 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -30,3 +30,7 @@ from .count_binary_substring import *
 from .repeat_string import *
 from .text_justification import *
 from .min_distance import *
+from .longest_common_prefix import *
+from .rotate import *
+from .first_unique_char import *
+from .repeat_substring import *
diff --git a/algorithms/strings/first_unique_char.py b/algorithms/strings/first_unique_char.py
new file mode 100644
index 0000000..44ba05e
--- /dev/null
+++ b/algorithms/strings/first_unique_char.py
@@ -0,0 +1,27 @@
+"""
+Given a string, find the first non-repeating character in it and return it's
+index. If it doesn't exist, return -1.
+
+For example:
+s = "leetcode"
+return 0.
+
+s = "loveleetcode",
+return 2.
+
+Reference: https://leetcode.com/problems/first-unique-character-in-a-string/description/
+"""
+def first_unique_char(s):
+    """
+    :type s: str
+    :rtype: int
+    """
+    if (len(s) == 1):
+        return 0
+    ban = []
+    for i in range(len(s)):
+        if all(s[i] != s[k] for k in range(i + 1, len(s))) == True and s[i] not in ban:
+            return i
+        else:
+            ban.append(s[i])
+    return -1   
diff --git a/algorithms/strings/is_rotated.py b/algorithms/strings/is_rotated.py
index a68d62d..a827fb4 100644
--- a/algorithms/strings/is_rotated.py
+++ b/algorithms/strings/is_rotated.py
@@ -6,10 +6,26 @@ is_rotated("hello", "helol") returns False
 
 accepts two strings
 returns bool
+Reference: https://leetcode.com/problems/rotate-string/description/
 """
 
 def is_rotated(s1, s2):
     if len(s1) == len(s2):
         return s2 in s1 + s1
     else:
-        return False
\ No newline at end of file
+        return False
+
+"""
+Another solution: brutal force
+Complexity: O(N^2)
+"""
+def is_rotated_v1(s1, s2):
+    if len(s1) != len(s2):
+        return False
+    if len(s1) == 0:
+        return True
+
+    for c in range(len(s1)):
+        if all(s1[(c + i) % len(s1)] == s2[i] for i in range(len(s1))):
+            return True
+    return False
diff --git a/algorithms/strings/longest_common_prefix.py b/algorithms/strings/longest_common_prefix.py
new file mode 100644
index 0000000..80facc9
--- /dev/null
+++ b/algorithms/strings/longest_common_prefix.py
@@ -0,0 +1,66 @@
+"""
+Write a function to find the longest common prefix string amongst an array of strings.
+
+If there is no common prefix, return an empty string "".
+
+Example 1:
+Input: ["flower","flow","flight"]
+Output: "fl"
+
+Example 2:
+Input: ["dog","racecar","car"]
+Output: ""
+Explanation: There is no common prefix among the input strings.
+
+Reference: https://leetcode.com/problems/longest-common-prefix/description/
+"""
+
+"""
+First solution: Horizontal scanning
+"""
+def common_prefix(s1, s2):
+    "Return prefix common of 2 strings"
+    if not s1 or not s2:
+        return ""
+    k = 0
+    while s1[k] == s2[k]:
+        k = k + 1
+        if k >= len(s1) or k >= len(s2):
+            return s1[0:k]
+    return s1[0:k]
+
+def longest_common_prefix_v1(strs):
+    if not strs:
+        return ""
+    result = strs[0]
+    for i in range(len(strs)):
+        result = common_prefix(result, strs[i])
+    return result
+
+"""
+Second solution: Vertical scanning
+"""
+def longest_common_prefix_v2(strs):
+    if not strs:
+        return ""
+    for i in range(len(strs[0])):
+        for string in strs[1:]:
+            if i == len(string) or string[i] != strs[0][i]:
+                return strs[0][0:i]
+    return strs[0]
+
+"""
+Third solution: Divide and Conquer
+"""
+def longest_common_prefix_v3(strs):
+    if not strs:
+        return ""
+    return longest_common(strs, 0, len(strs) -1)
+
+def longest_common(strs, left, right):
+    if left == right:
+        return strs[left]
+    mid = (left + right) // 2
+    lcp_left = longest_common(strs, left, mid)
+    lcp_right = longest_common(strs, mid + 1, right)
+    return common_prefix(lcp_left, lcp_right)
diff --git a/algorithms/strings/repeat_substring.py b/algorithms/strings/repeat_substring.py
new file mode 100644
index 0000000..0f26c28
--- /dev/null
+++ b/algorithms/strings/repeat_substring.py
@@ -0,0 +1,25 @@
+"""
+Given a non-empty string check if it can be constructed by taking
+a substring of it and appending multiple copies of the substring together.
+
+For example:
+Input: "abab"
+Output: True
+Explanation: It's the substring "ab" twice.
+
+Input: "aba"
+Output: False
+
+Input: "abcabcabcabc"
+Output: True
+Explanation: It's the substring "abc" four times.
+
+Reference: https://leetcode.com/problems/repeated-substring-pattern/description/
+"""
+def repeat_substring(s):
+    """
+    :type s: str
+    :rtype: bool
+    """
+    str = (s + s)[1:-1]
+    return s in str
diff --git a/algorithms/strings/rotate.py b/algorithms/strings/rotate.py
new file mode 100644
index 0000000..7f713ba
--- /dev/null
+++ b/algorithms/strings/rotate.py
@@ -0,0 +1,18 @@
+"""
+Given a strings s and int k, return a string that rotates k times
+
+For example,
+rotate("hello", 2) return "llohe"
+rotate("hello", 5) return "hello"
+rotate("hello", 6) return "elloh"
+rotate("hello", 7) return "llohe"
+
+accepts two strings
+returns bool
+"""
+def rotate(s, k):
+    double_s = s + s
+    if k <= len(s):
+        return double_s[k:k + len(s)]
+    else:
+        return double_s[k-len(s):k]


Test patch:
diff --git a/tests/test_map.py b/tests/test_map.py
new file mode 100644
index 0000000..5786803
--- /dev/null
+++ b/tests/test_map.py
@@ -0,0 +1,152 @@
+from algorithms.map import (
+    HashTable, ResizableHashTable,
+    Node, SeparateChainingHashTable
+)
+
+import unittest
+
+class TestHashTable(unittest.TestCase):
+    def test_one_entry(self):
+        m = HashTable(10)
+        m.put(1, '1')
+        self.assertEqual('1', m.get(1))
+
+    def test_add_entry_bigger_than_table_size(self):
+        m = HashTable(10)
+        m.put(11, '1')
+        self.assertEqual('1', m.get(11))
+
+    def test_get_none_if_key_missing_and_hash_collision(self):
+        m = HashTable(10)
+        m.put(1, '1')
+        self.assertEqual(None, m.get(11))
+
+    def test_two_entries_with_same_hash(self):
+        m = HashTable(10)
+        m.put(1, '1')
+        m.put(11, '11')
+        self.assertEqual('1', m.get(1))
+        self.assertEqual('11', m.get(11))
+
+    def test_get_on_full_table_does_halts(self):
+        # and does not search forever
+        m = HashTable(10)
+        for i in range(10, 20):
+            m.put(i, i)
+        self.assertEqual(None, m.get(1))
+
+    def test_delete_key(self):
+        m = HashTable(10)
+        for i in range(5):
+            m.put(i, i**2)
+        m.del_(1)
+        self.assertEqual(None, m.get(1))
+        self.assertEqual(4,m.get(2))
+
+    def test_delete_key_and_reassign(self):
+        m = HashTable(10)
+        m.put(1, 1)
+        del m[1]
+        m.put(1, 2)
+        self.assertEqual(2, m.get(1))
+
+    def test_assigning_to_full_table_throws_error(self):
+        m = HashTable(3)
+        m.put(1, 1)
+        m.put(2, 2)
+        m.put(3, 3)
+        with self.assertRaises(ValueError):
+            m.put(4, 4)
+
+    def test_len_trivial(self):
+        m = HashTable(10)
+        self.assertEqual(0, len(m))
+        for i in range(10):
+            m.put(i, i)
+            self.assertEqual(i + 1, len(m))
+
+    def test_len_after_deletions(self):
+        m = HashTable(10)
+        m.put(1, 1)
+        self.assertEqual(1, len(m))
+        m.del_(1)
+        self.assertEqual(0, len(m))
+        m.put(11, 42)
+        self.assertEqual(1, len(m))
+
+    def test_resizable_hash_table(self):
+        m = ResizableHashTable()
+        self.assertEqual(ResizableHashTable.MIN_SIZE, m.size)
+        for i in range(ResizableHashTable.MIN_SIZE):
+            m.put(i, 'foo')
+        self.assertEqual(ResizableHashTable.MIN_SIZE * 2, m.size)
+        self.assertEqual('foo', m.get(1))
+        self.assertEqual('foo', m.get(3))
+        self.assertEqual('foo', m.get(ResizableHashTable.MIN_SIZE - 1))
+
+    def test_fill_up_the_limit(self):
+        m = HashTable(10)
+        for i in range(10):
+            m.put(i,i**2)
+        for i in range(10):
+            self.assertEqual(i**2,m.get(i))
+
+
+class TestSeparateChainingHashTable(unittest.TestCase):
+    def test_one_entry(self):
+        m = SeparateChainingHashTable(10)
+        m.put(1, '1')
+        self.assertEqual('1', m.get(1))
+
+    def test_two_entries_with_same_hash(self):
+        m = SeparateChainingHashTable(10)
+        m.put(1, '1')
+        m.put(11, '11')
+        self.assertEqual('1', m.get(1))
+        self.assertEqual('11', m.get(11))
+
+    def test_len_trivial(self):
+        m = SeparateChainingHashTable(10)
+        self.assertEqual(0, len(m))
+        for i in range(10):
+            m.put(i, i)
+            self.assertEqual(i + 1, len(m))
+
+    def test_len_after_deletions(self):
+        m = SeparateChainingHashTable(10)
+        m.put(1, 1)
+        self.assertEqual(1, len(m))
+        m.del_(1)
+        self.assertEqual(0, len(m))
+        m.put(11, 42)
+        self.assertEqual(1, len(m))
+
+    def test_delete_key(self):
+        m = SeparateChainingHashTable(10)
+        for i in range(5):
+            m.put(i, i**2)
+        m.del_(1)
+        self.assertEqual(None, m.get(1))
+        self.assertEqual(4, m.get(2))
+
+    def test_delete_key_and_reassign(self):
+        m = SeparateChainingHashTable(10)
+        m.put(1, 1)
+        del m[1]
+        m.put(1, 2)
+        self.assertEqual(2, m.get(1))
+
+    def test_add_entry_bigger_than_table_size(self):
+        m = SeparateChainingHashTable(10)
+        m.put(11, '1')
+        self.assertEqual('1', m.get(11))
+
+    def test_get_none_if_key_missing_and_hash_collision(self):
+        m = SeparateChainingHashTable(10)
+        m.put(1, '1')
+        self.assertEqual(None, m.get(11))
+
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/tests/test_ml.py b/tests/test_ml.py
new file mode 100644
index 0000000..61852ec
--- /dev/null
+++ b/tests/test_ml.py
@@ -0,0 +1,31 @@
+from algorithms.ml.nearest_neighbor import (
+    distance,
+    nearest_neighbor
+)
+
+import unittest
+
+class TestML(unittest.TestCase):
+    def setUp(self):
+        # train set for the AND-function
+        self.trainSetAND = {(0,0) : 0, (0,1) :0, (1,0) : 0, (1,1) : 1} 
+
+        # train set for light or dark colors
+        self.trainSetLight = {(11, 98, 237) : 'L', (3, 39, 96) : 'D', (242, 226, 12) : 'L', (99, 93, 4) : 'D',
+        (232, 62, 32) : 'L', (119, 28, 11) : 'D', (25, 214, 47) : 'L', (89, 136, 247) : 'L',
+        (21, 34, 63) : 'D', (237, 99, 120) : 'L', (73, 33, 39) : 'D'}
+    def test_nearest_neighbor(self):
+        # AND-function
+        self.assertEqual(nearest_neighbor((1,1), self.trainSetAND), 1)
+        self.assertEqual(nearest_neighbor((0,1), self.trainSetAND), 0)
+
+        # dark/light color test
+        self.assertEqual(nearest_neighbor((31, 242, 164), self.trainSetLight), 'L')
+        self.assertEqual(nearest_neighbor((13, 94, 64), self.trainSetLight), 'D')
+        self.assertEqual(nearest_neighbor((230, 52, 239), self.trainSetLight), 'L')
+    def test_distance(self):
+        self.assertAlmostEqual(distance((1,2,3), (1,0,-1)), 4.47, 2)
+
+        
+if __name__ == "__main__":
+    unittest.main()
\ No newline at end of file
diff --git a/tests/test_strings.py b/tests/test_strings.py
index 0c77ac1..4474b75 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -9,7 +9,7 @@ from algorithms.strings import (
     int_to_roman,
     is_palindrome, is_palindrome_reverse,
     is_palindrome_two_pointer, is_palindrome_stack,
-    is_rotated,
+    is_rotated, is_rotated_v1,
     license_number,
     make_sentence,
     is_merge_recursive, is_merge_iterative,
@@ -32,7 +32,11 @@ from algorithms.strings import (
     count_binary_substring,
     repeat_string,
     text_justification,
-    min_distance
+    min_distance,
+    longest_common_prefix_v1, longest_common_prefix_v2, longest_common_prefix_v3,
+    rotate,
+    first_unique_char,
+    repeat_substring
 )
 
 import unittest
@@ -201,6 +205,21 @@ class TestIsRotated(unittest.TestCase):
         self.assertFalse(is_rotated("hello", "lloh"))
         self.assertTrue(is_rotated("", ""))
 
+    def test_is_rotated_v1(self):
+        self.assertTrue(is_rotated_v1("hello", "hello"))
+        self.assertTrue(is_rotated_v1("hello", "llohe"))
+        self.assertFalse(is_rotated_v1("hello", "helol"))
+        self.assertFalse(is_rotated_v1("hello", "lloh"))
+        self.assertTrue(is_rotated_v1("", ""))
+
+
+class TestRotated(unittest.TestCase):
+    def test_rotate(self):
+        self.assertEqual("llohe", rotate("hello", 2))
+        self.assertEqual("hello", rotate("hello", 5))
+        self.assertEqual("elloh", rotate("hello", 6))
+        self.assertEqual("llohe", rotate("hello", 7))
+
 
 class TestLicenseNumber(unittest.TestCase):
     """[summary]
@@ -475,6 +494,29 @@ class TestMinDistance(unittest.TestCase):
         self.assertEqual(2, min_distance("sea", "eat"))
         self.assertEqual(6, min_distance("abAlgocrithmf", "Algorithmmd"))
 
+class TestLongestCommonPrefix(unittest.TestCase):
+    def test_longest_common_prefix(self):
+        # Test first solution
+        self.assertEqual("fl", longest_common_prefix_v1(["flower","flow","flight"]))
+        self.assertEqual("", longest_common_prefix_v1(["dog","racecar","car"]))
+        # Test second solution
+        self.assertEqual("fl", longest_common_prefix_v2(["flower","flow","flight"]))
+        self.assertEqual("", longest_common_prefix_v2(["dog","racecar","car"]))
+        # Test third solution
+        self.assertEqual("fl", longest_common_prefix_v3(["flower","flow","flight"]))
+        self.assertEqual("", longest_common_prefix_v3(["dog","racecar","car"]))
+
+class TestFirstUniqueChar(unittest.TestCase):
+    def test_first_unique_char(self):
+        self.assertEqual(0, first_unique_char("leetcode"))
+        self.assertEqual(2, first_unique_char("loveleetcode"))
+
+class TestRepeatSubstring(unittest.TestCase):
+    def test_repeat_substring(self):
+        self.assertTrue(repeat_substring("abab"))
+        self.assertFalse(repeat_substring("aba"))
+        self.assertTrue(repeat_substring("abcabcabcabc"))
+
 
 if __name__ == "__main__":
     unittest.main()