about summary refs log tree commit diff
path: root/scratch/deepmind
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-02-26T16·03+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-03-01T22·32+0000
commitd2aa66a5b1857aa9553117ee418d089983898e65 (patch)
tree30d858fc971097962437b7ec84d6b9295de83374 /scratch/deepmind
parente4cdb5daed33a290e41468f0d7b5ebf458379fa4 (diff)
Solve InterviewCake's top-scores
Using a counting sort to sort a list of values in linear time.
Diffstat (limited to 'scratch/deepmind')
-rw-r--r--scratch/deepmind/part_two/todo.org2
-rw-r--r--scratch/deepmind/part_two/top-scores.py47
2 files changed, 48 insertions, 1 deletions
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index 3562dbe5be55..72b0e99a4253 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -8,7 +8,7 @@
 ** DONE Inflight Entertainment
 ** DONE Permutation Palindrome
 ** DONE Word Cloud Data
-** TODO Top Scores
+** DONE Top Scores
 * Greedy Algorithms
 ** TODO Apple Stocks
 ** TODO Highest Product of 3
diff --git a/scratch/deepmind/part_two/top-scores.py b/scratch/deepmind/part_two/top-scores.py
new file mode 100644
index 000000000000..0ac349c1f880
--- /dev/null
+++ b/scratch/deepmind/part_two/top-scores.py
@@ -0,0 +1,47 @@
+import unittest
+
+
+def sort_scores(xs, highest_possible_score):
+    result = []
+    buckets = [0] * highest_possible_score
+
+    for x in xs:
+        buckets[x - 1] += 1
+
+    for i in range(highest_possible_score - 1, -1, -1):
+        if buckets[i] > 0:
+            for _ in range(buckets[i]):
+                result.append(i + 1)
+
+    return result
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_no_scores(self):
+        actual = sort_scores([], 100)
+        expected = []
+        self.assertEqual(actual, expected)
+
+    def test_one_score(self):
+        actual = sort_scores([55], 100)
+        expected = [55]
+        self.assertEqual(actual, expected)
+
+    def test_two_scores(self):
+        actual = sort_scores([30, 60], 100)
+        expected = [60, 30]
+        self.assertEqual(actual, expected)
+
+    def test_many_scores(self):
+        actual = sort_scores([37, 89, 41, 65, 91, 53], 100)
+        expected = [91, 89, 65, 53, 41, 37]
+        self.assertEqual(actual, expected)
+
+    def test_repeated_scores(self):
+        actual = sort_scores([20, 10, 30, 30, 10, 20], 100)
+        expected = [30, 30, 20, 20, 10, 10]
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)