From d2aa66a5b1857aa9553117ee418d089983898e65 Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Wed, 26 Feb 2020 16:03:50 +0000
Subject: Solve InterviewCake's top-scores

Using a counting sort to sort a list of values in linear time.
---
 scratch/deepmind/part_two/todo.org      |  2 +-
 scratch/deepmind/part_two/top-scores.py | 47 +++++++++++++++++++++++++++++++++
 2 files changed, 48 insertions(+), 1 deletion(-)
 create mode 100644 scratch/deepmind/part_two/top-scores.py

(limited to 'scratch')

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)
-- 
cgit 1.4.1