interview_practice.py

import unittest
import logging
import sys

# https://github.com/adicu/interview_help/blob/master/interview_handout.md

# 1.) Given a two-dimensional array in which each row and each column is sorted,
# detect if a given element is in the array
from typing import List
TwoDMatrix = List[List[int]]
def detect_in_2d_arr(input:TwoDMatrix, target:int) -> bool:
    max_coord = len(input)
    # TODO: could perform binary search on diagonal and axes for speeeeeed

    # go down the diagonal
    for split_coord in range(max_coord):
        if input[split_coord][split_coord] == target:
            return True
        if input[split_coord][split_coord] > target:
            max_coord = split_coord

    # check our 'horizontal' axis
    for x_coord in range(max_coord, -1, -1):
        # logging.debug('testing value of: %d', input[x_coord][max_coord])
        if input[x_coord][max_coord] == target:
            return True
        if input[x_coord][max_coord] < target:
            break

    # check our 'vertical' axis
    for y_coord in range(max_coord, -1, -1):
        # logging.debug('testing value of: %d', input[max_coord][y_coord])
        if input[max_coord][y_coord] == target:
            return True
        if input[max_coord][y_coord] < target:
            break

    return False

class TestDetect2DArr(unittest.TestCase):
    def test_simple_success(self):
        self.assertEqual(detect_in_2d_arr([[2], [3]], 2), True)

    def test_between(self):
        self.assertEqual(detect_in_2d_arr([[2, 4], [5, 6]], 3), False)

    def test_too_big(self):
        self.assertEqual(detect_in_2d_arr([[2, 4, 6], [3, 7, 8], [4, 8, 10]], 9), False)

    def test_found_value(self):
        self.assertEqual(detect_in_2d_arr([[2, 6, 10, 89],[7, 23, 46, 667],[8, 25, 50, 700],[9, 30, 55, 800]], 667), True)

    def test_no_value(self):
        self.assertEqual(detect_in_2d_arr([[2, 6, 10, 89],[7, 23, 46, 667],[8, 25, 50, 700],[9, 30, 55, 800]], 668), False)

    def test_fast_scale_one_axis(self):
        self.assertEqual(detect_in_2d_arr([[2, 6, 10, 89],[7, 23, 46, 667],[8, 25, 50, 700],[9, 10000, 50000, 70000]], 9), True)



# 2.) Write a method that sorts a list of strings such that all anagrams are adjacent in the list
def anagram_sort(str_list:List[str]) -> List[str]:
    letter_dict = dict()
    for idx, word in enumerate(str_list):
        letters = ''.join(sorted(word))
        if letters in letter_dict:
            letter_dict[letters].append(idx)
        else:
            letter_dict[letters] = [idx]

    output = list()
    for letters in letter_dict:
        for idx in letter_dict[letters]:
            output.append(str_list[idx])

    return output


class TestAnagramSort(unittest.TestCase):
    def test_simple_pass(self):
        input_data = ['rail safety', 'roflcopters', 'fairy tales']
        result = anagram_sort(input_data)
        first_anagram_idx = result.index('rail safety')
        second_anagram_idx = result.index('fairy tales')
        self.assertEqual(abs(first_anagram_idx - second_anagram_idx), 1)



# 3.) Given an integer, return as a string the binary representation of the integer.
def dec_to_bin(given:int) -> str:
    output_string = str()
    while given > 0:
        output_string += '{}'.format(given % 2)
        given //= 2
        # logging.debug('output string: %s -- new given: %d', output_string, given)
    return output_string[::-1]


class TestDecToBin(unittest.TestCase):
    def test_simple_success(self):
        self.assertEqual(dec_to_bin(40), '101000')


if __name__ == '__main__':
    logging.basicConfig( stream=sys.stderr )
    logging.getLogger().setLevel( logging.DEBUG )
    unittest.main()