User:Jimmy Novik/Python

Python Code Snippets

Past Experience

Remote Patient Monitoring at Covidien/Medtronic

• .NET MVC Framework
• WebServices Access via Web Bridge Library Responsible for Abstraction of Web Services
• Asynchronous Data Display via AJAX

Big-Data: Cashtag-CU

• EC2 Elastic Cloud
• Node.js
  • V8 Engine
  • Non-blocking Event Queue/Loop
  • JavaScript
  • NPM Manager + Easy Command Line Tools
  • Express Server
  • MongoDB Driver
• Webgl Libraries (Three.js, Tween.js)
• MongoDB
  • Document Based
  • Scalable

BigO Complexity

Data Structures

	Access (Time, Average)	Search	Insertion	Deletion	Access (Time, Worst)	Search	Insertion	Deletion	Space Complexity (Worst)
Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)	O(n)

Graph Operations

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency List	V|+|E|)	O(1)	O(1)	V|+|E|)	E|)	V|)
Incidence List	V|+|E|)	O(1)	O(1)	E|)	E|)	E|)
Adjacency Matrix	V|^2)	V|^2)	O(1)	V|^2)	1|)	1|)
Incidence Matrix	V|*|E|)	V|*|E|)	V|*|E|)	V|*|E|)	V|*|E|)	E|)

Clever Tricks in Python

Generating a Dictionary with Keys Set to Alphabetic Characters

import string
d = dict.fromkeys(string.ascii_lowercase, 0)

Flattening Lists

>>> a = [[1, 2], [3, 4], [5, 6]]
>>> list(itertools.chain.from_iterable(a))
[1, 2, 3, 4, 5, 6]

Iterating over Dictionary Key and Value Pairs

>>> m = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
>>> for k, v in m.iteritems():
...     print '{}: {}'.format(k, v)

System Design

GFS

• Google File System

Map Reduce

• Map Reduce Picture
• MST Using Map Reduce

What

• Programming Model

Why

• To Process & Generate Large Data Sets *

Key Terms

• Map Function

(k1, v1) -> list(k2, v2)

• Reduce Function

(k2, list(v2)) -> list(v2)

• reduce hash (hash(key)modR)
• input split (64MB)
• Master (Chooses Workers)
  • Master Knows What Tasks Have to be Done the Workers at any Time
  • Checkpoints
  • Partitioning Function
• Worker (Parses and Buffers)
• Atomic Commits
• Stragglers
• Ordering Guarantee
• Combiner Function (Combines Intermediate Keys)
• Local Execution
• Status Info

Sorting

Bubble Sort

def bubbleSort(array):
    for i in range(len(array)-2, 0, -1):
        for j in range(i+1):
            if array[j+1] < array[j]:
                temp = array[j+1]
                array[j+1] = array[j]
                array[j] = temp

Insertion Sort

import random

def insertionSort(array):
    for j in range(1, len(array)):
        key = array[j]
        i = j-1
        while i>-1 and array[i]>key:
            array[i+1] = array[i]
            i -= 1
        array[i+1]=key
    

Heapsort

CLRS VERSION

import math

## NOTE TO SELF:
## What makes this implementation difficult, is
## that it you have to pay attention to indices.
## To find children and parents you have to mutiply and devide,
## and to make sure that you are not multiplying 0 by 2 (which
## gives 0) you have to watch for indices...

