Programming

Question 1

change bases

Answer 1

repeatably // by new base until 0, taking modulo and appending it to back of string each time

negatives should be abs and then “-“ inserted at front before return

Question 2

//

Answer 2

floor division

Question 3

DFS

Answer 3

Mark the current vertex as being visited.
Explore each adjacent vertex that is not included in the visited set.

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

Question 4

BFS

Answer 4

Explore first in queue not just adjacent

First path is one of the shortest (if path cost is number of edges)

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

Question 5

Dijsktra

Answer 5

Make visited dict - node:dist with start initialized to dist 0
Make path dict
Make set of all nodes
While items in set
Find minimum node in visited
If no min node, break done
Remove min node from set of all nodes
Set current weight to min node dist
For all neighbors of min node
Weight = current weight + weight of this edge
If neighbor not in visited OR weight < visited[edge]
Visited[neighbir] = weight
Path[neighbir] = minimum node

def dijsktra(graph, initial):
  visited = {initial: 0}
  path = {}

nodes = set(graph.nodes)

  while nodes: 
    min_node = None
    for node in nodes:
      if node in visited:
        if min_node is None:
          min_node = node
        elif visited[node] < visited[min_node]:
          min_node = node

if min_node is None:
  break

nodes.remove(min_node)
current_weight = visited[min_node]

for edge in graph.edges[min_node]:
  weight = current_weight + graph.distance[(min_node, edge)]
  if edge not in visited or weight < visited[edge]:
    visited[edge] = weight
    path[edge] = min_node

return visited, path

Question 6

DFS with goal node

Answer 6

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

Question 7

BFS with goal node

Answer 7

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

Question 8

Shortest path BFS

Answer 8

def shortest_path(graph, start, goal):
    try:
        return next(bfs_paths(graph, start, goal))
    except StopIteration:
        return None

Question 9

Permutations any list

Answer 9

takes all elements from the sequence, order matters

items[:i]+items[i+1]

def xcombinations(items, n):
    if n==0: yield []
    else:
        for i in range(len(items)):
            for cc in xcombinations(items[:i]+items[i+1:],n-1):
                yield [items[i]]+cc

def xpermutations(items):
    return xcombinations(items, len(items))

Question 10

Combinations any list

Answer 10

takes n distinct elements from the sequence, order matters

items[:i]+items[i+1:]

def xcombinations(items, n):
    if n==0: yield []
    else:
        for i in range(len(items)):
            for cc in xcombinations(items[:i]+items[i+1:],n-1):
                yield [items[i]]+cc

Question 11

Unique comibnations any list

Answer 11

takes n distinct elements from the sequence, order is irrelevant

items[i+1:]

def xuniqueCombinations(items, n):
    if n==0: yield []
    else:
        for i in range(len(items)):
            for cc in xuniqueCombinations(items[i+1:],n-1):
                yield [items[i]]+cc

Question 12

Selections any list

Answer 12

takes n elements (not necessarily distinct) from the sequence, order matters

items

def xselections(items, n):
    if n==0: yield []
    else:
        for i in range(len(items)):
            for ss in xselections(items, n-1):
                yield [items[i]]+ss

Question 13

insertion sort

Answer 13

def insertionSort(alist):
   for index in range(1,len(alist)):

 currentvalue = alist[index]
 position = index

 while position>0 and alist[position-1]>currentvalue:
     alist[position]=alist[position-1]
     position = position-1

 alist[position]=currentvalue

Question 14

Simple Graph rep Python

Answer 14

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Question 15

Stack

Answer 15

Collection

Push and pop

Peek access to too without changing

Last in first out

LIFO queue

Question 16

Queue

Answer 16

FIFO

Enqueue add to end
Dequeue removal from front

Question 17

Binary tree

Answer 17

Left and right

Left < right

Add: recursive call with left if < current left, right if right > current right, if left or right is none then assign

Find: recursive call with left if val < node.val, right if val > node.val, return node if equal.

Question 18

binary search

Answer 18

min and max, floor division, -1 if searching lower, +1 if searching higher, first max value -1 in python

def binary_search(seq, t):
    min = 0
    max = len(seq) - 1
    while True:
        if max < min:
            return -1
        m = (min + max) // 2
        if seq[m] < t:
            min = m + 1
        elif seq[m] > t:
            max = m - 1
        else:
            return m