diff options
Diffstat (limited to 'universe/deepmind/kth-to-last.py')
-rw-r--r-- | universe/deepmind/kth-to-last.py | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/universe/deepmind/kth-to-last.py b/universe/deepmind/kth-to-last.py new file mode 100644 index 000000000000..5335e419f7ec --- /dev/null +++ b/universe/deepmind/kth-to-last.py @@ -0,0 +1,64 @@ +import unittest + + +def kth_to_last_node(k, x): + a, b = x, x + + if k == 0: + raise Exception('Value of 0 for k is not supported') + + for _ in range(k - 1): + if not a.next: + raise Exception('Value of {} for k is too large'.format(k)) + a = a.next + + while a.next: + a, b = a.next, b.next + return b + + +class Test(unittest.TestCase): + class LinkedListNode(object): + def __init__(self, value, next=None): + self.value = value + self.next = next + + def get_values(self): + node = self + values = [] + while node is not None: + values.append(node.value) + node = node.next + return values + + def setUp(self): + self.fourth = Test.LinkedListNode(4) + self.third = Test.LinkedListNode(3, self.fourth) + self.second = Test.LinkedListNode(2, self.third) + self.first = Test.LinkedListNode(1, self.second) + + def test_first_to_last_node(self): + actual = kth_to_last_node(1, self.first) + expected = self.fourth + self.assertEqual(actual, expected) + + def test_second_to_last_node(self): + actual = kth_to_last_node(2, self.first) + expected = self.third + self.assertEqual(actual, expected) + + def test_first_node(self): + actual = kth_to_last_node(4, self.first) + expected = self.first + self.assertEqual(actual, expected) + + def test_k_greater_than_linked_list_length(self): + with self.assertRaises(Exception): + kth_to_last_node(5, self.first) + + def test_k_is_zero(self): + with self.assertRaises(Exception): + kth_to_last_node(0, self.first) + + +unittest.main(verbosity=2) |