Category Archives: Coding

Two’s Complement

Two’s complement is a way to represent positive and negative integers in binary format. In order to convert a positive binary number to the two’s complement negative number, you invert the bits and add 1.

Let’s say we have an 8-bit integer ‘00001000’ representing 8. We would get ‘11110111’ and then ‘11111000’ when we add the 1. The advantage of using two’s complement is that we can use regular math with the two’s complement version of the negative number. If we were to add 8, to ‘11111000’, the most significant number would overflow and we would go back to ‘00000000’. The two’s complement has a 1 at the most significant bit and accounts for half of the range.

1.8 Zero Matrix – CCI

  • find cols and rows that have a zero
  • set value of coords with those cols or rows to zero
# [1.8] Zero Matrix: Write an algorithm such that if an element
# in an MxN matrix is 0, its entire row and columns are set to 0.

#Time Complexity: O(MN)
#Space Complexity: O(M+N)

import unittest

def set_zeros(matrix):
    # don't do in place, because entire matrix
    # can end up with zeros
    cols = set()
    rows = set()

    for row_index, row in enumerate(matrix):
        for col_index, val in enumerate(row):
            
            #keep track of rows and columns with 0
            if val == 0:
                rows.add(row_index)
                cols.add(col_index)

    # traverse matrix and set coord to zero
    # if row or col is in set
    for row_index, row in enumerate(matrix):
        for col_index, val in enumerate(row):
            if row_index in rows or col_index in cols:
                matrix[row_index][col_index] = 0

    return matrix


class Test(unittest.TestCase):
    m1 = [
        [0,1,1],
        [1,1,1],
        [1,1,1]
    ]
    m1_after = [
        [0,0,0],
        [0,1,1],
        [0,1,1]
    ]

    m2 = [
        [0,1,1,1],
        [1,1,1,1],
        [1,1,1,0]
    ]
    m2_after = [
        [0,0,0,0],
        [0,1,1,0],
        [0,0,0,0]
    ]

    m3 = [
        [1,1,1,1],
        [1,1,0,1],
        [1,1,1,1]
    ]
    m3_after = [
        [1,1,0,1],
        [0,0,0,0],
        [1,1,0,1]
    ]

    def test_set_zeros(self):
        self.assertEqual(set_zeros(Test.m1),Test.m1_after)
        self.assertEqual(set_zeros(Test.m2),Test.m2_after)
        self.assertEqual(set_zeros(Test.m3),Test.m3_after)

if __name__ == '__main__':
    unittest.main()
  • We can improve the space complexity to O(1)
  • Use the first row and the first col as flags
  • these flags indicate whether that row or col should be zero
  • Need to separately check if first row or col is zero
import unittest

def set_zeros2(matrix):
    #Time Complexity: O(MN)
    #Space Complexity: O(1)
    if not matrix:
        raise Exception("Matrix is empty")

    rows = len(matrix)
    cols = len(matrix[0])

    first_row_zero = False
    first_col_zero = False

    # check if zero is in first row
    if 0 in matrix[0]:
        first_row_zero = True

    # check if zero is in first column
    for row in matrix:
        if row[0] == 0:
            first_col_zero = True
            break

    for row_index in xrange(1,rows):
        for col_index in xrange(1, cols):
            # use the first row and the first col
            # to tell us if that row or column should
            # be set to zero
            if matrix[row_index][col_index] == 0:
                matrix[0][col_index] = 0
                matrix[row_index][0] = 0

    # go through each row
    for row_index in xrange(1, rows):
        #check if the first item of each row is zero
        if matrix[row_index][0] == 0:
            #if it is, set each item in that row to 0
            for col_index in xrange(1, cols):
                matrix[row_index][col_index] = 0

    # go through each column
    for col_index in xrange(1, cols):
        # check if first item in col is zero
        if matrix[0][col_index] == 0:
            # if it is, set each item in col to 0
            for row_index in xrange(1, rows):
                matrix[row_index][col_index] = 0

    # if first row was flagged to be zero set
    # all items in it to 0
    if first_row_zero:
        for col_index in xrange(0,cols):
            matrix[0][col_index] = 0

    # if first col was flagged to be zero set
    # all items in it to 0
    if first_col_zero:
        for row_index in xrange(0,rows):
            matrix[row_index][0] = 0

    return matrix

class Test(unittest.TestCase):
    m1 = [
        [0,1,1],
        [1,1,1],
        [1,1,1]
    ]
    m1_after = [
        [0,0,0],
        [0,1,1],
        [0,1,1]
    ]

    m2 = [
        [0,1,1,1],
        [1,1,1,1],
        [1,1,1,0]
    ]
    m2_after = [
        [0,0,0,0],
        [0,1,1,0],
        [0,0,0,0]
    ]

    m3 = [
        [1,1,1,1],
        [1,1,0,1],
        [1,1,1,1]
    ]
    m3_after = [
        [1,1,0,1],
        [0,0,0,0],
        [1,1,0,1]
    ]

    def test_set_zeros2(self):
        self.assertEqual(set_zeros2(Test.m1),Test.m1_after)
        self.assertEqual(set_zeros2(Test.m2),Test.m2_after)
        self.assertEqual(set_zeros2(Test.m3),Test.m3_after)

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

1.7 Rotate Matrix – CCI

  • rotate the matrix by layers
  • rotate one item at a time for each row/col
  • store top value
  • move left value to top, bottom value to left, right value to bottom and top value to right
  • go through each item in row/col
  • after layer is done do the layer underneath
# [1.7]. Given an image represented by an NxN matrix,
# where each pixel in the image is 4 bytes, write a method to 
# rotate the image by 90 degrees. Can you do this in place?

