Skip to content

Instantly share code, notes, and snippets.

@quad
Created December 14, 2016 01:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save quad/e7a5d907c1c740ddede8e464a85c49b8 to your computer and use it in GitHub Desktop.
Interview Cake Solutions
import typing
import unittest
class TreeNode:
def __init__(self, left=None, right=None):
self.left = left
self.right = right
def is_superbalanced(self):
path = [(0, self)]
max_depth = None
while path:
depth, node = path.pop()
if node.right:
path.append((depth + 1, node.right))
if node.left:
path.append((depth + 1, node.left))
if node.left is None and node.right is None:
if not max_depth:
max_depth = depth
# Incorrect test.
if abs(max_depth - depth) > 1:
return False
return True
class TestIsSuperbalanced(unittest.TestCase):
def test_simple_ok(self):
root = TreeNode(
TreeNode(),
TreeNode())
self.assertTrue(root.is_superbalanced())
def test_simple_fail(self):
root = TreeNode(
TreeNode(TreeNode(TreeNode())),
TreeNode())
self.assertFalse(root.is_superbalanced())
def test_staggered_fail(self):
# TODO
class TempTracker:
def __init__(self):
self._count = 0
self._seen = [0] * (110 + 1)
self._sum = 0
self.max = None
self.min = None
self.mean = None
self.mode = 0
def insert(self, temperature):
self._count += 1
self._seen[temperature] += 1
self._sum += temperature
if self.max is None or temperature > self.max:
self.max = temperature
if self.min is None or temperature < self.min:
self.min = temperature
self.mean = self._sum / self._count
if self._seen[temperature] > self._seen[self.mode]:
self.mode = temperature
class TestTempTracker(unittest.TestCase):
def test_basic(self):
unit = TempTracker()
for t in [0, 1, 1, 2]:
unit.insert(t)
self.assertEqual(unit.max, 2)
self.assertEqual(unit.min, 0)
self.assertEqual(unit.mean, 1.0)
self.assertEqual(unit.mode, 1)
def test_multi_mode(self):
unit = TempTracker()
for t in [1, 3, 6, 3, 1, 3]:
unit.insert(t)
self.assertEqual(unit.min, 1)
self.assertEqual(unit.max, 6)
self.assertEqual(unit.mode, 3)
Rectangle = typing.NamedTuple('Rectangle', [
('left_x', int),
('bottom_y', int),
('width', int),
('height', int)])
def rectangle_collides(a, b):
def _overlap(a_origin, a_mag, b_origin, b_mag):
if a_origin <= b_origin <= a_origin + a_mag:
return b_origin, min(a_mag - (b_origin - a_origin), b_mag)
elif b_origin <= a_origin <= b_origin + b_mag:
return a_origin, min(b_mag - (a_origin - b_origin), a_mag)
return None, None
# Check overlap on the X dimension
left_x, width = _overlap(a.left_x, a.width, b.left_x, b.width)
bottom_y, height = _overlap(a.bottom_y, a.height, b.bottom_y, b.height)
if left_x is None or width == 0 \
or bottom_y is None or height == 0:
return None
return Rectangle(left_x, bottom_y, width, height)
class TestRectangleCollides(unittest.TestCase):
cases = [
((Rectangle(0, 0, 1, 1), Rectangle(5, 5, 1, 1)), None),
((Rectangle(0, 0, 1, 1), Rectangle(0, 0, 1, 1)), Rectangle(0, 0, 1, 1)),
((Rectangle(0, 0, 3, 3), Rectangle(1, 0, 2, 2)), Rectangle(1, 0, 2, 2)),
((Rectangle(0, 0, 1, 1), Rectangle(1, 1, 1, 1)), None),
]
def test_case(self):
for args, expected in self.cases:
self.assertEqual(rectangle_collides(*args), expected)
def make_change(amount, denominations):
coins_per_amount = [0] * (amount + 1)
coins_per_amount[0] = 1
for coin in denominations:
for amount in range(coin, len(coins_per_amount)):
coins_per_amount[amount] += coins_per_amount[amount - coin]
return coins_per_amount[amount]
class TestMakeChange(unittest.TestCase):
cases = [
((4, [1, 2, 3]), 4),
((7, [2, 4]), 0),
]
def test_cases(self):
for args, expected in self.cases:
self.assertEqual(make_change(*args), expected)
def merge_ranges(meetings):
rv = []
current_start, current_end = meetings[0]
for start, end in sorted(meetings):
if start > current_end:
rv.append((current_start, current_end))
current_start, current_end = start, end
elif end > current_end:
current_end = end
rv.append((current_start, current_end))
return rv
class TestMergeRanges(unittest.TestCase):
def test_example(self):
v = [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]
self.assertEqual(
merge_ranges(v),
[(0, 1), (3, 8), (9, 12)])
def test_touching(self):
self.assertEqual(
merge_ranges([(1, 2), (2, 3)]),
[(1, 3)])
def test_subsume(self):
self.assertEqual(
merge_ranges([(1, 5), (2, 3)]),
[(1, 5)])
def test_merged_merge(self):
v = [(1, 10), (2, 6), (3, 5), (7, 9)]
self.assertEqual(
merge_ranges(v),
[(1, 10)])
def highest_product(list_of_ints):
pproducts = [1, 1, 1]
nproducts = [-1, -1]
for x in list_of_ints:
if x >= pproducts[0]:
pproducts = [x, pproducts[0], pproducts[1]]
elif x <= nproducts[0]:
nproducts = [x, nproducts[0]]
high_pproduct = pproducts[0] * pproducts[1] * pproducts[2]
high_nproduct = nproducts[0] * nproducts[1] * pproducts[0]
return max(high_pproduct, high_nproduct)
class TestHighestProduct(unittest.TestCase):
def test_up(self):
v = [1, 2, 3, 4]
self.assertEqual(highest_product(v), 24)
def test_gotcha_a(self):
v = [-10, -10, 1, 3, 2]
self.assertEqual(highest_product(v), 300)
def get_products_of_all_ints_except_at_index(ints):
def _(rv, a):
acc = 1
for idx, v in enumerate(a):
rv[idx] = rv[idx] * acc
acc = acc * v
return rv
a = [1] * len(ints)
right = _(a[::-1], ints[::-1])[::-1]
left = _(right, ints)
return left
class TestGetProductsOfAllIntsExceptAtIndex(unittest.TestCase):
def test_example(self):
v = [1, 7, 3, 4]
self.assertEqual(
get_products_of_all_ints_except_at_index(v),
[84, 12, 28, 21])
def test_with_zero(self):
v = [1, 7, 3, 4, 0]
self.assertEqual(
get_products_of_all_ints_except_at_index(v),
[0, 0, 0, 0, 84])
def get_max_profit(prices):
min_price = prices[0]
best_price = prices[1] - prices[0]
for price in prices[1:]:
best_price = max(best_price, price - min_price)
min_price = min(min_price, price)
return best_price
class TestGetMaxProfit(unittest.TestCase):
def test_example(self):
stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
self.assertEqual(get_max_profit(stock_prices_yesterday), 6)
def test_out_of_order(self):
stock_prices_yesterday = [100, 1, 5]
self.assertEqual(get_max_profit(stock_prices_yesterday), 4)
def test_down(self):
stock_prices_yesterday = [1, 2, 3]
self.assertEqual(get_max_profit(stock_prices_yesterday), 2)
def test_up(self):
stock_prices_yesterday = [3, 2, 1]
self.assertEqual(get_max_profit(stock_prices_yesterday), -1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment