From d4d8397e5ffe6734ed5861e48ce475848956a3fe Mon Sep 17 00:00:00 2001 From: William Carroll Date: Wed, 15 Jan 2020 14:25:33 +0000 Subject: Add InterviewCake.com examples Adds some of the code I generated while studying for a role transfer at Google using the fantastic resource, InterviewCake.com. This work predates the mono-repo. I should think of ways to DRY up this code and the code in crack_the_coding_interview, but I'm afraid I'm creating unnecessary work for myself that way. --- .../second-largest-item-bst.py | 179 +++++++++++++++++++++ 1 file changed, 179 insertions(+) create mode 100644 data_structures_and_algorithms/second-largest-item-bst.py (limited to 'data_structures_and_algorithms/second-largest-item-bst.py') diff --git a/data_structures_and_algorithms/second-largest-item-bst.py b/data_structures_and_algorithms/second-largest-item-bst.py new file mode 100644 index 000000000000..bc167d975a7b --- /dev/null +++ b/data_structures_and_algorithms/second-largest-item-bst.py @@ -0,0 +1,179 @@ +import unittest +from collections import deque + + +################################################################################ +# Implementation +################################################################################ +def is_leaf(node): + return node.left is None and node.right is None + + +def find_largest(node): + current = node + while current.right is not None: + current = current.right + return current.value + + +def find_second_largest(node): + history = deque() + current = node + + while current.right: + history.append(current) + current = current.right + + if current.left: + return find_largest(current.left) + elif history: + return history.pop().value + else: + raise TypeError + + +def find_second_largest_backup(node): + history = deque() + current = node + + # traverse -> largest + while current.right: + history.append(current) + current = current.right + + if current.left: + return find_largest(current.left) + elif history: + return history.pop().value + else: + raise ArgumentError + + +# Write a iterative version to avoid consuming memory with the call stack. +# Commenting out the recursive code for now. +def find_second_largest_backup(node): + if node.left is None and node.right is None: + raise ArgumentError + + elif node.right is None and is_leaf(node.left): + return node.left.value + + # recursion + # elif node.right is None: + # return find_largest(node.left) + + # iterative version + elif node.right is None: + current = node.left + while current.right is not None: + current = current.right + return current.value + + # recursion + # TODO: Remove recursion from here. + elif not is_leaf(node.right): + return find_second_largest(node.right) + + # could do an else here, but let's be more assertive. + elif is_leaf(node.right): + return node.value + + else: + raise ArgumentError + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class BinaryTreeNode(object): + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def insert_left(self, value): + self.left = Test.BinaryTreeNode(value) + return self.left + + def insert_right(self, value): + self.right = Test.BinaryTreeNode(value) + return self.right + + def test_full_tree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + right.insert_right(80) + actual = find_second_largest(tree) + expected = 70 + self.assertEqual(actual, expected) + + def test_largest_has_a_left_child(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + actual = find_second_largest(tree) + expected = 60 + self.assertEqual(actual, expected) + + def test_largest_has_a_left_subtree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right_left = right.insert_left(60) + right_left_left = right_left.insert_left(55) + right_left.insert_right(65) + right_left_left.insert_right(58) + actual = find_second_largest(tree) + expected = 65 + self.assertEqual(actual, expected) + + def test_second_largest_is_root_node(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + actual = find_second_largest(tree) + expected = 50 + self.assertEqual(actual, expected) + + def test_descending_linked_list(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(40) + left_left = left.insert_left(30) + left_left_left = left_left.insert_left(20) + left_left_left.insert_left(10) + actual = find_second_largest(tree) + expected = 40 + self.assertEqual(actual, expected) + + def test_ascending_linked_list(self): + tree = Test.BinaryTreeNode(50) + right = tree.insert_right(60) + right_right = right.insert_right(70) + right_right.insert_right(80) + actual = find_second_largest(tree) + expected = 70 + self.assertEqual(actual, expected) + + def test_error_when_tree_has_one_node(self): + tree = Test.BinaryTreeNode(50) + with self.assertRaises(Exception): + find_second_largest(tree) + + def test_error_when_tree_is_empty(self): + with self.assertRaises(Exception): + find_second_largest(None) + + +unittest.main(verbosity=2) -- cgit 1.4.1