Daily Coding Problems 2020 Nov to Jan

1 2 3 4 8
5 1 2 3 4
4 5 1 2 3
7 4 5 1 2

import unittest

def is_valid_toeplitz(matrix):
    if not matrix or not matrix[0]:
        return True

    n, m = len(matrix), len(matrix[0])
    for r in xrange(1, n):
        for c in xrange(1, m):
            if matrix[r][c] != matrix[r - 1][c - 1]:
                return False
    
    return True


class IsValidToeplitz(unittest.TestCase):
    def test_example(self):
        matrix = [
            [1, 2, 3, 4, 8],
            [5, 1, 2, 3, 4],
            [4, 5, 1, 2, 3],
            [7, 4, 5, 1, 2]]
        self.assertTrue(is_valid_toeplitz(matrix))

    def test_empty_matrix(self):
        self.assertTrue(is_valid_toeplitz([]))
        self.assertTrue(is_valid_toeplitz([[]]))
    
    def test_one_elem_matrix(self):
        matrix = [[1]]
        self.assertTrue(is_valid_toeplitz(matrix))

    def test_matrix_of_one_row(self):
        matrix = [[1, 2, 3]]
        self.assertTrue(is_valid_toeplitz(matrix))
    
    def test_matrix_of_one_column(self):
        matrix = [
            [1],
            [2],
            [3]]
        self.assertTrue(is_valid_toeplitz(matrix))
    
    def test_valid_toeplitz(self):
        matrix = [
            [1, 1, 0],
            [1, 1, 1]
        ]
        self.assertTrue(is_valid_toeplitz(matrix))

    def test_invalid_toeplitz(self):
        matrix = [
            [1, 1, 1],
            [1, 1, 0],
            [1, 1, 1]
        ]
        self.assertFalse(is_valid_toeplitz(matrix))

    def test_invalid_toeplitz2(self):
        matrix = [
            [1, 0, 1],
            [0, 1, 1]
        ]
        self.assertFalse(is_valid_toeplitz(matrix))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def is_valid_number(raw_num):
    """
    (WHITE_SPACE) (SIGN) DIGITS (DOT DIGITS) (e (SIGN) DIGITS) (WHITE_SPACE)
    or
     (WHITE_SPACE) (SIGN) DOT DIGITS (e (SIGN) DIGITS) (WHITE_SPACE)
    """
    start = 0
    end = len(raw_num) - 1
    while start < len(raw_num) and raw_num[start].isspace():
        start += 1

    while end >= 0 and raw_num[end].isspace():
        end -= 1

    if start > end:
        return False
    
    has_sign = False
    has_dot = False
    has_exp = False
    has_digits = False

    for i in xrange(start, end + 1):
        ch = raw_num[i]
        if ch in ('-', '+'):
            if has_sign or has_digits or has_dot:
                return False
            has_sign = True
        elif ch.isdigit():
            has_digits = True
        elif ch in ('e', 'E'):
            if has_exp or not has_digits:
                return False
            has_exp = True
            has_sign = False
            has_dot = False
            has_digits = False
        elif ch == '.':
            if has_dot or has_exp:
                return False
            has_dot = True
        else:
            return False
    
    return has_digits


class IsValidNumberSpec(unittest.TestCase):
    def test_example1(self):
        self.assertTrue(is_valid_number("123"))  # Integer

    def test_example2(self):
        self.assertTrue(is_valid_number("12.3"))  # Floating point
    
    def test_example3(self):
        self.assertTrue(is_valid_number("-123"))  # Negative numbers
    
    def test_example4(self):
        self.assertTrue(is_valid_number("-.3"))  # Negative floating point
    
    def test_example5(self):
        self.assertTrue(is_valid_number("1.5e5")) # Scientific notation
    
    def test_example6(self):
        self.assertFalse(is_valid_number("12a"))  # No letters
    
    def test_example7(self):
        self.assertFalse(is_valid_number("1 2")) # No space between numbers
    
    def test_example8(self):
        self.assertFalse(is_valid_number("1e1.2"))  # Exponent can only be an integer (positive or negative or 0)
        
    def test_empty_string(self):
        self.assertFalse(is_valid_number(""))

    def test_blank_string(self):
        self.assertFalse(is_valid_number("   "))

    def test_just_signs(self):
        self.assertFalse(is_valid_number("+"))

    def test_zero(self):
        self.assertTrue(is_valid_number("0"))

    def test_contains_no_number(self):
        self.assertFalse(is_valid_number("e"))

    def test_contains_white_spaces(self):
        self.assertTrue(is_valid_number(" -123.456  "))

    def test_scientific_notation(self):
        self.assertTrue(is_valid_number("2e10"))

    def test_scientific_notation2(self):
        self.assertFalse(is_valid_number("10e5.4"))

    def test_scientific_notation3(self):
        self.assertTrue(is_valid_number("-24.35e-10"))

    def test_scientific_notation4(self):
        self.assertFalse(is_valid_number("1e1e1"))

    def test_scientific_notation5(self):
        self.assertTrue(is_valid_number("+.5e-23"))

    def test_scientific_notation6(self):
        self.assertFalse(is_valid_number("+e-23"))

    def test_scientific_notation7(self):
        self.assertFalse(is_valid_number("0e"))

    def test_scientific_notation8(self):
        self.assertTrue(is_valid_number("1E9"))

    def test_multiple_signs(self):
        self.assertFalse(is_valid_number("+-2"))

    def test_multiple_signs2(self):
        self.assertFalse(is_valid_number("-2-2-2-2"))

    def test_multiple_signs3(self):
        self.assertFalse(is_valid_number("6+1"))

    def test_multiple_dots(self):
        self.assertFalse(is_valid_number("10.24.25"))

    def test_sign_and_dot(self):
        self.assertFalse(is_valid_number(".-4"))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