class MaxHeap:
    def __init__(self, array):
        self.array = array
        self.heapsize = len(array)

    def buildMaxHeap(self):
        for i in range(len(self.array), 0, -1):
            self.maxHeapify(i)
            
    def heapsort(self):
        self.buildMaxHeap()
        for i in range(len(self.array), 1, -1):
            self.swap(1, i)
            self.heapsize = self.heapsize - 1
            self.maxHeapify(1)
            
    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)

        if l <= self.heapsize and self.array[l-1] > self.array[i-1]:
            largest = l
        else:
            largest = i
            
        if r <= self.heapsize and self.array[r-1] > self.array[i-1]:
            if self.array[r-1] > self.array[largest-1]:
                largest = r

        if largest != i:
            self.swap(largest, i)
            self.maxHeapify(largest)

    ## PRIORITY QUEUE

    def heapMaximum(self):
        self.heapsort()
        return self.array[0]

    def heapExtractMax(self):
        if self.heapsize < 1:
            return "Error: Heap Underflow"
        maxVar = self.array[0]
        self.array[0] = self.array[self.heapsize-1]
        self.heapsize = self.heapsize - 1
        self.maxHeapify(1)
        return maxVar
        
    def heapIncreaseKey(self, i, key):
        if key < self.array[i-1]:
            print("Error: new key is smaller than current key")
        self.array[i-1] = key
        while i > 1 and self.array[self.parrent(i)-1] < self.array[i]:
            self.swap(i, self.parent(i))
            i = self.parent(i)

    def maxHeapInsert(self, key):
        self.heapsize = self.heapsize + 1
        self.array[self.heapsize] = -100000
        self.heapIncreaseKey(self, self.heapsize, key)
        
    ## AUXILARY        

    def parent(self, i):
        return math.floor(i/2)

    def left(self, i):
        return 2*i

    def right(self, i):
        return 2*i + 1

    def swap(self, i, j):
        temp = self.array[i-1]
        self.array[i-1] = self.array[j-1]
        self.array[j-1] = temp

mh = MaxHeap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7])
mh.buildMaxHeap()
print(mh.array)

Other Version

def HeapSort(A):
    def heapify(A):
        start = (len(A) - 2) / 2
        while start >= 0:
            siftDown(A, start, len(A) - 1)
            start -= 1

    def siftDown(A, start, end):
        root = start
        while root * 2 + 1 <= end:
            child = root * 2 + 1
            if child + 1 <= end and A[child] < A[child + 1]:
                child += 1
            if child <= end and A[root] < A[child]:
                A[root], A[child] = A[child], A[root]
                root = child
            else:
                return

    heapify(A)
    end = len(A) - 1
    while end > 0:
        A[end], A[0] = A[0], A[end]
        siftDown(A, 0, end - 1)
        end -= 1

if __name__ == '__main__':
    
    T = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10] 

    HeapSort(T)
    print(T)

Quicksort

import random

list_to_sort = [x for x in range(10000)]
random.shuffle(list_to_sort)

class quickSort:
    def __init__(self, list_to_sort):
        self.list = list_to_sort;

    def swap(self, index01, index02):
        temp = self.list[index01]
        self.list[index01] = self.list[index02]
        self.list[index02] = temp

    def sort(self, wall, pivot):
        new_wall, pointer = wall, wall

        if (pivot - wall <= 0): return

        while (pivot != pointer):
            if (self.list[pointer] >= self.list[pivot]):
                pointer += 1
            else:
                self.swap(new_wall, pointer)
                new_wall = new_wall + 1
                pointer += 1

        self.swap(new_wall, pivot)
        self.sort(wall, new_wall-1)
        self.sort(new_wall+1, pivot)
        return

print("Before:", list_to_sort)
quickSort = quickSort(list_to_sort)
quickSort.sort(0, len(list_to_sort)-1)
print("After:", quickSort.list)

Merge Sort

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Hashtables

Open Adressing

hashTable = {1:[], 2:[], 3:[], 4:[], 5:[], 6:[], 7:[], 8:[], 9:[]}

def openAddressing(hashTable, value):
    key = value % len(hashTable)
    memo = key
    while(len(hashTable[key]) != 0):
        key = (key + 1) % len(hashTable)
        print(key)
    if (len(hashTable[key]) == 0):
        hashTable[key].append(value)
        return hashTable
    else:
        return hashTable

print(openAddressing(openAddressing(hashTable, 9), 8))

Trees

AVL Tree

Height Balanced Tree https://www.youtube.com/watch?v=YKt1kquKScY

Binary Tree

• Preorder Traversal

• Inorder Traversal

• Postorder Traversal

• Level Traversal

