Solve InterviewCake's reverse-words

Wrote a function to reverse the words in a list of characters. A word is a
space-delimited strings of characters.

The trick here is to first reverse the entire string and then reverse each word
individually.

2 files changed, 64 insertions, 1 deletions

diff --git a/scratch/deepmind/part_two/reverse-words.py b/scratch/deepmind/part_two/reverse-words.py
new file mode 100644
index 000000000000..d433ac594bcc
--- /dev/null
+++ b/scratch/deepmind/part_two/reverse-words.py
@@ -0,0 +1,63 @@
+import unittest
+
+
+def reverse(xs, i, j):
+    """Reverse array of characters, xs, in-place."""
+    while i < j:
+        xs[i], xs[j] = xs[j], xs[i]
+        i += 1
+        j -= 1
+
+
+def reverse_words(xs):
+    reverse(xs, 0, len(xs) - 1)
+    i = 0
+    j = i
+    while j < len(xs):
+        while j < len(xs) and xs[j] != ' ':
+            j += 1
+        reverse(xs, i, j - 1)
+        j += 1
+        i = j
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_one_word(self):
+        message = list('vault')
+        reverse_words(message)
+        expected = list('vault')
+        self.assertEqual(message, expected)
+
+    def test_two_words(self):
+        message = list('thief cake')
+        reverse_words(message)
+        expected = list('cake thief')
+        self.assertEqual(message, expected)
+
+    def test_three_words(self):
+        message = list('one another get')
+        reverse_words(message)
+        expected = list('get another one')
+        self.assertEqual(message, expected)
+
+    def test_multiple_words_same_length(self):
+        message = list('rat the ate cat the')
+        reverse_words(message)
+        expected = list('the cat ate the rat')
+        self.assertEqual(message, expected)
+
+    def test_multiple_words_different_lengths(self):
+        message = list('yummy is cake bundt chocolate')
+        reverse_words(message)
+        expected = list('chocolate bundt cake is yummy')
+        self.assertEqual(message, expected)
+
+    def test_empty_string(self):
+        message = list('')
+        reverse_words(message)
+        expected = list('')
+        self.assertEqual(message, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index a3a3df6ef1fe..91fd3fbf2c1c 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -1,7 +1,7 @@
 * Array and string manipulation
 ** DONE Merging Meeting Times
 ** DONE Reverse String in Place
-** TODO Reverse Words
+** DONE Reverse Words
 ** TODO Merge Sorted Arrays
 ** TODO Cafe Order Checker
 * Hashing and hash tables