Author Archives: yujinjcho@gmail.com

Update

It’s been a long time since I last wrote and quite a bit has happened since then.

Picking up from October, I had been interviewing at a startup in Mountain View for a Full Stack Engineering position which I got through an online coding challenge. The interview process was interesting. I had to come in for a few days and build a Django app using their API. I received some good feedback but ultimately ended up not getting an offer. I had considered staying in the Bay area since I thought it might be easier to get a tech job there, but decided to just pack up and move to LA since my wife had just started dental school in that area.

I spent pretty much the next two months looking for a job. I did work on one more project to get some experience with full stack Javascript (React, Express, Mongo), but from the conversations I had with people, I felt that they thought I was job-ready. Almost everyday, I spent all my time researching companies and reaching out to people.

It was really demoralizing and a tough couple of months. I figured not having a CS background nor any professional experience would make online applications exceptionally useless so I focused all my efforts on going to events and reaching out to anyone I possibly could. Bootcamp graduates were particularly helpful and I’m awfully thankful. A lot of them had also transitioned into the industry from non-traditional backgrounds and were often willing to chat.

Towards the beginning of December, I finally started picking up traction with a few companies and had a few phone interviews. The job I did end up getting was through a UF alumni. I had done research on the company and thought the bar might be too high for their software engineer role. I was a little lonely and didn’t know many people so figured I’d reach out anyway. We met up and had lunch. He recommended looking into the company’s Data Engineer position which I did.

I started working at Factual in January and have been really happy since then. I’ve learned about distributed computing, Hadoop Map Reduce, and Spark. I’ve started doing work around Machine Learning and managing geographical data with PostGIS. I feel like I’m learning a lot and best of all, the culture and people here are really awesome :).

8.14 Boolean Evaluation – CCI

# [8.14] Boolean Evaluation: Given a boolean expression 
# consisting of the symbols 0 (false), 1 (true), &
# (AND), | (OR), and ^ (XOR), and a desired boolean result
# value 'result', implement a function to count the number
# of ways of parenthesizing the expression such that it
# evaluates to 'result'. The expression should be
# fully parenthesize (e.g., (0)^(1)) but not extraneously
# (e.g., (((0))^(1))).

# EXAMPLE
# countEval("1^0|0|1", False) -> 2
# countEval("0&0&0&1^1|0", True) -> 10

import unittest

def bool_eval(expr, result):
    
    if expr == "1":
        if result:
            return 1
        return 0
    if expr == "0":
        if not result:
            return 1
        return 0

    subways = 0

    for i in xrange(1,len(expr),2):
        
        operator = expr[i]
        left = expr[0:i]
        right = expr[i+1:]

        left_true = bool_eval(left, True)
        left_false = bool_eval(left, False)
        right_true = bool_eval(right, True)
        right_false = bool_eval(right, False)
        total_ways = (left_true + left_false) * (right_true + right_false)
        true_ways = 0

        if operator == "&":
            true_ways += left_true*right_true
        elif operator == "|":
            true_ways += (
                (left_true*right_true) 
                + (left_true*right_false) 
                + (left_false*right_true)
            )
        elif operator == "^":
            true_ways += (left_true*right_false) + (left_false*right_true)

        if result:
            subways += true_ways
        else:
            subways += total_ways - true_ways

    return subways
    
class Test(unittest.TestCase):

    def test_bool_eval(self):
        self.assertEqual(bool_eval("0&0&0&1^1|0", True), 10)
        self.assertEqual(bool_eval("1^0|0|1", False), 2)
        
if __name__ == '__main__':
    unittest.main()

8.13 Stack of Boxes – CCI

# [8.13] Stack of Boxes: You have a stack of boxes, with width 
# w, heights h, and depths d. The boxes cannot be rotated
# and can only be stacked on top of one another if each box
# in the stack is strictly larger than the box above it
# in in width, height, and depth. Implement a method to compute
# the height of the tallest possible stack. The height of a 
# stack is the sum of the heights of each box.

import unittest

def max_stack_height_helper(boxes):
    if len(boxes) == 1:
        return boxes[0].height

    current_box = boxes[0]
    stackable_boxes = get_stackable_boxes(current_box, boxes[1:])

    if stackable_boxes:
        current_height = current_box.height + max_stack_height_helper(stackable_boxes)
    else:
        current_height = current_box.height

    return max(current_height, max_stack_height_helper(boxes[1:]))

def max_stack_height(boxes):
    boxes.sort(key=lambda x: x.height, reverse=True)
    return max_stack_height_helper(boxes)