from collections import namedtuple

from sys import stdout


Node = namedtuple('Node', "data, left, right")

tree = Node(1,

            Node(2,

                 Node(4,

                      Node(7, None, None),

                      None),

                 Node(5, None, None)),

            Node(3,

                 Node(6,

                      Node(8, None, None),

                      Node(9, None, None)),

                 None))


def printwithspace(i):

    stdout.write("%i " % i)


def preorder(node , visitor = printwithspace):

    if node is not None:

        visitor(node.data)

        preorder(node.left, visitor)

        preorder(node.right, visitor)

preorder(tree)

N-ary Tree

In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.

Red-Black Tree

Rules

1. A node is either red or black
2. The root is black
3. All leaves (NIL) are black
4. Every red node must have two black child nodes, and therefore it must have a black parent
5. Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes

Trie

Graphs

CLRS Style

class Vertex:
    def __init__(self, name):
        self.name = name
        self.edges = []
        self.color = "white"
        self.distance = 100000
        self.predecessor = None
        self.d = 0
        self.f = 0
        
    def createEdge(self, vertex):
        if vertex not in self.edges:
            self.edges.append(vertex)

class Graph:
    def __init__(self, graph):
        self.graph = graph
        self.time = 0

    def DFS(self):
        for u in self.graph:
            u.color = "white"
            u.predecessor = None
        time = 0
        for u in self.graph:
            if u.color == "white":
                self.dfsVisit(u)

    def dfsVisit(self, u):
        self.time = self.time + 1
        u.d = self.time
        u.color = "gray"
        for v in u.edges:
            if v.color == "white":
                v.predecessor = u
                self.dfsVisit(v)
        u.color = "black"
        self.time = self.time + 1
        u.f = self.time
            

    def BFS(self):
        s = self.graph[0]
        s.color = "gray"
        s.distance = 0
        s.predecessor = None
        q = [s]
        print(s.name)
        while len(q) != 0:
            u = q.pop(0)
            for vertex in u.edges: 
                if vertex.color=="white":
                    print(vertex.name, vertex.color)
                    vertex.color="gray"
                    vertex.distance=u.distance + 1
                    vertex.predecessor=u
                    q.append(vertex)
                    
            u.color = "black"
                
                        


a = Vertex("A")
b = Vertex("B")
c = Vertex("C")
d = Vertex("D")
a.createEdge(b)
a.createEdge(c)
b.createEdge(c)
c.createEdge(d)
d.createEdge(c)
graph = [a, b, c, d]
g = Graph(graph)
g.DFS()
for i in graph:
    print(i.d, i.f)

Strongly Connected Component

The most important thing here to remember is that second time you do DFS on the graph, you have to visit vertices in order of their finish times.

def sccDFS(self):
        components = []
        for u in self.graph:
            u.color = "white"
            u.predecessor = None
        time = 0
        for u in self.graph:
            if u.color == "white":
                component = self.sccDfsVisit(u, [u.name])
                components.append(component)
        return components
            
    def sccDfsVisit(self, u, scc):
        result = scc
        self.time = self.time + 1
        u.d = self.time
        u.color = "gray"
        for v in u.edges:
            if v.color == "white":
                v.predecessor = u
                result = self.sccDfsVisit(v, scc + [v.name])
        u.color = "black"
        self.time = self.time + 1
        u.f = self.time
        return result

Graph as a Dictionary

from collections import namedtuple
from sys import stdout

graph = {'A': ['B', 'C'],\
         'B': ['C', 'D'],\
         'C': ['D'],\
         'D': ['C'],\
         'E': ['F'],\
         'F': ['C']}

def find_path(graph, start, end, path=[]):

    path = path + [start]

    if start == end:
        return path
    if not start in graph:
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath: return newpath
    return None

print(find_path(graph, 'F', 'C', []))

def bfs(graph, start_node):
    seen = {}
    queue = []
    queue.append(start_node)
    seen[start_node] = True
    while (len(queue) != 0):
        i = queue.pop(0)
        print(i)
        for j in graph[i]:
            if j not in seen:
                queue.append(j)
                seen[j] = True
    return seen