# Time complexity: O(N^2)
# Space complexity: O(1)

import unittest

def rotate_matrix(matrix):
    N = len(matrix)
    layers = N/2

    for layer in xrange(layers):
        for pos in xrange(layer, N - layer - 1):
            top = matrix[layer][pos]
            matrix[layer][pos] = matrix[N-pos-1][layer]
            matrix[N-pos-1][layer] = matrix[N-layer-1][N-pos-1]
            matrix[import unittest

def rotate_matrix(matrix):
    #input is in list of lists 
    #matrix[row][col]

    N = len(matrix)
    layers = N/2
    
    # rotate by layers
    # if number of layers is odd, don't need to rotate last one
    for layer in xrange(layers):

        # don't do the last pos because the first move
        # puts the initial first value of the row in the last place
        # pos traverses between rows for top and bottom 
        # and cols for left and right
        for pos in xrange(layer, N - layer - 1):
            
            #store the top value
            top = matrix[layer][pos]
            
            #override top value with left
            matrix[layer][pos] = matrix[N-pos-1][layer]
            
            #override left with bottom
            matrix[N-pos-1][layer] = matrix[N-layer-1][N-pos-1]
            
            #override bottom with right
            matrix[N-layer-1][N-pos-1] = matrix[pos][N-layer-1]
            
            #override right with stored top
            matrix[pos][N-layer-1] = top

    return matrix

class Test(unittest.TestCase):
    m1 = [[1,2],[3,4]]
    m1_rotated = [[3,1],[4,2]]

    m2 = [[1,2,3],[4,5,6],[7,8,9]]
    m2_rotated = [[7,4,1],[8,5,2],[9,6,3]]

    m3 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
    m3_rotated = [[13,9,5,1],[14,10,6,2],[15,11,7,3],[16,12,8,4]]

    def test_rotate_matrix(self):
        self.assertEqual(rotate_matrix(Test.m1), Test.m1_rotated)
        self.assertEqual(rotate_matrix(Test.m2), Test.m2_rotated)
        self.assertEqual(rotate_matrix(Test.m3), Test.m3_rotated)

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

REST

REST or Representational State Transfer refers to the architectural design style of the world wide web.

The name “representational state transfer” is intended to evoke an image of how a well-designed Web application behaves: a network of web pages (a virtual state-machine), where the user progresses through the application by selecting links (state transitions), resulting in the next page (representing the next state of the application) being transferred to the user and rendered for their use. -Representational state transfer (Wikipedia)

In order to be considered REST, it must follow some constraints.

Client Server – The network must be made up of clients that interact with servers which have resources. This involves one-to-one communication.

Stateless – The client and server do not need to keep track of the other’s state. Requests are not tracked.

Uniform Interface – There must be a common language between the client and server. Servers can change the underlying implementation without breaking clients. This encourages independent evolution. Resources are identified by URI and HTTP. Resources are manipulated through representation. Clients sends representations of what it wants changed, but ultimately the server makes the decision. Messages are self-descriptive e.g. a response can specify content-type as text/html. The server sends data to the client and lets it know what it can do next.

Others – Clients can cache responses and save trips. There can be multiple layers. Clients can receive executable code i.e. JavaScript.

Benefits of a RESTful architecture include flexibility and scalability.

 

 

Recursion

 

I’m currently working through the recursion chapter of Cracking the Coding Interview. Recursion is essentially using the same function repeatedly to solve smaller subsets of the initial data.

The Fibonacci numbers are a good example of this (i.e. 1, 1, 2, 3, 5, 8, 13…). Each number is the sum of the previous two numbers.

def fib(n):
    if n < 2:
        return 1
    return fib(n-1) + fib(n-2)

If we are trying to find the 4th fibonacci term, we would have to first find the 2nd and 3rd term and so on and so forth. Recursion only works if there is a base case that eventually returns something. In this example, when n is eventually 0 or 1, the value 1 will be returned.

Recurse Center

The Recurse Center is a three-month programming retreat based out of New York. It’s not a boot camp. It doesn’t have any teachers or a curriculum. It is mostly self-directed learning. RC makes money by helping its retreaters get jobs at their partner companies.

I recently went through the interview process and unfortunately was not accepted into their batch. It’s very disappointing, but I’ve to go put my head down and keep on grinding. Can’t let one no keep me down.

Asynchronous I/O

I’m learning about asynchronous I/O in the Node.js chapter of Eloquent JavaScript. I/O is input output. One way of handling I/O is reading and returning files once they are fully read (synchronous). This may cause a program to freeze up while it is still waiting for information.

An asynchronous interface allows scripts to continue running while it does other work and call a function (callback) after it is done.

 

Binary Digits

Binary Digits or Bits are numbers represented by 1’s and 0’s. Each value in a binary digit represents a power of two.

  • The first position represents 1  (2^0)
  • The second position represents 2 (2^1)
  • The third position represents 4 (2^2)
  • The fourth position represents 8 (2^3)
  • and so on and so forth

In binary, we count like below.

  • 1     –  one
  • 10   –  two
  • 11   –  three
  • 100 –  four
  • 101 –  five
  • 111 –  six

Each position can only hold 1’s or 0’s so when we want to add one to one, we carry a one to the next slot.

In a computer, all numbers are stored in bits.

 

Eloquent JavaScript Chapter 15

I’m currently working through chapter 15 of Eloquent JavaScript. The chapter walks through a project for making a simple mario-type game. Previously, if I had trouble understanding something, I would go through and write out all the code. I did that for this chapter, but I’m still trying to connect some of the pieces.

I’m going to keep grinding through for now, because I heard reading code helps you improve as a programmer. Plus, this is an opportunity to read code written and organized by someone who seems really accomplished and good at what he does.