def get_stackable_boxes(box, boxes):
    for i, top_box in enumerate(boxes):
        if box.can_stack(top_box):
            return boxes[i:]
    return None

class Box(object):
    def __init__(self, width, height, length):
        self.width = width
        self.height = height
        self.length = length

    def can_stack(self, top_box):
        return (
            self.width > top_box.width and
            self.height > top_box.height and
            self.length > top_box.length
        )

    def __repr__(self):
        return 'Box(%s, %s, %s)' % (self.width, self.height, self.length)


class Test(unittest.TestCase):
    def setUp(self):
        b1 = Box(1,1,1)
        b2 = Box(2,2,2)
        b3 = Box(3,3,3)
        self.boxes1 = [b1,b2,b3]

        b4 = Box(1,1,1)
        b5 = Box(3,2,2)
        b6 = Box(3,3,3)
        self.boxes2 = [b4,b5,b6]

        b7 = Box(6,4,4)
        b8 = Box(7,5,5)
        b9 = Box(7,8,2)
        self.boxes3 = [b7,b8,b9]

        b10 = Box(5,5,5)
        self.boxes4 = [b10]

    
    def test_max_stack_height(self):
        self.assertEqual(max_stack_height(self.boxes1), 6)
        self.assertEqual(max_stack_height(self.boxes2), 4)
        self.assertEqual(max_stack_height(self.boxes3), 9)
        self.assertEqual(max_stack_height(self.boxes4), 5)


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

8.12 Eight Queens – CCI

# [8.12] Eight Queens: Write an algorithm to print all ways of
# arranging eight queens on an 8x8 chess board so that none
# of them share the same row, column, or diagonal. In this case,
# "diagonal" means all diagonals, not just the two that bisect
# the board.

import unittest

def queens(num_queens):
    results = []
    grid_size = num_queens
    columns = [None]*num_queens
    n_ways(columns, 0, results, grid_size)
    return results


def n_ways(columns, row, results, grid_size):
    
    if row == grid_size:
        results.append(columns)
        return

    for col in range(0, grid_size):
        if is_valid(columns, row, col, grid_size):
            cols_copy = columns[:]
            cols_copy[row] = col
            n_ways(cols_copy, row+1, results, grid_size)


def is_valid(columns, row1, col1, grid_size):
    
    if col1 in columns:
        return False

    for row2, col2 in enumerate(columns):
        if col2 is not None:
            if abs(col1 - col2) == abs(row1 - row2):
                return False

    return True


class Test(unittest.TestCase):
    
    def test_queens(self):
        self.assertEqual(len(queens(8)), 92)

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

8.11 Coins – CCI

# [8.11] Coins: Given an infinite number of quarters, dimes, 
# nickels, and pennies, write code to calculate the number of 
# ways of representing n cents.

import unittest

def change(amount):
    coins = [25,10,5,1]
    return change_helper(amount, 0, coins)

def change_helper(amount, denom, coins):
    if denom == 3:
        return 1
    elif amount < 0:
        return 0

    denom_amount = coins[denom]
    subtract_denom = change_helper(amount-denom_amount, denom, coins)
    move_to_next_denom = change_helper(amount, denom+1, coins)
    return subtract_denom + move_to_next_denom

class Test(unittest.TestCase):
    
    def test_change(self):
        self.assertEqual(change(10), 4)
        self.assertEqual(change(15), 6)


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

8.10 Paint Fill – CCI

# [8.10] Paint Fill: Implement the "paint fill" function that 
# one might see on many image editing programs. That is, given
# a screen (represented by a two-dimensional array of colors),
# a point, and a new color, fill in the surrounding area until 
# the color changes from the original color.

import unittest

def paint_fill(grid, row, col, color):
    target_color = grid[row][col]
    paint_fill_helper(grid, row, col, target_color, color)
    
def paint_fill_helper(grid, row, col, color_from, color_to):
    if not coords_in_bounds(grid, row, col):
        return

    if grid[row][col] == color_from:
        grid[row][col] = color_to
        paint_fill_helper(grid, row-1, col, color_from, color_to)
        paint_fill_helper(grid, row+1, col, color_from, color_to)
        paint_fill_helper(grid, row, col-1, color_from, color_to)
        paint_fill_helper(grid, row, col+1, color_from, color_to)


def coords_in_bounds(grid, row, col):
    row_in_bounds = row < len(grid) and row >= 0
    col_in_bounds = col < len(grid[0]) and col >= 0
    return row_in_bounds and col_in_bounds