print("BFS: ", bfs(graph, 'A'))

def dfs(graph, start_node):
    seen = {}
    stack = []
    stack.append(start_node)
    seen[start_node] = True
    while (len(stack) != 0):
        i = stack.pop(-1)
        print(i)
        for j in graph[i]:
            if j not in seen:
                stack.append(j)
                seen[j] = True
    return seen

print("DFS: ", dfs(graph, 'A'))

Graph as a Matrix

graph_matrix = [\
    #A  B  C  D  E  F
    [0, 1, 1, 0, 0, 0],\
    [0, 0, 1, 1, 0, 0],\
    [0, 0, 0, 1, 0, 0],\
    [0, 0, 1, 0, 0, 0],\
    [0, 0, 0, 0, 0, 1],\
    [0, 0, 1, 0, 0, 0],\
]

class graphMatrix:
    def __init__(self, graph_matrix):
        self.matrix = graph_matrix
        self.seen = {0: False, 1: False, 2: False, 3: False, 4: False, 5: False}
        self.stack = []

    def dfs(self, start_node_index):
        self.stack = []
        self.seen[start_node_index] = True
        self.stack.append(start_node_index)
        while(len(self.stack) != 0):
            temp_element = self.stack.pop()
            for node in range(0, 6):
                print(node)
                if (self.matrix[temp_element][node] == 1 and self.seen[node] == False):
                    self.seen[node] = True
                    self.stack.append(node)
            print(self.seen)
            print(self.stack)
        return

graphMatrix = graphMatrix(graph_matrix)
graphMatrix.dfs(0)
print(graphMatrix.seen)

Queue

class Queue:
    def __init__(self):
        self.items = []
        self.minimumValue = float("inf")

    def isEmpty(self):
        return (self.items == [])

    def enqueue (self, item):
        self.items.insert(0, item)
        if (item < self.minimumValue):
            self.minimumValue = item

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

Bellman-Ford Single Source Shortest Path

def initializeSingleSource(G, s)
    for vertex in G.vertices:
        vertex.d = float("inf")
        vertex.p = None
    s.d = 0

def BellmanFord(G, w, s)
    initializeSingleSource(G, s)
    for vertex in G.vertices:
        for edge in G.edges:
            relax(u, v, w)
    for edge in G.edges:
        if edge[v].d > edge[u].d + edge.w
            return False
    return True

Dijkstra Non-Negative Edges Single Source Shortest Path

def Dijkstra(G,w,s):
    initializeSingleSource(G,s)
    S = []
    Q = G.vertices
    while len(Q) != 0:
        u = extractMin(Q)
        S = S + [u]
        for vertex v in G.adj[u]:
            relax(u, v, w)

NP-Completeness

Categories

NP-hard problems do not have to be elements of the complexity class NP. As NP plays a central role in computational complexity, it is used as the basis of several classes:

NP

Class of computational problems for which a given solution can be verified as a solution in polynomial time by a deterministic Turing machine.

NP-hard

Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.

NP-complete

Class of problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.

NP-easy

At most as hard as NP, but not necessarily in NP, since they may not be decision problems.

NP-equivalent

Problems that are both NP-hard and NP-easy, but not necessarily in NP, since they may not be decision problems.

NP-intermediate

If P and NP are different, then there exist problems in the region of NP that fall between P and the NP-complete problems. (If P and NP are the same class, then NP-intermediate problems do not exist.)

Operating Systems

Locks

Used when the same resource can be accessed from several places, use synchronized otherwise

import asyncio

async def coro(name, lock):
    print('coro {}: waiting for lock'.format(name))
    async with lock:
        print('coro {}: holding the lock'.format(name))
        await asyncio.sleep(1)
        print('coro {}: releasing the lock'.format(name))

loop = asyncio.get_event_loop()
lock = asyncio.Lock()
coros = asyncio.gather(coro(1, lock), coro(2, lock))
try:
    loop.run_until_complete(coros)