2
1.5
2
3.5
2
2
2

* 1, [2], 3
* 1, [2], [3], 4

[5, 1, 7]            [8 , 20, 10]
       ^ left-max     ^ right-min

import unittest
from Queue import PriorityQueue

def generate_running_median(num_stream):
    min_heap = PriorityQueue()
    max_heap = PriorityQueue()

    for num in num_stream:
        min_heap.put(num)
        if min_heap.qsize() - max_heap.qsize() > 1:
            max_heap.put(-min_heap.get())
        
        if min_heap.qsize() == max_heap.qsize():
            yield (-max_heap.queue[0] + min_heap.queue[0]) / 2.0
        else:
            yield min_heap.queue[0]


class GenerateRunningMedian(unittest.TestCase):
    def test_example(self):
        num_stream = iter([2, 1, 5, 7, 2, 0, 5])
        expected = [2, 1.5, 2, 3.5, 2, 2, 2]
        self.assertEqual(expected, list(generate_running_median(num_stream)))

    def test_empty_stream(self):
        self.assertEqual([], list(generate_running_median(iter([]))))

    def test_unique_value(self):
        num_stream = iter([1, 1, 1, 1, 1])
        expected = [1, 1, 1, 1, 1]
        self.assertEqual(expected, list(generate_running_median(num_stream)))

    def test_contains_zero(self):
        num_stream = iter([0, 1, 1, 0, 0])
        expected = [0, 0.5, 1, 0.5, 0]
        self.assertEqual(expected, list(generate_running_median(num_stream)))

    def test_contains_zero2(self):
        num_stream = iter([2, 0, 1])
        expected = [2, 1, 1]
        self.assertEqual(expected, list(generate_running_median(num_stream)))

    def test_even_iteration_gives_average(self):
        num_stream = iter([3, 0, 1, 2])
        expected = [3, 1.5, 1, 1.5]
        self.assertEqual(expected, list(generate_running_median(num_stream)))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest
import random

class URLShortener(object):
    CHAR_SET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    def __init__(self):
        self.short_to_long = {}
        self.long_to_short = {}

    def shorten(self, url):
        if url in self.long_to_short:
            return self.long_to_short[url]

        short = None
        while not short or short in self.short_to_long:
            short = URLShortener.encode(url)
        self.long_to_short[url] = short
        self.short_to_long[short] = url
        return short

    def restore(self, short):
        return self.short_to_long.get(short, None)

    @staticmethod
    def encode(url):
        return "".join(random.choice(URLShortener.CHAR_SET) for _ in xrange(6))


class URLShortenerSpec(unittest.TestCase):
    def test_should_be_able_to_init(self):
        URLShortener()

    def test_restore_should_not_fail_when_url_not_exists(self):
        url_shortener = URLShortener()
        self.assertIsNone(url_shortener.restore("oKImts"))

    def test_shorten_result_into_six_letters(self):
        url_shortener = URLShortener()
        res = url_shortener.shorten("http://magic_url")
        self.assertEqual(6, len(res))

    def test_restore_short_url_gives_original(self):
        url_shortener = URLShortener()
        original_url = "http://magic_url"
        short_url = url_shortener.shorten(original_url)
        self.assertEqual(original_url, url_shortener.restore(short_url))

    def test_shorten_different_url_gives_different_results(self):
        url_shortener = URLShortener()
        url1 = "http://magic_url_1"
        res1 = url_shortener.shorten(url1)
        url2 = "http://magic_url_2"
        res2 = url_shortener.shorten(url2)
        self.assertNotEqual(res1, res2)

    def test_shorten_same_url_gives_same_result(self):
        url_shortener = URLShortener()
        url = "http://magic_url_1"
        res1 = url_shortener.shorten(url)
        res2 = url_shortener.shorten(url)
        self.assertEqual(res1, res2)
        

if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

For n = 2, one gray code would be [00, 01, 11, 10].

import unittest

def gray_code(n):
    """
                      0
                  /       \
              0                 1
            /   \              /  \
         00       01        11       10
       /  \      /  \      /  \     /  \
     000  001  011  010  110  111  101  100
    """
    res = [0] * (2 ** n)
    for step in xrange(n):
        for i in xrange(2 ** step - 1, -1, -1):
            prev = res[i]
            prev_append_zero = prev << 1
            prev_append_one = prev_append_zero + 1 
            if i % 2 == 0:
                res[2 * i] = prev_append_zero
                res[2 * i + 1] = prev_append_one
            else:
                res[2 * i] = prev_append_one
                res[2 * i + 1] = prev_append_zero
    return res


