Complete practice algorithms from InterviewCake.com

While I've done these algorithms before, I'm preparing for an on-site with
DeepMind, so I created a subdirectory called deepmind where I'm storing my
second attempts at these problems. The idea of storing them in a second
directory is to remove the urge to check my existing solutions that also exist
in this repository.

1 files changed, 59 insertions, 0 deletions

diff --git a/deepmind/merging-ranges.py b/deepmind/merging-ranges.py
new file mode 100644
index 000000000000..23b40793b8f1
--- /dev/null
+++ b/deepmind/merging-ranges.py
@@ -0,0 +1,59 @@
+import unittest
+
+
+def merge_ranges(xs):
+    xs.sort()
+    result = [xs[0]]
+    for curr in xs[1:]:
+        a, z = result[-1]
+        if z >= curr[0]:
+            result[-1] = (a, max(z, curr[1]))
+        else:
+            result.append(curr)
+    return result
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_meetings_overlap(self):
+        actual = merge_ranges([(1, 3), (2, 4)])
+        expected = [(1, 4)]
+        self.assertEqual(actual, expected)
+
+    def test_meetings_touch(self):
+        actual = merge_ranges([(5, 6), (6, 8)])
+        expected = [(5, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_meeting_contains_other_meeting(self):
+        actual = merge_ranges([(1, 8), (2, 5)])
+        expected = [(1, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_meetings_stay_separate(self):
+        actual = merge_ranges([(1, 3), (4, 8)])
+        expected = [(1, 3), (4, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_multiple_merged_meetings(self):
+        actual = merge_ranges([(1, 4), (2, 5), (5, 8)])
+        expected = [(1, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_meetings_not_sorted(self):
+        actual = merge_ranges([(5, 8), (1, 4), (6, 8)])
+        expected = [(1, 4), (5, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_one_long_meeting_contains_smaller_meetings(self):
+        actual = merge_ranges([(1, 10), (2, 5), (6, 8), (9, 10), (10, 12)])
+        expected = [(1, 12)]
+        self.assertEqual(actual, expected)
+
+    def test_sample_input(self):
+        actual = merge_ranges([(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)])
+        expected = [(0, 1), (3, 8), (9, 12)]
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)