finally:
    loop.close()

Semaphores

• Mutex Semaphore (Lock)
• Counting Semaphore (lets several threads access same resource)
• Event Semaphores (notifies all waiting threads)

Monitors

Set of routines protected by a mutual exclusion lock that handle all the details of lock acquisition and release

Deadlock

Conditions

• Mutual Exclusion
• Hold and Wait
• No Preemption
• Circular Wait

Dynamic Programming

Listing Elements in Binary Tree Fashion

import math

class List:
    def __init__(self):
        self.array = [1, 2, 3, 4, 5, 6, 7]
    def traverse(self):
        self.traverse_helper(0, len(self.array)-1)
    def traverse_helper(self, start, end):
        array = self.array[start:end+1]
        middle = math.floor(len(array)/2)

        #base cases
        if len(array) == 0:
            return
        elif len(array) == 1:
            print(array[0])
            return
        
        #recursion
        else:
            for i in range(1):
                self.traverse_helper(start+middle, end)
                self.traverse_helper(start, start+middle-1)     

        
l = List()
l.traverse()

Binary Search

import math

class BinarySearch:
    def __init__(self):
        self.array = [1, 2, 3, 4, 5, 6, 7, 8]

    def search(self, value):
        print(self.search_helper(value, 0, len(self.array)-1));

    def search_helper(self, value, start, end):
        array = self.array[start:end+1]
        middle = math.floor(len(array)/2)
        
        #base cases: *** don't forget the case where you have one element and it is not what you are looking for!
        if len(array) == 0:
            return False;
        if array[middle] == value:
            return True
        if len(array) == 1 and array[0] == value:
            return True
        elif len(array) == 1 and array[0] != value:
            return False

        #recursion
        else:
            if (value < array[middle]):
                return self.search_helper(value, start, start+middle-1) #start + middle super easy to forget! 
            elif (value > array[middle]):
                return self.search_helper(value, start+middle, end)
            else:
                return False

All Subsets of a Set

Note to Self!