class Test(unittest.TestCase):
    def setUp(self):
        self.grid = [
            ['white', 'white','red','red'],
            ['white', 'white','white','white'],
            ['white', 'white','white','white'],
            ['blue', 'blue','white','white'],
            ['blue', 'blue','white','white'],
        ]
        self.result = [
            ['blue', 'blue','red','red'],
            ['blue', 'blue','blue','blue'],
            ['blue', 'blue','blue','blue'],
            ['blue', 'blue','blue','blue'],
            ['blue', 'blue','blue','blue'],
        ]

    
    def test_paint_fill(self):
        paint_fill(self.grid, 0, 0, 'blue')
        self.assertEqual(self.grid, self.result)


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

8.9 Parens – CCI

# [8.9] Parens: Implement an algorithm to print all valid (e.g
# properly opened and closed) combinations of n pairs of
# parentheses

# EXAMPLE: 
# Input: 3
# Output: ((())), (()()), (())(), ()(()), ()()()

import unittest

def parens(n):
    result = []
    parens_helper('', 0, 0, n, result)
    return result

def parens_helper(s, left, right, n, result):
    if left == n and right == n:
        result.append(s)

    if left < n:
        parens_helper(s + '(', left+1, right, n, result)

    if right < left:
        parens_helper(s + ')', left, right+1, n, result)


class Test(unittest.TestCase):
    def setUp(self):
        self.result = ['((()))', '(())()', '()()()', '()(())', '()()()', '(()())']
    
    def test_parents(self):
        self.assertEqual(set(parens(3)), set(self.result))


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

8.8 Permutation with Dups – CCI

# [8.8] Permutation with Dups: Write a method to computer all
# permutations of a string whose characters are not necessarily
# unique. The list of permutations should not have duplicates.

import unittest

def perms_with_dups(s):
    char_count = get_char_count(s)
    result = []
    perms_with_dups_helper('', char_count, len(s), result)
    return result

def perms_with_dups_helper(s, char_count, n, result):
    if len(s) == n:
        result.append(s)

    for char in char_count:

        if char_count[char] == 1:
            del char_count[char]
        else:
            char_count[char] -= 1

        perms_with_dups_helper(s + char, char_count, n, result)

        if not char in char_count:
            char_count[char] = 1
        else:
            char_count[char] += 1


def get_char_count(s):
    char_count = {}
    for char in s:
        if char not in char_count:
            char_count[char] = 1
        else:
            char_count[char] += 1

    return char_count

class Test(unittest.TestCase):
    
    def setUp(self):
        self.result = ['aaac', 'aaca', 'acaa', 'caaa']

    def test_perms_with_dups(self):
        self.assertEqual(set(perms_with_dups('aaac')), set(self.result))


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

8.7 Permutations without Duplicates – CCI

  • we can find all permutations starting with a certain char by prepending it to all the permutations of the remaining characters
  • by recursively calling on subsequently smaller groups of chars, we can return the result
# [8.7] Permutations without Dups: Write a method to compute
# all permutations of a string of unique characters.

import unittest

def perms_with_dups(s):
    if len(s) == 1:
        return [s]

    result = []
    for char_index in range(len(s)):
        active_char = s[char_index]
        remaining = s[:char_index] + s[char_index+1:]
        remaining_perms = perms_with_dups(remaining)
        perms = [active_char + perm for perm in remaining_perms]
        result.extend(perms) 

    return result

class Test(unittest.TestCase):
    
    def setUp(self):
        self.result = ['abc','acb','bac','bca','cab','cba']

    def test_perms_with_dups(self):
        self.assertEqual(set(perms_with_dups('abc')), set(self.result))


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

8.6 Towers of Hanoi – CCI

# [8.6] Towers of Hanoi: In the classic problem of the Towers
# of Hanoi, you have 3 towers and N disks of different sizes
# which can slide onto any tower. The puzzle starts with disks
# sorted in ascending order of size from top to bottom (i.e.
# each disk sits on top of an even larger one). You have the 
# following constraints:

# (1) Only one disk can be moved at a time
# (2) A disk is slid off the top of one tower onto another
# (3) A disk cannot be placed on top of a smaller disk

# Write a program to move the disks from the first tower to the
# last using stacks.

import unittest

def hanoi(towers, n, start, temp, end):
    if n > 0:
        hanoi(towers, n-1, start, end, temp)
        if towers[start]:
            disk = towers[start].pop()
            towers[end].append(disk)
        hanoi(towers, n-1, temp, start, end)
    

class Test(unittest.TestCase):
    def setUp(self):
        self.towers = [[5,4,3,2,1], [], []]
        self.result = [[], [], [5,4,3,2,1]]
    
    def test(self):
        hanoi(self.towers, len(self.towers[0]), 0, 1, 2)
        self.assertEqual(self.towers, self.result)

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