Solve InterviewCake's top-scores

Using a counting sort to sort a list of values in linear time.

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)