From 93d654df779c580e1755e66078975838b6845904 Mon Sep 17 00:00:00 2001 From: William Carroll Date: Mon, 24 Feb 2020 16:24:16 +0000 Subject: Solve InterviewCake permutation-palindrome problem Write a predicate to test whether any permutation of an input string is a palindrome. --- .../deepmind/part_two/permutation-palindrome.py | 37 ++++++++++++++++++++++ scratch/deepmind/part_two/todo.org | 2 +- 2 files changed, 38 insertions(+), 1 deletion(-) create mode 100644 scratch/deepmind/part_two/permutation-palindrome.py (limited to 'scratch') diff --git a/scratch/deepmind/part_two/permutation-palindrome.py b/scratch/deepmind/part_two/permutation-palindrome.py new file mode 100644 index 000000000000..730b4bfdc873 --- /dev/null +++ b/scratch/deepmind/part_two/permutation-palindrome.py @@ -0,0 +1,37 @@ +import unittest +from collections import Counter + + +def has_palindrome_permutation(xs): + vs = Counter(xs).values() + return len([v for v in vs if v % 2 == 1]) in {0, 1} + + +# Tests +class Test(unittest.TestCase): + def test_permutation_with_odd_number_of_chars(self): + result = has_palindrome_permutation('aabcbcd') + self.assertTrue(result) + + def test_permutation_with_even_number_of_chars(self): + result = has_palindrome_permutation('aabccbdd') + self.assertTrue(result) + + def test_no_permutation_with_odd_number_of_chars(self): + result = has_palindrome_permutation('aabcd') + self.assertFalse(result) + + def test_no_permutation_with_even_number_of_chars(self): + result = has_palindrome_permutation('aabbcd') + self.assertFalse(result) + + def test_empty_string(self): + result = has_palindrome_permutation('') + self.assertTrue(result) + + def test_one_character_string(self): + result = has_palindrome_permutation('a') + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org index a51ee9c59017..a710e05b83b8 100644 --- a/scratch/deepmind/part_two/todo.org +++ b/scratch/deepmind/part_two/todo.org @@ -6,7 +6,7 @@ ** DONE Cafe Order Checker * Hashing and hash tables ** DONE Inflight Entertainment -** TODO Permutation Palindrome +** DONE Permutation Palindrome ** TODO Word Cloud Data ** TODO Top Scores * Greedy Algorithms -- cgit 1.4.1