diff options
author | William Carroll <wpcarro@gmail.com> | 2020-02-06T16·56+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-02-06T16·56+0000 |
commit | 5df3bb4e40c039b1736627be36515d18a38638b6 (patch) | |
tree | 5fa0ab24101d4a6cbad03be49e5dab40477e2377 /deepmind/part_one/find-rotation-point.py | |
parent | b4dd290745ae314f831880be5a3335155d25951f (diff) |
Partition deepmind directory into two parts
Since I did not pass my one-site interview with DM, but I have been invited to attempt again, I decided to partition this directory into two parts: 1. part_one: Hosting the exercises that I completed before my first attempt at earning the job. 2. part_two: Hosting the exercise that I will complete before my second attempt at earning the job.
Diffstat (limited to 'deepmind/part_one/find-rotation-point.py')
-rw-r--r-- | deepmind/part_one/find-rotation-point.py | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/deepmind/part_one/find-rotation-point.py b/deepmind/part_one/find-rotation-point.py new file mode 100644 index 000000000000..5c21d5167ce9 --- /dev/null +++ b/deepmind/part_one/find-rotation-point.py @@ -0,0 +1,55 @@ +import unittest +from math import floor + + +def midpoint(a, b): + return a + floor((b - a) / 2) + + +def do_find_rotation_point(a, b, xs): + i = midpoint(a, b) + count = b - a + 1 + + if count == 2: + if xs[a] > xs[b]: + return b + else: + return -1 + + if i in {a, b}: + return i + + if xs[a] < xs[i]: + return do_find_rotation_point(i, b, xs) + else: + return do_find_rotation_point(a, i, xs) + + +def find_rotation_point(xs): + return do_find_rotation_point(0, len(xs) - 1, xs) + + +# Tests +class Test(unittest.TestCase): + def test_small_list(self): + actual = find_rotation_point(['cape', 'cake']) + expected = 1 + self.assertEqual(actual, expected) + + def test_medium_list(self): + actual = find_rotation_point( + ['grape', 'orange', 'plum', 'radish', 'apple']) + expected = 4 + self.assertEqual(actual, expected) + + def test_large_list(self): + actual = find_rotation_point([ + 'ptolemaic', 'retrograde', 'supplant', 'undulate', 'xenoepist', + 'asymptote', 'babka', 'banoffee', 'engender', 'karpatka', + 'othellolagkage' + ]) + expected = 5 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) |