class GrayCodeSpec(unittest.TestCase):
    def validate_grey_code(self, code_arr):
        for i in xrange(1, len(code_arr)):
            cur = code_arr[i]
            prev = code_arr[i-1]
            xor_val = cur ^ prev
            if xor_val & (xor_val - 1) != 0:
                # make sure the current value is 1 bit different from the previous value
                return False
        return True

    def test_zero_bit_grey_code(self):
        self.assertTrue(self.validate_grey_code(gray_code(0)))

    def test_one_bit_grey_code(self):
        self.assertTrue(self.validate_grey_code(gray_code(1)))

    def test_two_bits_grey_code(self):
        self.assertTrue(self.validate_grey_code(gray_code(2)))

    def test_three_bits_grey_code(self):
        self.assertTrue(self.validate_grey_code(gray_code(3)))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def rotate_list(head, k):
    if not head:
        return None

    n = list_len(head)
    k %= n
    if k == 0:
        return head

    fast = slow = head
    for _ in xrange(k):
        fast = fast.next

    while fast.next:
        fast = fast.next
        slow = slow.next
    
    res = slow.next
    fast.next = head
    slow.next = None
    return res


def list_len(lst):
    res = 0
    while lst:
        lst = lst.next
        res += 1
    return res 


class Node(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

    def __eq__(self, other):
        return other and self.val == other.val and self.next == other.next

    def __repr__(self):
        return "%d -> %s" % (self.val, self.next)

    @staticmethod
    def List(*vals):
        p = dummy = Node(-1)
        for val in vals:
            p.next = Node(val)
            p = p.next
        return dummy.next


class RotateListSpec(unittest.TestCase):
    def test_example(self):
        k, lst = 2, Node.List(1, 2, 3, 4)
        expected = Node.List(3, 4, 1, 2)
        self.assertEqual(expected, rotate_list(lst, k))

    def test_empty_list(self):
        self.assertIsNone(rotate_list(None, 42))

    def test_single_elem_list(self):
        k, lst = 42, Node.List(1)
        expected = Node.List(1)
        self.assertEqual(expected, rotate_list(lst, k))

    def test_k_greater_than_length_of_list(self):
        k, lst = 5, Node.List(1, 2)
        expected = Node.List(2, 1)
        self.assertEqual(expected, rotate_list(lst, k))

    def test_k_equal_length_of_list(self):
        k, lst = 3, Node.List(1, 2, 3)
        expected = Node.List(1, 2, 3)
        self.assertEqual(expected, rotate_list(lst, k))

    def test_k_less_than_length_of_list(self):
        k, lst = 5, Node.List(0, 1, 2, 3, 4, 5)
        expected = Node.List(1, 2, 3, 4, 5, 0)
        self.assertEqual(expected, rotate_list(lst, k))

    def test_array_contains_duplicates(self):
        k, lst = 1, Node.List(1, 2, 2, 3, 3, 3, 4)
        expected = Node.List(4, 1, 2, 2, 3, 3, 3)
        self.assertEqual(expected, rotate_list(lst, k))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def min_partition_difference(nums):
    nums_sum = sum(nums)
    n = len(nums)

    # Let dp[i][sum] represents exists subset sum for nums[:i]
    # dp[i][sum] = dp[i-1][sum]              if exclude nums[i - 1]
    #            = dp[i-1][sum - nums[i-1]]  if include nums[i - 1]
    dp = [[False for _ in xrange(nums_sum // 2 + 1)] for _ in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][0] = True

    for i in xrange(1, n + 1):
        elem = nums[i-1]
        for s in xrange(1, nums_sum // 2 + 1):
            # Exclude current element, as we can already reach sum s
            dp[i][s] = dp[i - 1][s]

            if s -  elem >= 0:
                # As all number are positive, include current elem cannot exceed current sum
                dp[i][s] = dp[i - 1][s - elem]
    
    """
     Let's do some math here:
     Let s1, s2 be the size to two subsets after partition and assume s1 >= s2
     We can have s1 + s2 = sum_nums and we want to get min{s1 - s2} where s1 >= s2:

     min{s1 - s2}
     = min{s1 + s2 - s2 - s2}
     = min{sum_nums - 2 * s2}  in this step sum_nums - 2 * s2 >=0, gives s2 <= sum_nums/ 2
     = sum_nums - 2 * max{s2}  where s2 <= sum_nums/2
    """
    for s in xrange(nums_sum // 2, -1, -1):
        if dp[n][s]:
            return nums_sum - 2 * s

    return None


class MinPartitionDifferenceSpec(unittest.TestCase):
    def test_example(self):
        # Partition: [10, 25] and [5, 15, 20]
        self.assertEqual(5, min_partition_difference([5, 10, 15, 20, 25]))

    def test_empty_array(self):
        self.assertEqual(0, min_partition_difference([]))

    def test_array_with_one_element(self):
        self.assertEqual(42, min_partition_difference([42]))

    def test_array_with_two_elements(self):
        self.assertEqual(0, min_partition_difference([42, 42]))

    def test_unsorted_array_with_duplicated_numbers(self):
        # Partition: [3, 4] and [1, 2, 2, 1]
        self.assertEqual(1, min_partition_difference([3, 1, 4, 2, 2, 1]))

    def test_unsorted_array_with_unique_numbers(self):
        # Partition: [11] and [1, 5, 6]
        self.assertEqual(1, min_partition_difference([1, 6, 11, 5]))

    def test_sorted_array_with_duplicated_numbers(self):
        # Partition: [1, 2, 2] and [4]
        self.assertEqual(1, min_partition_difference([1, 2, 2, 4]))

    def test_min_partition_difference_is_zero(self):
        # Partition: [1, 8, 2, 7] and [3, 6, 4, 5]
        self.assertEqual(0, min_partition_difference([1, 2, 3, 4, 5, 6, 7, 8]))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def smallest_stub_set(intervals):
    intervals.sort(key=lambda interval: (interval[1], interval[0]))

    smallest_end = None
    res = []
    for start, end in intervals:
        if start > smallest_end:
            res.append(end)
            smallest_end = end
    return res


class SmallestStubSetSpec(unittest.TestCase):
    def assert_result(self, expected, intervals):
        res = smallest_stub_set(intervals)
        self.assertEqual(len(expected), len(res), "Expected result like {} but given {}".format(expected, res))
        for num in res:
            self.assertTrue(any(lo <= num <= hi for lo, hi in intervals))

    def test_example(self):
        intervals = [(1, 4), (4, 5), (7, 9), (9, 12)]
        expected = [4, 9]
        self.assert_result(expected, intervals)

    def test_empty_intervals(self):
        self.assertEqual([], smallest_stub_set([]))

    def test_optimal_result(self):
        intervals = [(1, 5), (5, 10), (2, 9)]
        expected = [5]
        self.assert_result(expected, intervals)

    def test_optimal_result2(self):
        intervals = [(2, 8), (8, 15), (1, 5), (5, 10), (10, 20)]
        expected = [5, 10]
        self.assert_result(expected, intervals)

    def test_have_to_include_all_ends(self):
        intervals = [(2, 2), (8, 8), (1, 1), (5, 5), (2, 2)]
        expected = [1, 2, 5, 8]
        self.assert_result(expected, intervals)

    def test_multiple_solutions(self):
        intervals = [(1, 2), (1, 3), (1, 4), (3, 5)]
        expected = [2, 5]  # other solution also work
        self.assert_result(expected, intervals)
    
    def test_multiple_solutions2(self):
        intervals = [(1, 5), (2, 5), (3, 5), (4, 10)]
        expected = [5]  # other solution also work
        self.assert_result(expected, intervals)


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

 Bytes   |           Byte format
-----------------------------------------------
   1     | 0xxxxxxx
   2     | 110xxxxx 10xxxxxx
   3     | 1110xxxx 10xxxxxx 10xxxxxx
   4     | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

import unittest

MAX_BYTE = 0b11111111
FOLLOWING_BYTE_PREFIX = 0b10


def validate_utf8(byte_arr):
    if not byte_arr:
        return False
    
    first_byte = byte_arr[0]
    if len(byte_arr) == 1:
        return first_byte >> 7 == 0
    
    if not validate_byte_value(byte_arr):
        return False

    num_bytes = count_prefix_ones(first_byte)
    if num_bytes != len(byte_arr):
        return False
    
    return validate_following_bytes(byte_arr[1:])


def validate_byte_value(byte_arr):
    return all(byte <= MAX_BYTE for byte in byte_arr)


def count_prefix_ones(byte):
    count = 0
    for i in xrange(7, -1, -1):
        if byte & 1 << i == 0:
            break
        count += 1
    return count


def validate_following_bytes(byte_arr):
    return all(FOLLOWING_BYTE_PREFIX == (byte >> 6) for byte in byte_arr)


class ValidateUtf8Spec(unittest.TestCase):
    def test_example(self):
        byte_arr = [0b11100010, 0b10000010, 0b10101100]
        self.assertTrue(validate_utf8(byte_arr))

    def test_empty_arr(self):
        byte_arr = []
        self.assertFalse(validate_utf8(byte_arr))

    def test_valid_one_byte(self):
        byte_arr = [0b0]
        self.assertTrue(validate_utf8(byte_arr))

    def test_valid_one_byte2(self):
        byte_arr = [0b01111111]
        self.assertTrue(validate_utf8(byte_arr))

    def test_invalid_one_byte(self):
        byte_arr = [0b10101010]
        self.assertFalse(validate_utf8(byte_arr))

    def test_invalid_one_byte2(self):
        byte_arr = [0b0, 0b10000010]
        self.assertFalse(validate_utf8(byte_arr))

    def test_valid_two_bytes(self):
        byte_arr = [0b11000000, 0b10000000]
        self.assertTrue(validate_utf8(byte_arr))

    def test_valid_two_bytes2(self):
        byte_arr = [0b11011111, 0b10111111]
        self.assertTrue(validate_utf8(byte_arr))

    def test_valid_three_bytes(self):
        byte_arr = [0b11100000, 0b10000000, 0b10000000]
        self.assertTrue(validate_utf8(byte_arr))

    def test_valid_three_bytes2(self):
        byte_arr = [0b11101111, 0b10111111, 0b10111111]
        self.assertTrue(validate_utf8(byte_arr))

    def test_valid_four_bytes(self):
        byte_arr = [0b11110000, 0b10000000, 0b10000000, 0b10000000]
        self.assertTrue(validate_utf8(byte_arr))

    def test_valid_four_bytes2(self):
        byte_arr = [0b11110111, 0b10111111, 0b10111111, 0b10111111]
        self.assertTrue(validate_utf8(byte_arr))

    def test_short_on_bytes(self):
        byte_arr = [0b11110111, 0b10111111, 0b10111111]
        self.assertFalse(validate_utf8(byte_arr))

    def test_more_than_necessary_bytes(self):
        byte_arr = [0b11000111, 0b10111111, 0b10111111]
        self.assertFalse(validate_utf8(byte_arr))
    
    def test_following_bytes_with_incorrect_prefix(self):
        byte_arr = [0b11100000, 0b11000000, 0b11000000]
        self.assertFalse(validate_utf8(byte_arr))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def is_palindrome_integer(num):
    return num >= 0 and num == reverse_number(num)


def reverse_number(num):
    res = 0
    while num > 0:
        res = 10 * res + num % 10
        num //= 10
    return res


class IsPalindromeIntegerSpec(unittest.TestCase):
    def test_example1(self):
        self.assertTrue(is_palindrome_integer(121))

    def test_example2(self):
        self.assertTrue(is_palindrome_integer(88))

    def test_example3(self):
        self.assertFalse(is_palindrome_integer(678))

    def test_example4(self):
        self.assertFalse(is_palindrome_integer(80))

    def test_zero(self):
        self.assertTrue(is_palindrome_integer(0))

    def test_single_digit_number(self):
        self.assertTrue(is_palindrome_integer(7))

    def test_non_palindrome1(self):
        self.assertFalse(is_palindrome_integer(123421))

    def test_non_palindrome2(self):
        self.assertFalse(is_palindrome_integer(21010112))

    def test_negative_number1(self):
        self.assertFalse(is_palindrome_integer(-1))

    def test_negative_number2(self):
        self.assertFalse(is_palindrome_integer(-222))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

power_set([]) => [[]]
power_set([1]) => [[], [1]]
power_set([1, 2]) => [[], [1], [2], [1, 2]]
power_set([1, 2, 3]) => [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] which is power_set([1, 2]) + append powerSet([1, 2]) with new elem 3
...
power_set([1, 2, ..., n]) =>  power_set([1, 2, ..., n - 1]) + append powerSet([1, 2, ..., n - 1]) with new elem n

import unittest

def generate_power_set(nums):
    res = [[]]
    for num in nums:
        include = []
        for existing_set in res:
            include.append(existing_set + [num])
        res.extend(include)
    return res
            

class GeneratePowerSetSpec(unittest.TestCase):
    def test_example(self):
        nums = [1, 2, 3]
        expected = [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]
        self.assertItemsEqual(expected, generate_power_set(nums))

    def test_empty_set(self):
        nums = []
        expected = [[]]
        self.assertItemsEqual(expected, generate_power_set(nums))

    def test_one_elem_set(self):
        nums = [1]
        expected = [[], [1]]
        self.assertItemsEqual(expected, generate_power_set(nums))

    def test_two_elem_set(self):
        nums = [1, 2]
        expected = [[], [1], [2], [1, 2]]
        self.assertItemsEqual(expected, generate_power_set(nums))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def most_freq_tree_sum(tree):
    if not tree:
        return None

    freq = {}
    node_sum(tree, freq)
    return max(freq.keys(), key=lambda k: (freq[k], -k))


def node_sum(node, freq):
    if not node:
        return 0
    
    left_res = node_sum(node.left, freq)
    right_res = node_sum(node.right, freq)
    res = node.val + left_res + right_res
    freq[res] = freq.get(res, 0) + 1
    return res


class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class MostFreqTreeSumSpec(unittest.TestCase):
    def test_example1(self):
        """
           3
          / \
         2  -3
        """
        t = TreeNode(3, TreeNode(2), TreeNode(-3))
        self.assertEqual(2, most_freq_tree_sum(t))

    def test_empty_tree(self):
        self.assertIsNone(most_freq_tree_sum(None))

    def test_tree_with_unique_value(self):
        """
          0
         / \
        0   0
         \
          0
        """
        l = TreeNode(0, right=TreeNode(0))
        t = TreeNode(0, l, TreeNode(0))
        self.assertEqual(0, most_freq_tree_sum(t))

    def test_depth_3_tree(self):
        """
           _0_ 
          /   \
         0     -3  
        / \   /  \   
       1  -1 3   -1  
        """
        l = TreeNode(0, TreeNode(1), TreeNode(-1))
        r = TreeNode(-3, TreeNode(3), TreeNode(-1))
        t = TreeNode(0, l, r)
        self.assertEqual(-1, most_freq_tree_sum(t))

    def test_return_smaller_freq_when_there_is_a_tie(self):
        """
            -2
           /   \
          0     1
         / \   / \
        0   0 1   1
        """
        l = TreeNode(0, TreeNode(0), TreeNode(0))
        r = TreeNode(1, TreeNode(1), TreeNode(1))
        t = TreeNode(-2, l, r)
        self.assertEqual(0, most_freq_tree_sum(t))

    def test_return_smaller_freq_when_there_is_a_tie2(self):
        """
           3
          / \
         2   -1
        """
        t = TreeNode(3, TreeNode(2), TreeNode(-1))
        self.assertEqual(-1, most_freq_tree_sum(t))
        

if __name__ == '__main__':
    unittest.main(exit=False)

{0: [1, 2],
 1: [0, 5],
 2: [0],
 3: [6],
 4: [],
 5: [1],
 6: [3]} 

import unittest

def find_cycles(friendships):
    capacity = len(friendships)
    uf = DisjointSet(capacity)
    for p1, friends in friendships.items():
        for p2 in friends:
            uf.union(p1, p2)
    return uf.groups


class DisjointSet(object):
    def __init__(self, capacity):
        self.parent = range(capacity)
        self.groups = capacity

    def find(self, p):
        while p != self.parent[p]:
            self.parent[p] = self.find(self.parent[p])
            p = self.parent[p]
        return p

    def union(self, p1, p2):
        parent1 = self.find(p1)
        parent2 = self.find(p2)
        if parent1 != parent2:
            self.parent[parent1] = parent2
            self.groups -= 1


class FindCycleSpec(unittest.TestCase):
    def test_example(self):
        friendships = {
            0: [1, 2],
            1: [0, 5],
            2: [0],
            3: [6],
            4: [],
            5: [1],
            6: [3]
        }
        expected = 3  # [0, 1, 2, 5], [3, 6], [4]
        self.assertEqual(expected, find_cycles(friendships))

    def test_no_friends(self):
        friendships = {
            0: [],
            1: [],
            2: []
        }
        expected = 3  # [0], [1], [2]
        self.assertEqual(expected, find_cycles(friendships))

    def test_all_friends(self):
        friendships = {
            0: [1, 2],
            1: [0, 2],
            2: [0, 1]
        }
        expected = 1  # [0, 1, 2]
        self.assertEqual(expected, find_cycles(friendships))
    
    def test_common_friend(self):
        friendships = {
            0: [1],
            1: [0, 2, 3],
            2: [1],
            3: [1],
            4: []
        }
        expected = 2  # [0, 1, 2, 3], [4]
        self.assertEqual(expected, find_cycles(friendships))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def generate_regular_numbers(n):
    if n == 0:
        return []

    res = [1]
    i, j, k = 0, 0, 0
    for _ in xrange(n - 1):
        num = min(2 * res[i], 3 * res[j], 5 * res[k])
        res.append(num)

        if num % 2 == 0:
            i += 1

        if num % 3 == 0:
            j += 1

        if num % 5 == 0:
            k += 1
    return res


# Source: https://en.wikipedia.org/wiki/Regular_number
REGULAR_NUMBERS = [
    1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40,
    45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128,
    135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256, 270,
    288, 300, 320, 324, 360, 375, 384, 400, 405
]


class GenerateRegularNumberSpec(unittest.TestCase):
    def test_empty_result(self):
        self.assertEqual([], generate_regular_numbers(0))

    def test_5_elements(self):
        self.assertEqual(REGULAR_NUMBERS[:5], generate_regular_numbers(5))

    def test_10_elements(self):
        self.assertEqual(REGULAR_NUMBERS[:10], generate_regular_numbers(10))

    def test_15_elements(self):
        self.assertEqual(REGULAR_NUMBERS[:15], generate_regular_numbers(15))

    def test_20_elements(self):
        self.assertEqual(REGULAR_NUMBERS[:20], generate_regular_numbers(20))

if __name__ == '__main__':
    unittest.main(exit=False)

Given the following matrix:
[[ 1,  3,  6, 10, 15, 20],
 [ 2,  7,  9, 14, 22, 25],
 [ 3,  8, 10, 15, 25, 30],
 [10, 11, 12, 23, 30, 35],
 [20, 25, 30, 35, 40, 45]]
And i1 = 1, j1 = 1, i2 = 3, j2 = 3
 
return 15 as there are 15 numbers in the matrix smaller than 7 or greater than 23.

import unittest

def count_elements(matrix, pos1, pos2):
    n, m = len(matrix), len(matrix[0])
    v1 = matrix[pos1[0]][pos1[1]]
    v2 = matrix[pos2[0]][pos2[1]]
    if v1 > v2:
        return n * m

    less_than_v1 = count_smaller_elements(matrix, v1)
    not_greater_than_v2 = count_smaller_elements(matrix, v2, exclusive=False)
    return less_than_v1 + n * m - not_greater_than_v2


def count_smaller_elements(matrix, target, exclusive=True):
    n, m = len(matrix), len(matrix[0])
    res = 0
    row = 0
    for col in xrange(m - 1, -1, -1):
        while row < n:
            if matrix[row][col] > target or exclusive and matrix[row][col] == target:
                break
            row += 1
        res += row
    return res


class CountElementSpec(unittest.TestCase):
    def test_example(self):
        matrix = [
            [1, 3, 6, 10, 15, 20], 
            [2, 7, 9, 14, 22, 25],
            [3, 8, 10, 15, 25, 30], 
            [10, 11, 12, 23, 30, 35],
            [20, 25, 30, 35, 40, 45]]
        pos1, pos2 = (1, 1), (3, 3)
        expected = 15
        self.assertEqual(expected, count_elements(matrix, pos1, pos2))

    def test_no_elem_found(self):
        matrix = [
            [1, 2],
            [3, 6]
        ]
        pos1, pos2 = (0, 0), (1, 1)
        expected = 0
        self.assertEqual(expected, count_elements(matrix, pos1, pos2))

    def test_top_right_bottom_left(self):
        matrix = [
            [1, 2, 3],
            [4, 5, 6],
            [7, 8, 9]]
        pos1, pos2 = (0, 2), (2, 0)
        expected = 4
        self.assertEqual(expected, count_elements(matrix, pos1, pos2))

    def test_covers_entire_matrix(self):
        matrix = [
            [1, 2, 3],
            [2, 3, 4],
            [9, 10, 11]
        ]
        pos1, pos2 = (2, 2), (0, 0)
        expected = 9
        self.assertEqual(expected, count_elements(matrix, pos1, pos2))

    def test_identical_pos(self):
        matrix = [
            [1, 2, 3],
            [2, 3, 4],
            [9, 10, 11]
        ]
        pos1, pos2 = (1, 1), (1, 1)
        expected = 7
        self.assertEqual(expected, count_elements(matrix, pos1, pos2))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

import unittest

def exists_overlap_rectangle(rectangles):
    rects = map(Rectangle.from_object, rectangles)
    # sort by x_min, then y_min
    rects.sort(key=Rectangle.get_bottom_left)
    n = len(rects)
    for i, rect1 in enumerate(rects):
        for j in xrange(i + 1, n):
            rect2 = rects[j]
            if rect2.x_min >= rect1.x_max:
                break
            if rect1.is_overlapped(rect2):
                return True
    
    return False


class Rectangle(object):
    def __init__(self, top_left, dimension):
        self.x_min = top_left[0]
        self.x_max = top_left[0] + dimension[0]
        self.y_min = top_left[1] - dimension[1]
        self.y_max = top_left[1]

    def __repr__(self):
        return "Rectangle(x_min=%d, x_max=%d, y_min=%d, y_max=%d)" % (self.x_min, self.x_max, self.y_min, self.y_max)

    def is_overlapped(self, other):
        return (max(self.x_min, other.x_min) < min(self.x_max, other.x_max) and
                max(self.y_min, other.y_min) < min(self.y_max, other.y_max))

    @staticmethod
    def from_object(obj):
        return Rectangle(obj.get("top_left"), obj.get("dimensions"))
    
    @staticmethod
    def get_bottom_left(rect):
        return (rect.x_min, rect.y_min)


class ExistsOverlapRectangleSpec(unittest.TestCase):
    def test_example(self):
        rectangles = [
            {
                "top_left": (1, 4),
                "dimensions": (3, 3)  # width, height
            },
            {
                "top_left": (-1, 3),
                "dimensions": (2, 1)
            },
            {
                "top_left": (0, 5),
                "dimensions": (4, 3)
            }
        ]
        self.assertTrue(exists_overlap_rectangle(rectangles))

    def test_empty_rectangle_list(self):
        self.assertFalse(exists_overlap_rectangle([]))

    def test_two_overlap_rectangle(self):
        rectangles = [
            {
                "top_left": (0, 1),
                "dimensions": (1, 3)  # width, height
            },
            {
                "top_left": (-1, 0),
                "dimensions": (3, 1)
            }
        ]
        self.assertTrue(exists_overlap_rectangle(rectangles))

    def test_two_overlap_rectangle_form_a_cross(self):
        rectangles = [
            {
                "top_left": (-1, 1),
                "dimensions": (3, 2)  # width, height
            },
            {
                "top_left": (0, 0),
                "dimensions": (1, 1)
            }
        ]
        self.assertTrue(exists_overlap_rectangle(rectangles))

    def test_same_y_coord_not_overlap(self):
        rectangles = [
            {
                "top_left": (0, 0),
                "dimensions": (1, 1)  # width, height
            },
            {
                "top_left": (1, 0),
                "dimensions": (2, 2)
            },
            {
                "top_left": (3, 0),
                "dimensions": (5, 2)
            }
        ]
        self.assertFalse(exists_overlap_rectangle(rectangles))

    def test_same_y_coord_overlap(self):
        rectangles = [
            {
                "top_left": (0, 0),
                "dimensions": (1, 1)  # width, height
            },
            {
                "top_left": (1, 0),
                "dimensions": (2, 2)
            },
            {
                "top_left": (3, 0),
                "dimensions": (5, 2)
            }
        ]
        self.assertFalse(exists_overlap_rectangle(rectangles))

    def test_rectangles_in_different_quadrant(self):
        rectangles = [
            {
                "top_left": (1, 1),
                "dimensions": (2, 2)  # width, height
            },
            {
                "top_left": (-1, 1),
                "dimensions": (2, 2)
            },
            {
                "top_left": (1, -1),
                "dimensions": (2, 2)
            },
            {
                "top_left": (-1, -1),
                "dimensions": (2, 2)
            }
        ]
        self.assertFalse(exists_overlap_rectangle(rectangles))


if __name__ == '__main__':
    unittest.main(exit=False)

import unittest

def calculate_satisfactory_playlist(preference):
    neighbors = {}
    inbound = {}
    for songs in preference:
        prev = None
        for cur_song in songs:
            inbound[cur_song] = inbound.get(cur_song, 0)
            if prev:
                neighbors[prev] = neighbors.get(prev, set())
                if cur_song not in neighbors[prev]:
                    neighbors[prev].add(cur_song)
                    inbound[cur_song] += 1
            prev = cur_song

    queue = []
    for song, count in inbound.items():
        if count == 0:
            queue.append(song)

    res = []
    while queue:
        cur = queue.pop(0)
        res.append(cur)

        if cur not in neighbors:
            continue

        for nb in neighbors[cur]:
            inbound[nb] -= 1
            if inbound[nb] == 0:
                queue.append(nb)
            
    return res if len(res) == len(inbound) else None
        

class CalculateSatisfactoryPlaylistSpec(unittest.TestCase):
    def validate_result(self, preference, suggested_order):
        song_set = set([song for songs in preference for song in songs])
        self.assertEqual(
            song_set,
            set(suggested_order),
            "Missing song: " + str(str(song_set - set(suggested_order))))

        for i in xrange(len(suggested_order)):
            for j in xrange(i+1, len(suggested_order)):
                for lst in preference:
                    song1, song2 = suggested_order[i], suggested_order[j]
                    if song1 in lst and song2 in lst:
                        self.assertLess(
                            lst.index(song1), 
                            lst.index(song2),
                            "Suggested order {} conflict: {} cannot be more popular than {}".format(suggested_order, song1, song2))

    def test_example(self):
        preference = [[1, 7, 3], [2, 1, 6, 7, 9], [3, 9, 5]]
        # possible order: 2, 1, 6, 7, 3, 9, 5
        suggested_order = calculate_satisfactory_playlist(preference) 
        self.validate_result(preference, suggested_order)
    
    def test_preference_contains_duplicate(self):
        preference = [[1, 2], [1, 2], [1, 2]]
        # possible order: 1, 2
        suggested_order = calculate_satisfactory_playlist(preference) 
        self.validate_result(preference, suggested_order)

    def test_empty_graph(self):
        self.assertEqual([], calculate_satisfactory_playlist([]))

    def test_cyclic_graph(self):
        preference = [[1, 2, 3], [1, 3, 2]]
        self.assertIsNone(calculate_satisfactory_playlist(preference))

    def test_acyclic_graph(self):
        preference = [[1, 2], [2, 3], [1, 3, 5], [2, 5], [2, 4]]
        # possible order: 1, 2, 3, 4, 5
        suggested_order = calculate_satisfactory_playlist(preference)
        self.validate_result(preference, suggested_order)

    def test_disconnected_graph(self):
        preference = [[0, 1], [2, 3], [3, 4]]
        # possible order: 0, 1, 2, 3, 4
        suggested_order = calculate_satisfactory_playlist(preference)
        self.validate_result(preference, suggested_order)

    def test_disconnected_graph2(self):
        preference = [[0, 1], [2], [3]]
        # possible order: 0, 1, 2, 3
        suggested_order = calculate_satisfactory_playlist(preference)
        self.validate_result(preference, suggested_order)


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)

Input: "9:00"
Output: 90

import unittest

def clock_angle(hhmm):
    h, m = map(int, hhmm.split(':'))
    h %= 12
    unit_hr = 360 / 12.0
    unit_min = 360 / 60.0

    hr_hand = h * unit_hr + m * unit_hr / 60.0 
    min_hand = m * unit_min
    angle = abs(min_hand - hr_hand)
    return min(angle, 360 - angle)


class ClockAngleSpec(unittest.TestCase):
    def test_minute_point_zero(self):
        hhmm = "12:00"
        angle = 0
        self.assertEqual(angle, clock_angle(hhmm))
        
    def test_minute_point_zero2(self):
        hhmm = "1:00"
        angle = 30
        self.assertEqual(angle, clock_angle(hhmm))
        
    def test_minute_point_zero3(self):
        hhmm = "9:00"
        angle = 90
        self.assertEqual(angle, clock_angle(hhmm))
        
    def test_minute_point_zero4(self):
        hhmm = "6:00"
        angle = 180
        self.assertEqual(angle, clock_angle(hhmm))
        
    def test_half_pass_hour(self):
        hhmm = "12:30"
        angle = 165
        self.assertEqual(angle, clock_angle(hhmm))
        
    def test_half_pass_hour2(self):
        hhmm = "3:30"
        angle = 75
        self.assertEqual(angle, clock_angle(hhmm))

    def test_irregular_time(self):
        hhmm = "16:20"
        angle = 10
        self.assertEqual(angle, clock_angle(hhmm))

    def test_irregular_time3(self):
        hhmm = "3:15"
        angle = 7.5
        self.assertEqual(angle, clock_angle(hhmm))


if __name__ == '__main__':
    unittest.main(exit=False, verbosity=2)