about summary refs log tree commit diff
path: root/deepmind/merging-ranges.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-01-18T17·04+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-01-18T17·04+0000
commit34dc3e05c8a42c47023776d52ff33f100f2d310f (patch)
treed1c15b350e924b5c032ef5320454e474a827efe9 /deepmind/merging-ranges.py
parenta62553f7b7f51c735e12dc935bec57dec8eac25e (diff)
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.
Diffstat (limited to 'deepmind/merging-ranges.py')
-rw-r--r--deepmind/merging-ranges.py59
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)