When thinking about how to solve a problem using dynamic programming think about what solution your function is going to produce, and use those solutions as your base cases. For example, in this problem you are looking at a set with no elements, which will give you []... then you look at a set with a1 element, which will give you [[], [a1], then you look add another one (a2), which will give you [[]. [a1], [a2], [a1, a2]]. It is easy to see a pattern here. But if you look let say at only one solution with three elements and thinking "ok, I have to combine first element with another one, and it will give me..." it will not get you anywhere...

class SetBuilder:
    def __init__(self, array):
        self.array = array

    def findAllSubsets(self):
        result = self.findAllSubsetsHelper(0, [])
        print(len(result), result)
        
    def findAllSubsetsHelper(self, index, results):
        if index == len(self.array)+1:
            return results
        else:
            if len(results) == 0:
                results.append([])
            else:
                temp_results = results[:]
                for subset in temp_results:
                    new_subset = subset[:]
                    new_subset.append(self.array[index-1])
                    results.append(new_subset)
        return self.findAllSubsetsHelper(index+1, results)

sb = SetBuilder(["a", "dog", "cat"])
sb.findAllSubsets()

All Possible Permutations

deg getPerms(str):
  print(str)
  
  if (str == None):
    return None
  
  if str == "":
    permutations.append("")
    return permutations
  
  first = str[0]
  words = getPerms(str[1:])
  for word in words:
  for j in range(len(word) + 1):
      s = insertCharAt (word, first, j)
      permutations.append(s)
  return permutations

All Legitimate Parentheses Permutations

def addParen(list_input, left_remaining, right_remaining, string_input, count):
    if left_remaining < 0 or left_remaining > right_remaining:
        return
    if left_remaining == 0 and right_remaining == 0:
        print(string_input)
    else:

        string_input[count:count+1] = b"("
        addParen(list_input, left_remaining - 1, right_remaining, string_input, count + 1)

        string_input[count:count+1] = b")"
        addParen(list_input, left_remaining, right_remaining - 1, string_input, count + 1)
    
    test_list = [];
    num = 3
    addParen(test_list, num, num, bytearray((b""*num)), 0)
    print(test_list)

8 Queens

Note to Self: Don't Return if You are Iterating withing a Recursive Function, and if You Want to Return a Result Array, Don't Append Arrays to It, Append Strings!

import math

def placeQueens(row, columns, results): 
    if (row == 8):
        results.append(columns)
        print(results)
    else:
        for col in range(8):
            if (checkValid(columns, row, col)):
                columns[row] = col;
                placeQueens(row + 1, columns, results)
                columns[row] = -1

def checkValid(columns, row1, column1):
    for row2 in range(row1):
        column2 = columns[row2]
        if column1 == column2:
            return False
        columnDistance = abs(column2 - column1)
        rowDistance = row1-row2
        if columnDistance == rowDistance:
            return False
    return True

placeQueens(0, [-1, -1, -1, -1, -1, -1, -1, -1], [])
    

Binary Representation

Iterate Through Every Bit

number = 19

num_bits = 8
bits = [(number >> bit) & 1 for bit in range(num_bits - 1, -1, -1)]

OO Design and Design Patterns

S.O.L.I.D.

Initial	Stands for (acronym)	Concept
S	SRP	Single responsibility principle a class should have only a single responsibility (i.e. only one potential change in the software's specification should be able to affect the specification of the class)
O	OCP	Open/closed principle “software entities … should be open for extension, but closed for modification.”
L	LSP	Liskov substitution principle “objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program.” See also design by contract.
I	ISP	Interface segregation principle “many client-specific interfaces are better than one general-purpose interface.”
D	DIP	Dependency inversion principle one should “Depend upon Abstractions. Do not depend upon concretions.”

Singleton

class Singleton:
    def __init__(self):
        self.firstInstance = None;

    def getInstance(self):
        if (self.firstInstance == None):
            self.firstInstance = Singleton() #lazy instantiation
        return self.firstInstance


s = Singleton()
print(s.getInstance())

Factory

# returns on of several possible classes
# that share a common super class (create an enemy in a game)
# (When you don't know ahed of time what class object you need)
class EnemyShip:
    def __init__(self):
        self.name = ""
        self.amtDamage = 0

    def getName(self):
        print(self.name)
        return self.name

    def setName(self, newname):
        self.name = newname

class UFOEnemyShip(EnemyShip):
    def __init__(self):
        self.setName("UFO Enemy Ship")

class RocketEnemyShip(EnemyShip):
    def __init__(self):
        self.setName("Rocket Enemy Ship")

class EnemyShipFactory:
    def __init__(self):
        self.object = None
    def makeEnemyShip(self, shipType):
        if "u" in shipType or "U" in shipType:
            return UFOEnemyShip()
        elif "r" in shipType or "R" in shipType:
            return RocketEnemyShip()
        return None

ufoShipFactory = EnemyShipFactory()
test = ufoShipFactory.makeEnemyShip("u")
test.getName()

Iterator

class SongInfo:
    def __init__(self, songName, bandName, year):
        self.songName = songName
        self.bandName = bandName
        self.year = year

    def getSongName(self):
        return self.songName

    def getBandName(self):
        return self.bandName

    def getYearReleased():
        return self.year

class songsOfThe70s:
    def __init__(self):
        self.bestSongs = []
        self.addSong("Imagine", "John Lennon", 1971)
        self.addSong("American Pie", "Don McLean", 1971)
        self.addSong("I Will Survive", "Gloria Gaynor", 1979)
    def addSong(self, songName, bandName, yearReleased):
        songInfo = SongInfo(songName, bandName, yearReleased)
        self.bestSongs.append(songInfo)
    def getBestSongs(self):
        return self.bestSongs

class songsOfThe80s:
    def __init__(self):
        self.bestSongs = {}
        self.addSong("Imagine2", "John Lennon", 1971)
        self.addSong("American Pie2", "Don McLean", 1971)
        self.addSong("I Will Survive2", "Gloria Gaynor", 1979)
    def addSong(self, songName, bandName, yearReleased):
        songInfo = SongInfo(songName, bandName, yearReleased)
        self.bestSongs[songName] = songInfo
    def getBestSongs(self):
        return self.bestSongs

class DJ:
    def __init__(self, array, hash):
        self.songs70 = array
        self.songs80 = hash

    def showSongs(self):
        #itterate through these datatypes accordingly
        

s = songsOfThe70s()
for i in s.getBestSongs():
    print(i.songName)

Observer

# Itterator is needed when many objects need
# to receive info about a change

class Subject:
    def __init__(self, ibm, apple, google):
        self.observers = []
        self.ibm = ibm
        self.apple = apple
        self.google = google
        
    def register(self, observer):
        self.observers.append(observer)
        print("Observer " + str(len(self.observers)-1) + " was added")

    def unregister(self, observer):
        print("Observer " + str(self.observers.index(observer)) + " was removed")
        self.observers.remove(observer)

    def notifyObserver(self):
        for observer in self.observers:
            observer.update(self.ibm, self.apple, self.google)

    def setIBMPrice(self, ibm):
        self.ibm = ibm
        self.notifyObserver()

    def setApplePrice(self, apple):
        self.apple = apple
        self.notifyObserver()

    def setGooglePrice(self, google):
        self.google = google
        self.notifyObserver()

class Observer:
    def __init__(self):
        self.ibm = 0
        self.apple = 0
        self.google = 0
        
    def update(self, ibm, apple, google):
        self.ibm = ibm
        self.apple = apple
        self.google = google
        print("Updated: ", ibm, apple, google)

observer01 = Observer()
observer02 = Observer()
observer03 = Observer()
subject = Subject(100, 200, 300)
subject.register(observer01)
subject.register(observer02)
subject.register(observer03)
subject.setIBMPrice(1000)
subject.setGooglePrice(99999)

Decorator

# Decorator is more flexible than inheritence
# Allows to modify objects dynamically

class Pizza:
    def __init__(self, name, cost):
        self.name = name
        self.cost = cost
        
    def getDescription(self):
        return self.name

    def getCost(self):
        return self.cost

class ToppingDecorator:
    def __init__(self, pizza):
        self.tempPizza = pizza

    def getDescription(self):
        return self.tempPizza.getName()

    def getCost(self):
        return self.tempPizza.getCost()

class Mozzarella(ToppingDecorator):
    def __init__(self, pizza):
        self.tempPizza = pizza
        print("Adding Dough", "Adding Mozzarella")

    def getDescription(self):
        return self.tempPizza.getDescription() + ", Mozzarella"

    def getCost(self):
        return self.tempPizza.getCost() + 10

class TomatoSauce(ToppingDecorator):
    def __init__(self, pizza):
        self.tempPizza = pizza
        print("Adding Tomato Sauce")

    def getDescription(self):
        return self.tempPizza.getDescription() + ", Tomato Sauce"

    def getCost(self):
        return self.tempPizza.getCost() + 20

pi = TomatoSauce(Mozzarella(Pizza("Cheese", 5)))
print(pi.getDescription())

Programming Questions

Basics

What are the types in C, Java, C++, Perl? How many bits does it take to represent the basic types?

• C
  • short int: 16 bits
  • unsigned short int: 16 bits
  • unsigned int: 32 bits
  • int: 32 bits
  • long int: 32 bits
  • signed char: 8 bits
  • unsigned char: 8 bits
  • float: 32 bits
  • double: 64 bits
  • long double: 128 bits

• Java
  • byte
  • short
  • int
  • long
  • float
  • double
  • boolean
  • char
  • reference
  • literal

• Python
  • integers
  • float
  • strings
  • tuples
  • lists
  • dictionaries

What do floating point numbers look in memory? Specifically, how many bits are there in a double and what sequence to the bits appear in?

• Sign Bit: 1
• Exponent: 8/11
• Mantissa: 23/52

What is two's complement notation?

Way of representing negative and positive numbers in bits.

How would you implement a bit-vector class?

?

Does the check x == x + 1 always return false for integer x?

No, in the left associative languages it would return True

What dose a C struct look like in memory? What does a C++ object look like in memory? What does a Java object look like in memory?

vtables and contiguous chunks of certain length

What is the difference between an interpreted and a compiled language?

Compiled language gets translated directly into assembly code, but the interpreted languages are translated into precompiled bits of code.

What is garbage collection?

Purge of Heap

How would you determine if call stack grows up or down relative to memory addresses?

print address of vars in nested functions

Give an example of a memory leak in Java?

?

What is tail recursion? How can it be removed automatically?

Some languages recognize this and implement "proper tail calls" or "tail call elimination": if they see a recursive call in tail position, they actually compile it into a jump that reuses the current stack frame instead of calling the function normally.

Is the natural recursive program for computing n! tail recursive?

Yes

Is Python 10x Faster than C?

No. Interpreted high level languages are slower because there a lot of stuff on top of assembly.

What does an executable look like as a sequence of bytes?

"Assembly" instructions.

Libraries

Give an example of a function that is in the C standard library

• printf()
• scanf()
• cos(), sin()....

Testing

What was you last bug? What was your hardest bug?

My last bug: Lorenz Attractor implementation. Hardest bug: patient data won't be displayed in a web app because of the device internal id is not unique...

How would you debug a distributed program?

Make a designated book-keeper of states of variables (like a master node)

Program Works sometimes, but fails other times on the same input? Why?

This could be due to program using probabilistic functions or because of hardware issues, or possibly interference from other processes etc.

How would you determine where the program spends most of its time?

Use a profiler

Programming Language Implementation

Give an example of a language which cannot be parsed by any computer

English because it is ambiguous!

What problems does dynamic linkage solve? What problems does it introduce?

It prevents you from recompiling the whole program if the only thing you changed is a small function

What is a functional language?

Programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

What is a virtual function?

Function that is redefined in derived classes.

What is automatic garbage collection and how is it implemented?

reference counters (each allocated region knows how many references there are to it and is freed when 0), sweep algorithms (traversal of a directed graph)

What is a type-sage language?

"Well typed programs cannot go wrong." Robin Milner 1978. Meaningless programs won't run (C and C++ are not type safe, Java and C# are)

What is the difference between a lexer and parser?

• Lexer: lexical analysis (characters to tokens)
• Parser: semantics (tokens into statements)

Operating Systems

What is a system call?

Request of a service from an operating system's kernel by a program.

How is a system call different from a library call?

system calls - kernel; library calls - application;

What is a device driver?

Program that provides interface between a device and application/operating system.

What is livelock? What is deadlock? Examples

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

A real-world example of livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they both repeatedly move the same way at the same time.

Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can be repeatedly triggered. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action.

What is a race condition? What can you do to prevent races?

Race condition is when to threads try to modify same memory location. One has to either make code thread safe by mutual exclusion or not use threads at all.

Read from memory, disk, SSD

Read 1 MB sequentially from disk 20,000,000 ns 20 ms 80x memory, 20X SSD

Computer Architecture

What is pipelining? Describe a 5-stage pipeline

Way of processor to execute instructions (Similar to the car pipline

What is a multi-issue processor

Some machines now try to go beyond pipelining to execute more than one instruction at a clock cycle, producing an effective CPI < 1. This is possible if we duplicate some of the functional parts of the processor (e.g., have two ALUs or a register file with 4 read ports and 2 write ports),

What is the difference between a superscalar and VLIW processor? Where is each appropriate?

?

What is a multicore machine?

CPU Core (processing unit) and L1 Cache

What is the significance of the privileged bit?

Kernel Mode/ User mode

Systems

How does a web browser work? Autcompletion?

Parsers for HTML and DOM construction

How does internet work? Specifically describe the roles of the TCP/IP protocol, routers, and DNS

Routers connect local networks to other networks. DNS stores information about IPs associated with domain names. TCP/IP protocol is stateless. Has headers etc...