# cards

front: What is Hamming Code?
back:
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming(7,4)-code, and were invented by Richard Hamming in 1950. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors.


front: What does ELF stand for?
back:
Executable and Linkable Format.
It's a common standard file format for executables, object code, shared libraries, and core dumps.


front: What is code generation?
back:
Producing a translation from a high-level program to assembly code. (Linker and Archiver taker over from here to produce machine code)


front:
Write a function that reverses a linked list, with this argument: pointer to pointer to the head node.

back:
void reverse(node_t **head) {
  node_t *prev = NULL;
  node_t *current = *head;
  node_t *next = *head;

  while (current) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }

  *head = prev;
}


front: Delete a given value from a BST rooted at given node. Returns a pointer to node.
back:
bst_node* delete_value(bst_node* node, int value) {
  if (node == NULL)
    return node;

  if (value < node->value) {
    node->left = delete_value(node->left, value);
  } else if (value > node->value) {
    node->right = delete_value(node->right, value);
  } else { // found value

    if (node->left == NULL && node->right == NULL) {
      free(node);
      node = NULL;
    } else if (node->left == NULL) {
      bst_node* temp = node;
      node = node->right;
      free(temp);
    } else if (node->right == NULL) {
      bst_node* temp = node;
      node = node->left;
      free(temp);
    } else {
      // 2 children - get min node of right subtree
      int right_min = get_min(node->right);
      node->value = right_min;
      node->right = delete_value(node->right, right_min);
    }
  }

  return node;
}


front: Get the successor of a value in a BST rooted by given node. Returns int.
back:
int get_successor(bst_node* node, int value) {
  if (node == NULL)
    return -1;

  bst_node* target = node;

  while (target->value != value) {
    if (value < target->value) {
      target = target->left;
    } else if (value > target->value) {
      target = target->right;
    }
  }

  // arrived at target node
  if (target->right != NULL) {
    // get min value of right subtree
    return get_min(target->right);
  } else {
    // get lowest ancestor that is a left child in the path to target value
    bst_node* successor = NULL;
    bst_node* ancestor = node;
    while (ancestor != NULL) {
      if (value < ancestor->value) {
        successor = ancestor;
        ancestor = ancestor->left;
      } else {
        ancestor = ancestor->right;
      }
    }

    return successor->value;
  }

}


front: Using recursion, insert a value into a tree: root = insert(node*, int)
back:
bst_node* insert(bst_node* node, const int value) {
  if (node == 0) {
    bst_node* new_node = malloc(sizeof(bst_node));
    if (new_node == NULL) {
      printf("Unable to allocate memory.");
      exit(0);
    }

    new_node->value = value;
    new_node->left = 0;
    new_node->right = 0;

    node = new_node;

    return node;
  }

  if (value < node->value) {
    node->left = insert(node->left, value);
  } else if (value > node->value) {
    node->right = insert(node->right, value);
  }

  return node;
}


front: Using an iterative approach, insert a value into a BST: insert(node*, int)
back:
void treeInsert(bst_node* node, int key) {
  bst_node* new_node;
  new_node = malloc(sizeof(*new_node));
  assert(new_node);

  new_node->key = key;
  new_node->left = 0;
  new_node->right = 0;

  while (1) {
    if (node->key > key) {
      if (node->left) {
        node = node->left;
      } else {
        node->left = new_node;
        return;
      }
    } else {
      if (node->right) {
        node = node->right;
      } else {
        node->right = new_node;
        return;
      }
    }
  }
}


front:
Write a method is_binary_search_tree that returns true if a given tree is a BST (use helper function).

back:
bool is_binary_search_tree(bst_node* node) {
  if (node == NULL) return true;

  return is_between(node, INT_MIN, INT_MAX);
}

bool is_between(bst_node* node, int min, int max) {
  if (node == NULL) return true;

  // ensure subtrees are not hiding a value lower or higher than the subtree
  // allows
  return node->value > min && node->value < max &&
         is_between(node->left, min, node->value) &&
         is_between(node->right, node->value, max);
}


front:
Using an iterative approach, write a function find_node(bst_node* root, int target) that returns the node with the given target value in a BST.

back:
bst_node* find_node(bst_node* root, int target) {
  while (root != NULL && root->key != target) {
    if (root->key > target) {
      root = root->left;
    } else {
      root = root->right;
    }
  }
  return root;
}


front:
Using an recursive approach, write a function: find_node(bst_node* node, int value) that returns the node with the given target value in a BST.

back:
bst_node* find_node(bst_node* node, int value) {
  if (node == NULL)
    return false;

  if (value < node->value) {
    return find_node(node->left, value);
  } else if (value > node->value) {
    return find_node(node->right, value);
  } else {
    return node;
  }
}


front: Function that returns the height (in nodes) of a BST: int get_height(bst_node* node)
back:
int get_height(bst_node* node) {
  if (node == NULL) {
    return 0;
  }

  return 1 + max_num(get_height(node->left), get_height(node->right));
}


front: How can build heap be done in linear time?
back:
A tree of size n nodes, will have floor(n/2^h) nodes with height >= h.
The last half of nodes will be leaves, so they already satisfy the heap property. No work needs to be done on them.
going bottom-up (ignoring the last n/2 items) and satisfying the heap property one level at a time, each level going up the tree has to do at most 1 operation more than the level below it. But as you go up the tree, higher levels have fewer nodes, so you may be doing more operations, but it happens on fewer number of times.
This resembles a series:

n/2 - height 1: 1 operations
n/4 - height 2: 2 operation
n/8 - height 3: 3 operations
...
going to floor(n/2^h) - height h: h operations

n * (1/2 + 2/4 + 3/8 + 4/16 ....) = n * 1 = n


front: C or Python: Sort an array of numbers using heap sort.
back:
void heap_sort(int* numbers, int count) {
  int temp;
  for (int i = count - 1; i > 0; --i) {
    temp = numbers[i];
    numbers[i] = numbers[0];
    numbers[0] = temp;

    percolate_down(numbers, i, 0);
  }
}

void heapify(int* numbers, int count) {
  for (int i = count / 2 - 1; i >= 0; --i) {
    percolate_down(numbers, count, i);
  }
}

void percolate_down(int* numbers, int count, int index) {
  while (index * 2 + 1 < count) {
    int swap_index = index;
    int left_child_index = index * 2 + 1;
    int right_child_index = index * 2 + 2;
    bool has_left_child = left_child_index < count;
    bool has_right_child = right_child_index < count;

    if (has_left_child && has_right_child) {
      if (numbers[left_child_index] > numbers[right_child_index]) {
        swap_index = left_child_index;
      } else {
        swap_index = right_child_index;
      }
    } else if (has_left_child) {
      swap_index = left_child_index;
    } else if (has_right_child) {
      swap_index = right_child_index;
    } else {
      break;
    }

    if (numbers[swap_index] > numbers[index]) {
      int temp = numbers[index];
      numbers[index] = numbers[swap_index];
      numbers[swap_index] = temp;

      index = swap_index;
    } else {
      break;
    }
  }
}


front: Write a function that calculates the Hamming distance.
back:
def hamming_distance(x, y):  
    difference = x ^ y
    count = 0
    while difference != 0:
        count += 1
        difference &= difference - 1
    return count


front: Write a function to calculate the Hamming weight of an integer. (Kernighan method)
back:
int countSetBits(int n) {
  int count = 0;

  while (n) {
    n = n & (n - 1);
    ++count;
  }

  return count;
}


front: Write a function that calculates the Hamming weight in constant time. Divide and Conquer strategy.
back:
int countSetBits(unsigned int n) {
  n = n - ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n + (n >> 4)) & 0x0F0F0F0F;
  n = n + (n >> 8);
  n = n + (n >> 16);

  return n & 0x0000003F;
}


front: Write a function to add 2 integers using bitwise operations.
back:
def add(a, b):
    while a:
        c = b & a
        b ^= a
        c <<= 1
        a = c
    return b


front:
Write a binary search function that works iteratively, taking a target int, array of ints, and size of the array, returning the index of the found item, or -1.

back:
int binary_search(int target, int numbers[], int size) {
  int low = 0;
  int high = size - 1;
  int mid = 0;
  while (low <= high) {
    mid = (high + low) / 2;

    if (target > numbers[mid]) {
      low = mid + 1;
    } else if (target < numbers[mid]) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
}


front:
Write a binary search function that works recursively, returning the index of the found item, or -1.

back:
int binary_search_recur(int target, int numbers[], int low, int high) {
  if (low > high) {
    return -1;
  }

  int mid = (high + low) / 2;

  if (target > numbers[mid]) {
    return binary_search_recur(target, numbers, mid + 1, high);
  } else if (target < numbers[mid]) {
    return binary_search_recur(target, numbers, low, mid - 1);
  } else {
    return mid;
  }
}


front:
In C or Python, Write a universal hashing function for a string, taking as arguments a string and the capacity of the hashtable.

back:
int hash(const char* key, const int m) {
  int hash = 0;

  for (int i = 0; i < key[i] != '\0'; ++i) {
    hash = hash * 31 + key[i];
  }

  return abs(hash % m);
}


front:
Describe the universal hashing function for an integer. What arguments would it need? What would it look like?

back:
/*
  key = the Key 
  a = random number from 1 to p-1
  b = random number from 0 to p-1
  p = a prime number >=m
  m = the size of the array
*/
int hash(int key, int a, int b, int p, int m) {
  return ((a * x + b) % p) % m;
}


front: What is a Binary Search Tree?
back:
A binary tree is a data structure where each node has a comparable key and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.


front: What is a red-black tree?
back:
BSTs having red and black links satisfying:
- Red links lean left
- No node has two links connected to it
- The tree has perfect black balance: every path from the root to a null link has the same number of blacks


front: What is a splay tree?
back:
A self-adjusting binary search tree where recently accessed elements are moved to the root so they are quick to access again.


front: What is a treap?
back:
A random priority is assigned to every key and must maintain two properties:
-They are in order with respect to their keys, as in a typical binary search tree
-They are in heap order with respect to their priorities, that is, no key has a key of lower priority as an ancestor
O(log N) expected time for all operations, O(N) worst case.


front: What is typical cache line size?
back:
64 bytes.

-- extra below --

To know the sizes, you need to look it up using the documentation for the processor, afaik there is no programatic way to do it. On the plus side however, most cache lines are of a standard size, based on intels standards. On x86 cache lines are 64 bytes, however, to prevent false sharing, you need to follow the guidelines of the processor you are targeting (intel has some special notes on its netburst based processors), generally you need to align to 64 bytes for this (intel states that you should also avoid crossing 16 byte boundries).

To do this in C or C++ requires that you use aligned_malloc or one of the compiler specific specifiers such as __attribute__((align(64))) or __declspec(align(64)). To pad between members in a struct to split them onto different cache lines, you need on insert a member big enough to align it to the next 64 byte boundery


front: What is latency?
back:
Latency is the delay from input into a system to desired outcome. The time interval between between a stimulus and response.


front: What is a y-fast trie?
back:
A y-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n) space, where n is the number of stored values and M is the maximum value in the domain. The structure was proposed by Dan Willard in 1982 to decrease the O(n log M) space used by an x-fast trie.


front: What is an x-fast trie?
back:
An x-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n log M) space, where n is the number of stored values and M is the maximum value in the domain. The structure was proposed by Dan Willard in 1982, along with the more complicated y-fast trie, as a way to improve the space usage of van Emde Boas trees, while retaining the O(log log M) query time.


front: What is a van Emde Boas tree?
back:
The van Emde Boas tree supports insertions, deletions, lookups, successor queries, and predecessor queries in time O(log log U), where U is the universe of items to store. Items are stored in clusters of size sqrt(U). 

The van Emde Boas data structure divides the range {0,...,n−1} into blocks of size sqrt(n), which we call clusters. Each cluster is itself a vEB structure of size sqrt(n). In addition, there is a “summary” structure that keeps track of which clusters are nonempty.

More detail:
A van Emde Boas tree (or van Emde Boas priority queue), also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O(log m) time, or equivalently in O(log log M) time, where M = 2m is the maximum number of elements that can be stored in the tree. The M is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree data-structures is often measured. The vEB tree has good space efficiency when it contains a large number of elements, as discussed below. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.


back: sed 's/ /\n/g' words.txt | sort
front:
Sed command to take a file separated by spaces, turn spaces into newlines, and then sort it alphabetically.


front: Write merge sort in C (check answer carefully)
back:
void merge(int numbers[], int low, int mid, int high) {
  // temp array for holding sorted items
  int b[high - low - 1];
  int i = low;
  int j = mid + 1;
  int k = 0;

  // merge items from list in order
  while (i <= mid && j <= high) {
    if (numbers[i] <= numbers[j]) {
      b[k++] = numbers[i++];
    } else {
      b[k++] = numbers[j++];
    }
  }

  // copy the remaining items to tmp array
  while (i <= mid) b[k++] = numbers[i++];
  while (j <= high) b[k++] = numbers[j++];

  --k;
  while (k >= 0) {
    numbers[low + k] = b[k];
    --k;
  }
}

void merge_sort(int numbers[], int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;

    merge_sort(numbers, low, mid);
    merge_sort(numbers, mid + 1, high);
    merge(numbers, low, mid, high);
  }
}


front: Write a MergeSort class in Python (check answer carefully)
back:
class MergeSort(object):
    def __init__(self, numbers):
        self.values = numbers
        self.count = len(numbers)

    def sort(self):
        self.merge_sort(0, self.count - 1)
        return self.values

    def merge_sort(self, low, high):
        if low < high:
            mid = (low + high) // 2

            self.merge_sort(low, mid)
            self.merge_sort(mid + 1, high)
            self.merge(low, mid, high)

    def merge(self, low, mid, high):
        b = []
        i = low
        j = mid + 1

        while i <= mid and j <= high:
            if self.values[i] <= self.values[j]:
                b.append(self.values[i])
                i += 1
            else:
                b.append(self.values[j])
                j += 1

        while i <= mid:
            b.append(self.values[i])
            i += 1

        while j <= high:
            b.append(self.values[j])
            j += 1

        for index, val in enumerate(b):
            self.values[low + index] = val


front: Write quick sort in C with only one method and random pivot (check answer carefully)
back:
void quick_sort(int numbers[], int left, int right) {

  if (left == right)
    return;

  int i = left;
  int j = right;
  int temp = 0;

  int count = right - left;
  int pivot_mod = rand() % count;

  int pivot = numbers[left + pivot_mod];

  while (i <= j) {
    while (numbers[i] < pivot) ++i;
    while (numbers[j] > pivot) --j;

    if (i <= j) {
      temp = numbers[i];
      numbers[i] = numbers[j];
      numbers[j] = temp;
      ++i;
      --j;
    }
  }

  if (left < j) {
    quick_sort(numbers, left, j);
  }

  if (right > i) {
    quick_sort(numbers, i, right);
  }
}


front: Write a QuickSort class in Python (check answer carefully)
back:
import random

class QuickSort(object):

    def __init__(self, numbers):
        self.values = numbers
        self.count = len(self.values)

    def sort(self):
        self.quick_sort(0, self.count - 1)
        return self.values

    def quick_sort(self, left, right):
        if left == right:
            return

        i = left
        j = right

        pivot_index = random.randint(left, right)

        pivot = self.values[pivot_index]

        while i <= j:
            while self.values[i] < pivot:
                i += 1
            while self.values[j] > pivot:
                j -= 1
            if i <= j:
                if i < j:
                    temp = self.values[i]
                    self.values[i] = self.values[j]
                    self.values[j] = temp
                i += 1
                j -= 1

        if left < j:
            self.quick_sort(left, j)
        if right > i:
            self.quick_sort(i, right)


front: How does perfect hashing handle collisions?
back:
It creates a second hash table in the buckets where there are multiple items (k), using a second hash function, and k^2 space. The hash table has two hashing levels. k^2 is chosen because the Markov inequality (birthday paradox) ensures we will not have collisions in bucket.


front: What are the downsides of using an adjacency matrix to represent a graph?
back:
Finding all the outgoing edges from a vertex takes O(n) time even if there aren't very many, and the O(n^2) space cost is high for "sparse graphs," those with much fewer than n^2 edges.


front: When is using an adjacency list expensive?
back:
Finding predecessors of a node u is extremely expensive, requiring looking through every list of every node in time O(n + e), where e is the total number of edges, although if this is something we actually need to do often we can store a second copy of the graph with the edges reversed.


front: When are adjacency lists most useful?
back:
Adjacency lists are most useful when we mostly want to enumerate outgoing edges of each node. This is common in search tasks, where we want to find a path from one node to another or compute the distances between pairs of nodes. If other operations are important, we can optimize them by augmenting the adjacency list representation; for example, using sorted arrays for the adjacency lists reduces the cost of edge existence testing to O(log(d+ (u))), and adding a second copy of the graph with reversed edges lets us find all predecessors of u in O(d− (u)) time, where d− (u) is u's in-degree.


front: What is the complexity of Dijkstra's shortest-path algorithm?
back:
O(e log v), where e is the number of edges. 
It must scan each edge, and gets and updates values on the heap.


front: How would you implement a queue with a linked list?
back:
Use a tail pointer. Push new items at the tail, pop items at the head. Both operations are constant-time.


front: What can use to find if a graph is bipartite?
back:
BFS. Using only 2 colors. When you encounter a new vertex, if it has no color, give it the opposite color of its parent vertex. If it is already colored the same, the graph is not bipartite.


front: How can you find a cycle in a graph?
back:
DFS. If you discover an edge that connects to an ancestor (previously discovered vertex), you have a cycle.


front: How can you find an articulation vertex?
back:
DFS multiple times. Remove each edge one at a time, doing a DFS after each, so see if you end up with > 1 connected components. If you remove a node and then DFS and find you have fewer than m - 1 edges, you've deleted an articulation vertex. O(n(n+m))

A faster way, with a little more bookkeeping, can be done in O(n+m) time, if you do DFS and keep track of parents and make a note when you reach a back edge, which connects to an ancestor.


front:
How could you identify errors in a DNA fragment assembly given many pairs of sequences, where item A must appear before B in the larger sequence?

back:
Build a DAG representing all the left-right constraints. Any topological sort of the DAG is a consistent ordering. If there are cycles, there must be errors.


front:
C++: We want to call parent constructor in our MyClass constructor, with an arg int called foo. What does this look like in .h and .cc? Parent is ParentClass.

back:
.h:
MyClass(const int foo);

.cc:
MyClass::MyClass(const int foo) : ParentClass(foo) {
    // stuff
}


front:
Python: Write a class function to tell if the graph is bipartite. Start with vertex 0. You can access the adjacency list for a vertex v with: self.adjacency_list[v]

back:
def is_bipartite(self):
        """
        Returns true if graph is bipartite
        :rtype: bool
        """
        colorings = {}
        to_visit = queue.Queue()
        to_visit.put(0)
        colorings[0] = 0

        while not to_visit.empty():
            v = to_visit.get()

            for u in self.adjacency_list[v]:
                if u not in colorings:
                    colorings[u] = 1 - colorings[v]
                    to_visit.put(u)
                elif colorings[u] == colorings[v]:
                    return False

        return True


front: What should you avoid in your base case in recursion?
back:
Too many base case scenarios. Just have one base case so you can return as quickly as possible. Avoid "arm's length" recursion.


front: When talking dynamic programming, what is optimality?
back:
An algorithm has optimality if the subsolutions of an optimal solution of the problem are themsleves optimal solutions for their subproblems.


front: What is dynamic programming?
back:
Dynamic programming is a general-purpose algorithm design technique that is most often used to solve combinatorial optimization problems, where we are looking for the best possible input to some function chosen from an exponentially large search space.

There are two parts to dynamic programming. The first part is a programming technique: dynamic programming is essentially divide and conquer run in reverse: we solve a big instance of a problem by breaking it up recursively into smaller instances; but instead of carrying out the computation recursively from the top down, we start from the bottom with the smallest instances of the problem, solving each increasingly large instance in turn and storing the result in a table. The second part is a design principle: in building up our table, we are careful always to preserve alternative solutions we may need later, by delaying commitment to particular choices to the extent that we can.

The bottom-up aspect of dynamic programming is most useful when a straightforward recursion would produce many duplicate subproblems. It is most efficient when we can enumerate a class of subproblems that doesn't include too many extraneous cases that we don't need for our original problem.


front: Write a dynamic programming version of computing Fibonacci for n.
back:
def fib(n):
   fibValues = [0,1]
   for i in range(2, n+1):
      fibValues.append(fibValues[i-1] + fibValues[i-2])

   return fibValues[n]


front: Write a dynamic programming implementation of longest common subsequence of 2 strings.
back:
def longest_common_subsequence(sequence1, sequence2):
    cols = len(sequence1) + 1   # Add 1 to represent 0 valued column for DP
    rows = len(sequence2) + 1   # Add 1 to represent 0 valued row for DP

    T = [[0 for _ in range(cols)] for _ in range(rows)]

    max_length = 0

    for i in range(1, rows):
        for j in range(1, cols):
            if sequence2[i - 1] == sequence1[j - 1]:
                T[i][j] = 1 + T[i - 1][j - 1]
            else:
                T[i][j] = max(T[i - 1][j], T[i][j - 1])

            max_length = max(max_length, T[i][j])

    return max_length


front: Python: Implement the Floyd-Warshall algorithm (all pairs shortest paths).
back:
# Python Program for Floyd Warshall Algorithm
 
# Number of vertices in the graph
V = 4
 
# Define infinity as the large enough value. This value will be
# used for vertices not connected to each other
INF  = 99999
 
# Solves all pair shortest path via Floyd Warshall Algrorithm
def floydWarshall(graph):
 
    """ dist[][] will be the output matrix that will finally
        have the shortest distances between every pair of vertices """
    """ initializing the solution matrix same as input graph matrix
    OR we can say that the initial values of shortest distances
    are based on shortest paths considerting no 
    intermedidate vertices """
    dist = map(lambda i : map(lambda j : j , i) , graph)
     
    """ Add all vertices one by one to the set of intermediate
     vertices.
     ---> Before start of a iteration, we have shortest distances
     between all pairs of vertices such that the shortest
     distances consider only the vertices in set 
    {0, 1, 2, .. k-1} as intermediate vertices.
      ----> After the end of a iteration, vertex no. k is
     added to the set of intermediate vertices and the 
    set becomes {0, 1, 2, .. k}
    """
    for k in range(V):
 
        # pick all vertices as source one by one
        for i in range(V):
 
            # Pick all vertices as destination for the
            # above picked source
            for j in range(V):
 
                # If vertex k is on the shortest path from 
                # i to j, then update the value of dist[i][j]
                dist[i][j] = min(dist[i][j] ,
                                  dist[i][k]+ dist[k][j]
                                )
    printSolution(dist)
 
 
# A utility function to print the solution
def printSolution(dist):
    print "Following matrix shows the shortest distances\
 between every pair of vertices"
    for i in range(V):
        for j in range(V):
            if(dist[i][j] == INF):
                print "%7s" %("INF"),
            else:
                print "%7d\t" %(dist[i][j]),
            if j == V-1:
                print ""
 
 
 
# Driver program to test the above program
# Let us create the following weighted graph
"""
            10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3           """
graph = [[0,5,INF,10],
             [INF,0,3,INF],
             [INF, INF, 0,   1],
             [INF, INF, INF, 0]
        ]
# Print the solution
floydWarshall(graph);
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)


front: What is the difference between __str__ and __repr__?
back:
def __str__(self): - meant to be human readable
def __repr__(self): - mean to represent the object and be unambiguous, usually as the constructor: for a Vector class, would be:
   
def __repr__(self):
    return "Vector({!r}, {!r})".format(self.x, self.y)
    OR
    return "Vector(%r, %r)" % (self.x, self.y)


Containers use __repr__ of elements when __str__ is called on container.


front: C: Method to find a given item x in a linked list. Head is a List *, x's data type is item_type
back:
List *search_list(List *l, item_type x)
{
  if (l == NULL) return(NULL);

  if (l->item == x)
    return(l);
  else
    return search_list(l->next, x);
}


front: C: Method to insert a given item x into a linked list. Head is a List *, x's data type is item_type
back:
void insert_list(List **l, item_type x) {
  List *p;

  p = malloc(sizeof(List));
  p->item = x;
  p->next = *l;
  *l = p;
}


front: C: Method to return the nth item from the end of a linked list.
back:
int value_n_from_end(node_t *head, int n) {
  if (n < 1 || head == NULL) {
    printf("Cannot get nth item from end.");
    exit(EXIT_FAILURE);
  }

  node_t *current = head;
  node_t *match = head;

  for (int i = 0; i < n && current; ++i) {
    current = current->next;
  }

  if (i != n) {
    printf("List is too short to get nth item from end.");
    exit(EXIT_FAILURE);
  }

  while (current) {
    current = current->next;
    match = match->next;
  }

  return match->val;
}


front:
Python: Given an array of non negative numbers and a total, is there subset of numbers in this array which adds up to given total.

back:
"""
* Time complexity is O(input.size * total_sum)
* Space complexity is O(input.size*total_sum)
"""

def subset_sum(sequence, sum_value):
    cols = sum_value + 1         # Plus 1 for 0 valued col.
    rows = len(sequence) + 1     # Plus 1 for 0 valued row.
    T = [[False for _ in range(cols)] for _ in range(rows)]

    for row in range(rows):
        T[row][0] = True

    for index_i in range(1, rows):
        for index_j in range(1, cols):
            if index_j >= sequence[index_i - 1]:
                T[index_i][index_j] = T[index_i - 1][index_j] or T[index_i - 1][index_j - sequence[index_i - 1]]
            else:
                T[index_i][index_j] = T[index_i - 1][index_j]

    return T[rows - 1][cols - 1]


if __name__ == '__main__':
    sequence = [2, 3, 7, 8]
    assert True == subset_sum(sequence, 11)


front: What is a contiguously-allocated structures, and give examples.
back:
Contiguously-allocated structures are composed of single slabs of memory, and include arrays, matrices, heaps, and hash tables.


front: What are linked data structures and give examples.
back:
Linked data structures are composed of distinct chunks of memory bound together by pointers, and include lists, trees, and graph adjacency lists.


front: Why is memory locality important?
back:
Physical continuity between successive data accesses helps exploit the high-speed cache memory on modern computer architectures.


front: What are some advantages to linked lists over arrays?
back:
- Overflow on linked structures can never occur unless the memory is actually full.
- Insertions and deletions are simpler than for contiguous (array) lists.
- With large records, moving pointers is easier and faster than moving the items themselves.


front: What are some advantages to arrays over linked lists?
back:
- Linked structures require extra space for storing pointer fields.
- Linked lists do not allow efficient random access to items.
- Arrays allow better memory locality and cache performance than random pointer jumping.


front:
Given two strings str1 and str2, find the minimum number of edits (edit one character to another, delete char from str1 or delete char from str2) to change str1 to str2.

back:
"""
* DP Runtime : O(len(str1) * len(str2))
"""

def min_edit_distance(str1, str2):
    rows = len(str2) + 1
    cols = len(str1) + 1
    T = [[0 for _ in range(cols)] for _ in range(rows)]

    for j in range(cols):
        T[0][j] = j

    for i in range(rows):
        T[i][0] = i

    for i in range(1, rows):
        for j in range(1, cols):
            if str2[i - 1] == str1[j - 1]:
                T[i][j] = T[i - 1][j - 1]
            else:
                T[i][j] = 1 + min(T[i - 1][j - 1], T[i - 1][j], T[i][j - 1])

    print_edits(T, str1, str2)

    return T[rows - 1][cols - 1]


if __name__ == '__main__':
    str1 = "azced"
    str2 = "abcdef"
    expected = 3
    assert expected == min_edit_distance(str1, str2)
    assert expected == min_edit_distance(str2, str1)


back: How?
front:
Codeless question: Write a function to compare whether two binary trees are identical. Identical trees have the same key value at each position and the same structure.


back: How would you do it?
front:
Codeless Question: You are given a search string and a magazine. You seek to generate all the characters in search string by cutting them out from the magazine. Give an algorithm to efficiently determine whether the magazine contains all the letters in the search string.


front:
Codeless question: Give an algorithm for finding an ordered word pair (e.g., “New York”) occurring with the greatest frequency in a given webpage. Which data structures would you use?

back:
You could use a hash table, creating or updating an entry for each pair. 
Keep track of max_frequency and most_frequent_phrase.
Just increment the count, and when you see the new count is > than max_frequency, update max_frequency and most_frequent_phrase


front:
Codeless question: Given a set of n numbers, how do you find the pair of numbers that have the smallest difference between them?

back:
Sort them: Once the numbers are sorted, the closest pair of numbers must lie next to each other somewhere in sorted order. Thus, a linear-time scan through them completes the job, for a total of O(n log n) time including the sorting.


front: Codeless question: Are there any duplicates in a given set of n items?
back:
This is a special case of the closest-pair problem, where we ask if there is a pair separated by a gap of zero. The most efficient algorithm sorts the numbers and then does a linear scan though checking all adjacent pairs.


front:
Codeless question: Given a set of n items, which element occurs the largest number of times in the set? Bonus: How do you find out how many times some element k appears?

back:
If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting.

To find out how often an arbitrary element k occurs, look up k using binary search in a sorted array of keys. Then use binary search in each direction to find where that run of the number begins and ends.


front:
Codeless question: Give an efficient algorithm to determine whether two sets (of size m and n, respectively) are disjoint.

back:
The small set can be sorted in O(m log m) time. We can now do a binary search with each of the n elements in the big set, looking to see if it exists in the small one. The total time will be O((n + m) log m).

This is better than sorting the larger array or sorting both sets and going through the list.


front:
Python: Function that reads file numbers.txt and outputs numbers-mult.txt where each number in numbers.txt is multiplied by its line number.

back:
# don't use os.linesep

def main():
    input_file = "numbers.txt"
    output_file = "numbers-mult.txt"

    output = []

    with open(input_file, "r") as input_handle:
        for line_number, line in enumerate(input_handle, 1):
            output.append(line_number * int(line.rstrip()))

    output_handle = open(output_file, "w")
    output_handle.write('\n'.join(str(n) for n in output))


front: What is a uniform distribution?
back:
When a known finite number of outcomes are equally likely to occur. When graphed as a histogram of occurrences, it's a flat line. N items each have 1/n probability.


front: What is a normal distribution?
back:
The standard normal probability density function has the famous bell shape that is known to just about everyone.


front:
Alter a binary search function to find the start and end indexes of the incidences of a number k in a sorted list.

back:
Alter this:


int binary_search(item_type s[], item_type key, int low, int high)
{
    int middle; /* index of middle element */

    if (low > high) return (-1); /* key not found  - replace with return low instead of -1

    middle = (low+high)/2;

    if (s[middle] == key) return(middle); // delete

    if (s[middle] > key)
        return( binary_search(s,key,low,middle-1) );
    else
        return(binary_search(s,key,middle+1,high) );
}


back: ?
front:
Codeless question: If you are given a million integers to sort, what algorithm would you use to sort them? How much time and memory would that consume?


back: ?
front:
Codeless: Implement an algorithm that takes an input array and returns only the unique elements in it.


back: ?
front:
Codeless: You have a computer with only 2Mb of main memory. How do you use it to sort a large file of 500 Mb that is on disk?


front: Python: Default arguments are okay to use with the following caveat.
back:
Do not use mutable objects as default values in the function or method definition.

Lists are not ok.


front: What's the difference between foo.sort() and sorted(foo) where foo is a list?
back:
foo.sort() changes the list to its sorted state
sorted(foo) doesn't change foo, just returns a sorted list.


front: Python: How to output today's date, like August 10, 2016
back:
import datetime

currentDate = datetime.date.today()
print(currentDate.strftime("The date is %B %d, %Y"))


front: Python: How to output today's date, like 8/10/2016 (August, not October)
back:
import datetime

currentDate = datetime.date.today()
print(currentDate.strftime("The date is %m/%d/%Y"))


front: What's the probability of getting heads, tails, heads? P(HTH)
back:
1/8 
= 1/2 * 1/2 * 1/2
the ordering of HTH doesn't matter. It could be TTH or HHH or TTT, they are tall the same.


back: 26*26*26 = 26^3 = 17,576
front:
You have 26 letters in an alphabet. How many ways you can arrange 3 letters from that alphabet where repeated letters is OK?


back: 26*25*24 = 26 permute 3 = 15,600
front:
You have 26 letters in an alphabet. How many ways you can arrange 3 letters from that alphabet without repeating a letter?


back: 26*25*24 / 3! = 2600
front:
Given an alphabet of 26 letters, how many times you can you choose 3 letters, if ordering of the letters doesn't matter?


back: 6 = 4 choose 2 = 4 * 3 / 2
front:
There are 4 people. How many ways can they shake each other's hands without shaking the same person's hand twice?


front: What does NP mean? What is an NP algorithm?
back:
NP is the set of decision problem solvable in non-deterministric polynomial time. An NP problem can be solved by a lucky algorithm that magically always finds a yes decision. NP problems can be checked in polynomial time.


front: What is a weak reference in Python?
back:
A weak reference to an object does not affect its reference count. 
When the only remaining references to a referent are weak references, garbage collection is free to destroy the referent and reuse its memory for something else. A primary use for weak references is to implement caches or mappings holding large objects, where it’s desired that a large object not be kept alive solely because it appears in a cache or mapping.


front: How does garbage collection work in CPython?
back:
CPython uses reference counting and generational garbage collection. There are 3 age stages where objects live in memory. They all start in the "nursery", stage0, then if they survive a garbage collection, they are moved to stage1, the oldest objects that continue to survive in stage1 are promoted to stage2. The gc module has thresholds 700, 10, 10 for each stage. In order to decide when to run, the collector keeps track of the number object allocations and deallocations since the last collection. When the number of allocations minus the number of deallocations exceeds threshold0, collection starts. If generation 0 has been examined more than threshold1 times since generation 1 has been examined, then generation 1 is examined as well. Similarly, threshold2 controls the number of collections of generation 1 before collecting generation 2.


front: What is reference counting?
back:
RC is a method of garbage collection. The runtime keeps track of references to an object by manipulating the reference count on each assignment and delete (del), and when the reference count reaches 0 it means the object is practically unreachable. When the next collection runs, the object's memory will be reserved to allocate for new objects.


front: What is a finalizer in Python?
back:
A finalizer is a destructor, named __del__. __del__() is run when the runtime is about to destroy the object.


front: What are 2 disadvantages of reference counting?
back:
- it cannot collect circular references
- manipulating reference counts at each assignment is very slow.


front: How is garbage collection done in PyPy?
back:
The GC implementation can be chosen at runtime. It's pluggable.
PyPy uses mark and sweep, and generational gc optimization. Marked objects are promoted from the nursery to an older generation.
PyPy uses incremental garbage collection, where major collection is split into multiple passes, each lasting only a few milliseconds.


front: How does mark and sweep work?
back:
(In Java) Perform a DFS on the graph of references to objects. This graph can have multiple roots. Each root is a reference that the program can access directly, such as a variable. Traverse the graph, setting a mark bit in each object. The sweep phase causes unmarked memory to be linked together in a list, so that memory can be reallocated. Sometimes this also triggers compaction, which moves used objects adjacent to each other in memory. The side effect of this is that free memory is also adjacent to free memory so large blocks can be allocated.


front: What is copying garbage collection (stop and copy)?
back:
Heap memory is split into 2 partitions: an old space and a new space. Find live objects by DFS of their reference graph, and move live objects into the new space. The new space is now called the old space. Unreachable objects are simply left in the old space to be overwritten the next time collection occurs. The movement of objects implicitly compacts the objects. Disadvantage: you can only use half of the heap space.


front: How could you implement an LRU cache?
back:
A fast lookup table, like a hash table or binary tree, and a linked list of items by use. When you access or add an item, you delete it from the linked list and add it to the head of the list.  Then to prune, traverse the linked list and remove trailing elements, and delete them from the storage (tree or hash table).
You can also use a splay tree, since it moves accesses to the root. To prune items, somehow find and remove the leaves, since the number of leaves will be about n/2.


front: What is a direct mapped cache?
back:
It's a type of cache used in the CPU, where the lower order bits of a given memory address are used modulo the number of cache lines to place or lookup in the cache. Collisions are treated as overwrites.


front: What is a fully-associative cache?
back:
It's a type of cache used in the CPU, where lookups are done on all cache lines in parallel to determine a hit or miss.

This requires a very large number of comparators that increase the complexity and cost of implementing large caches. Therefore, this type of cache is usually only used for small caches, typically less than 4K.


front: What is an N-way set associative cache?
back:
A Set-Associative cache scheme is a combination of Fully-Associative and Direct Mapped caching schemes. A set-associate scheme works by dividing the cache SRAM into equal sections (2 or 4 sections typically) called cache ways. The cache page size is equal to the size of the cache way. Each cache way is treated like a small direct mapped cache.


front: Describe the memory hierarchy of a Core i7 processor.
back:
Inside of each core is a 32 kB L1 instruction cache, a 32 kB L1 data cache (it's 8-way set associative), and a dedicated 256 kB L2 cache (also 8-way set associative). 
Outside of the cores is the L3, which is much larger at 8 MB and smarter (16-way associative) than the L2s.


front: Is DELETE idempotent?
back:
According to the REST spec, yes, but it's up to the developer to conform to that. It can be achieved by using a deleted flag for a resource instead of completely removing the resource.


front: What is idempotent?
back:
The property that a method has side-effects of making more than one identical requests is the same as for a single request.


front: What is HMAC?
back:
HMAC is a keyed-hash message authentication code used to provide a checksum for a message, sent along with the message to provide confidence that the message has not been tampered.


front: What is a MAC?
back:
MAC is a message authentication code used to provide a checksum for a message, sent along with the message to provide confidence that the message has not been tampered.


front: How does RSA work?
back:
It's a public/private key cryptography method. The public key can be used to encrypt a message into ciphertext that only the owner of the key can decrypt. The owner of the key uses their secret key to encrypt messages, and their secret key to decrypt messages encrypted with their public key.


front: What is symmetric key encryption?
back:
There is a known encryption function, and one key is used to encrypt and decrypt. The key has to be shared between 2 parties.


front: How does Diffie-Hellman key exchange work?
back:
2 parties agree on a G and a modulus p, and each party comes up with a number. One party does G^a and the other G^b. They pass this information. One party A computes the key from B as B^a mod p. B computes A^b mod p to get the key.


front: How is RSA (using product of large primes) better than using NP-Complete algorithms for encryption?
back:
NP-Complete algorithms are hard in the worst case, but can be sometimes solved in linear time in the average case. Compositing the product of large primes is hard in the average case.


front: What is Vigenere cipher?
back:
Improvement on Caesar cipher. Letters are shifted based on a shifted dictionary. "Polyalphabetic cipher"


front: What is a one-time pad encryption?
back:
The "perfect" simple encryption scheme. Pad/key is the same size as the message being encrypted. The key is randomly generated and xored against the plain text. Or key used to determine the amount each letter should be shifted.


front: What is block size in cryptography?
back:
Symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size. Both the input (plaintext) and output (ciphertext) are the same length; the output cannot be shorter than the input – this is logically required by the Pigeonhole principle and the fact that the cipher must be invertible – and it is simply undesirable for the output to be longer than the input.


front: What is the limiting factor of compression?
back:
For lossless compression, it's entropy. For lossy compression, it's our acceptance with the amount of loss.


front: What is LZ* compression based on?
back:
Cataloging the positions and lengths of redundant patterns and combining the values with a dictionary.


front: What is LZMA?
back:
It's a variant of LZ77 that uses Markov chains. It's used in the 7z compression algorithms used in 7-zip.


front: What is DEFLATE?
back:
It's an lossless compression algorithm based on LZ77 used in Gzip, WinZip, and mod_deflate, which is bundled with Apache web server for automated gzip compression of HTTP served content. It uses LZ77 and Huffman coding.


front: How does LZ77-based compression work?
back:
LZ77 is a dictionary encoding algorithm, which is a statistical encoding algorithm. Compression in the LZ77 algorithm is based on the notion that strings of characters (words, phrases, etc.) occur repeatedly in the message being compressed.

The input is partitioned into 2 segments: a search buffer and a look-ahead buffer. The search buffer maxes out at 32KB. Starting with one character in the LA buffer, it looks back in the search buffer to find a copy of the symbol. If one is found, it looks at the second symbol of the LA buffer to see if it also matches the predecessor. Using this method, it can detect long phrases of symbols and encode them as one unit.

This process implicitly creates a rolling statistical probability for each symbol/phrase.


front: What is Huffman encoding?
back:
Huffman encoding algorithm analyzes the occurrence of individual symbols and creates a binary tree where the common symbols are closest to the root, using fewer bits to encode, and less common/rare symbols have longer paths on the tree, with longer encodings to accommodate. By traversing the tree, from root to leaf, and keeping track of 1 or 0 at each node, we can determine the encoding of the symbol.


front: What is the Burrows-Wheeler transform?
back:
It's a compression method involving the sorting of all possible rotations of the input text into lexicographic order. Take as output the last column and the index of the row that the original text appears in. 

To decode, take the single column and repeatedly add the final columns characters to each of the rows, sorting each time. Once you've reached the length of the column's height, use the index to find the output string.


front: How can you make JSON better compressable with Gzip?
back:
Transpose from multiple mini-dicts into one dict with arrays as the values. This allows the items in an array to fit within the 32KB search buffer common to LZ-based compression.


front: What are Dense Codes?
back:
A way to put symbols or words into a dictionary or array, and use the indices as the values in the text to save space so that words are not repeated.


front: What is OS hardware virtualization?
back:
The abstraction of heterogeneous hardware provided by the operating system, to hide the details of interfacing with various hardware so that they share a common interface for that type.


front: What is a process?
back:
An instance of an executing program consisting of an address space and one or more threads of control. It has restricted rights. It owns a region of memory. It owns file descriptors, file system context. It encapsulates one or more threads sharing the process' resources. It is isolated from other processes.


front: What causes operating systems to crash most of the time?
back:
Device drivers. They are in the kernel and very low level. They have access to all the hardware, including memory. They are written by authors outside of the operating system.


front: What is a process VM?
back:
A virtual environment that supports the execution of a single program. This is provided by an operating system.


front: What is a system VM?
back:
A virtual environment that supports the execution of an entire operating system and its applications.


front: What is the execution sequence for a program?
back:
- Fetch instruction
- Decode
- Execute (perhaps using ALU and writing result to a register)
- Write results to registers or memory
- Increment program counter
- Repeat


front: What triggers a context switch?
back:
Timer interrupt, hardware interrupt, I/O where we're waiting for a read or write to complete (OS doesn't want to waste time waiting), voluntary yield.


front: How does the OS run a program?
back:
It does an exec from kernel mode (system mode 1). We go to system mode 0, user mode. When the program exits, we switch back to kernel mode.


front: How does a user program interact with the kernel?
back:
It makes a system call, and the kernel takes over, completes the action, and the kernel returns to the process (back to user mode).


front: What happens when the hardware needs something to happen?
back:
It does an interrupt, and the kernel takes control, switches the process, and once hardware task is complete, does a return from interrupt back to user mode.


front: What is base and bound?
back:
It's a memory addressing restriction where a processes are only allowed access to the memory between a base address and the bound + base addresses. Each process has its own base and bound. A drawback is you don't get address 0. Address translation fixes this.


front: How does the OS know how to handle an interrupt?
back:
It keeps an interrupt vector in the memory of the OS. Each interrupt type is mapped to an address to execute. They are just pointers to code in the OS.


front: What is the difference between PC and uPC?
back:
PC is the program counter for the current process. uPC is the PC of the user process we will return to once an interrupt or other OS process switches context.


front: How does x86 do segments and stacks?
back:
Each process' individual segments (heap, stack, code, static data) get their own base and bound. They don't even need to be adjacent in memory and their location is hidden by memory addressing.


front: When a process forks, what happens?
back:
The process is paused, and a complete copy is made: code, stack, heap, data, program counter and registers.
The child and parent resume with returning from fork syscall.


front: What is a shell?
back:
A job control program. It allows a programmer to create and manage a set of programs to do some task.


front: How does the kernel handle reads and writes?
back:
It buffers reads so they can be handled as a stream in your program. Writes are buffered and are not written until the kernel flushes the buffer.


front: What's the difference between the fread, read, fwrite, write I/O calls?
back:
The ones with f are high-level I/O and streamed and buffered by the kernel. The non-f are low-level I/O.


front: What is a socket?
back:
It's an abstraction of a network I/O queue.  It's a method of communication where a producer writes to one side, and a consumer reads from the other side. It's similar to writing and reading a file, but no file is involved.


front: What is the GIL?
back:
It's the Global Interpreter Lock. It's is a part of CPython. It ensures only one thread runs in the interpreter at once. Having the GIL simplifies many low-level details (memory management, callouts to C extensions, etc.)


front: What happens every 100 "ticks" in the CPython interpreter?
back:
A thread check occurs during which the thread releases the GIL then attempts to reacquire it. Other Python threads will contend for the the GIL. This is no longer the case in 3.4.


front: What can happen with thread stacks if one goes into a deep recursion?
back:
One thread's stack can grow into another thread's stack and write over it. A guard page can help to protect from that.


front: What can cause a thread to give control back to the dispatcher?
back:
Thread returns control voluntarily (yield, requesting I/O (which blocks), wait for signal from another thread) or gets preempted by an interrupt.


front: What's the difference between parallelism and concurrency?
back:
Concurrency means running multiple blocks of instructions independently. Parallelism means running instructions at the same time, as on multiple cores at once.


front: What is a race condition?
back:
When the outcome of a deterministic procedure becomes non-deterministic based on differences in subprocess timing.


front: How do you use a mutex in Python?
back:
import threading

lock = threading.Lock()

[first process]
global lock
lock.release()
...
[other process]
global lock
lock.acquire() // attempts to get access, waits if it can't


front: What is livelock?
back:
It occurs when multiple processes are attempting to deal with the current state, but neither makes progress. This can happen when a system is attempting to resolve a deadlock situation but another or the same process continue to trigger it.
Starvation is another example.


front: In Python, what can you use to fork a process?
back:
The multiprocessing module. It supports process Pool and Process for making a pool of worker processes or forking temporary subprocesses.


front: What happens during an interrupt?
back:
The currently running process' state is saved. We switch to kernel mode, the interrupt handler runs, and once its complete, the system goes back to user mode and the process continues.


front: What really happens when you fork a process?
back:
A fork doesn't copy everything, it just duplicates the page table pointers, which are all set at read-only. Called copy-on-write. Once you write to memory, then it copies the state.


front: What does a PCB contain?
back:
Everything about a process:
- status
- register state (when not in ready state)
- PID, User, Executable, Priority
- Execution time
- Memory space, translation


front: What are the five states a process can be in?
back:
- new (when being created)
- ready
- running
- waiting (for I/O or event coordination)
- terminated (waits for parent process to receive its exit code)


front: What is the difference between filter() and map()?
back:
Filter uses a function that returns true or false (predicate).
Map uses a function that returns a value.


front: What is a critical section?
back:
A block of code that you lock before entering, then unlock when leaving. This creates a mutual exclusion on shared data.


front: What is the priority inversion problem?
back:
A thread that is busy-waiting for a lock to be released ends up stealing CPU and getting a higher priority than the thread with the lock. SO since the waiting thread gets higher priority, the thread holding the lock can't complete and release the lock.


front: What is busy-waiting?
back:
One or more threads is using a lot of CPU by continuously checking a value, or test&set() checking and writing a value in wiating for a lock to release, thus stealing CPU from the thread holding the lock.


front: What is a semaphore?
back:
A semaphore (defined by Dijkstra) is kind of signaling solution for handling concurrency data integrity problems that arise in multi-threaded applications. It has a non-negative integer that supports 2 operations:
- P() [proberen, to test/probe] - atomic operation that waits for semaphore to become > 1, then decrements it by 1 (wait)
- V() [verhogen, to increment] - an atomic operation that increments the semaphore by 1, waking up any P (signal)

The initial semaphore value will determine how many threads can run in the critical section at once.


front: What is a drawback of context switching?
back:
CPU cache misses as thread comes back from switching and finds the CPU cache doesn't have the values it had before.


front: What is the round robin scheduling scheme?
back:
Each process gets a time quantum q milliseconds to run. 10-100ms, the q is tunable. Each process runs for that time slice (or until completion if close to done) and then goes back on the ready queue.


front: What are some methods of avoiding deadlock?
back:
- don't allow waiting for a resource (means a lot of retries)
- make all threads request everything they'll need at the beginning
- force all threads to request resources in a particular order preventing any cyclic uses of resources (so no cycle exists)
- temporarily expand resources when a deadlock is detected


front: What is the banker's algorithm for preventing deadlock?
back:
- allocate resources dynamically
- evaluate each request and grant if some ordering of threads is still deadlock-free afterward
- do so by pretending the request was granted, then running a simulation to see if a deadlock would occur


front: How does the banker's algorithm solve the dining lawyers problem?
back:
When you try to grab a chopstick, it's either:
- not the last chopstick
- is last chopstick but someone else will have two afterwards


front: What is a PDU?
back:
Protocol data unit
- generic term used to describe the information at a given layer in the TCP/IP stack


front: What is involved in the 3 way handshake (TCP)?
back:
SYN=1 - synchronize, gives a Seq number and expects that number + 1 in response
ACK=1 - sent by acknowledging server with incremented number, who also sends a SYN=1 and a Seq
SYN=0 ACK=1 and the Seq (incremented number) back to the server

Now you're talking!


front: What are the 4 layers of TCP/IP?
back:
- application (application, presentation, session in OSI)
- transport
- internet (network in OSI)
- network access (data link & physical in OSI)


front: How is an SSL certificate generated by the certificate authority (CA)?
back:
The common name and public key for a given domain name, signed by the certificate authority's secret key.
The browser can verify the cert with CA's public key.


front: What is the secure flag on a cookie?
back:
When set on a cookie, it will only be sent on https requests.
When not set, cookie will be sent on both http and https requests.


front: Give an example of the thread-per-connection pattern.
back:
A web server might spawn a thread per connection, then reuse that thread once the connection ends, or terminate the thread.


front: Give an example of the thread pool model.
back:
A pool of threads can be maintained in order to quickly provide one as a resource for a database connection.


front: What is special about TCP?
back:
It manages the sending and receiving of packet data.
It acknowledges receipt of packets.
If packets are missing, the source will resend the missing packets.


front: What does SNMP do?
back:
Gathers info from machines on the network when each box has an SNMP agent installed. Can send a large amount of info about machines, software installed, and machine configuration.


front: What is special about UDP?
back:
It's connectionless, packets are only sent once and not re-sent if dropped. Packets may not arrive in the right order, and there is no ordering mechanism to fix on the receiving end. No congestion control.


front: What's special about TCP?
back:
It does a 3-way handshake before data is sent.
Delivery is acknowledged by receiver.
Packets missing within a certain time window are re-requested.
Packets are put in order on receipt.
Congestion control: can delay delivery until network is uncongested.
IPv4 and IPv6: error detection, checksum mandatory.


front: What happens in the Session layer of the OSI model?
back:
This layer handles configuration of the data:
- encryption
- compression
- translation to and from different character encodings


front: What happens at the Session layer of the OSI model?
back:
This layer controls the communication's access via:
- login rights
- permissions
- rights
- roles


front: What happens at the Transport layer of the OSI model?
back:
This layer guarantees end-to-end delivery of data:
- packet ordering
- error detection
- acknowledgements


front: What happens at the Network layer of the OSI model?
back:
This layer's function is to find the shortest path through the network to the destination network.
Deals with congestion, bandwidth, etc.


front: What happens at the Data Link layer of the OSI model?
back:
It decides whose turn it is to talk on the network using bus arbitration methods.
It finds the physical device on the network.


front: What happens at the Physical layer of the OSI model?
back:
It's the physical network that deals with the physical transmission of electricity through wire:
- cables
- voltages
- frequencies
- connectors
- bits
- transfer rates
- and much more


front: How does HTTP/2 save bandwidth?
back:
Headers are compressed and do not need to send the same headers in a session if they haven't changed.
Servers can send assets referenced in a document without waiting for discrete requests for them.


front: How are headers and body treated differently in HTTP/2?
back:
They are split into a header frame and a data frame. Multiple requests can be interleaved in a connection, so a request doesn't block.


front: How many host IDs are supported on a Class A network?
back:
2^24 = 16 million
There are 8 bits for the network ID, and the remaining 24 bits are for host IDs.
So there are 16 million per network.


front: What is a limited broadcast address?
back:
The limited broadcast address is the address formed by setting all 32 bits of the IP address to 1 (255.255.255.255). The limited broadcast address is used when an IP node must perform a one-to-everyone delivery on the local network but the network ID is unknown.


front: What does a /24 CIDR mean?
back:
The first 24 bits of the IP address are masked. Only hosts with addresses in the unmasked portion are reachable.


front: What is a block cipher?
back:
A block cipher is a method of encrypting text (to produce ciphertext) in which a cryptographic key and algorithm are applied to a block of data (for example, 64 contiguous bits) at once as a group rather than to one bit at a time.


front: What is QUIC?
back:
QUIC is a new transport which reduces latency compared to that of TCP. On the surface, QUIC is very similar to TCP+TLS+HTTP/2 implemented on UDP.


front: What is Capsicum?
back:
A sandboxing framework that adds capability-based security to unix-like kernels and denies access to global namespaces.


front: What is Google Native Client?
back:
Also called NaCl, Native Client is a sandbox for running compiled C and C++ code in the browser efficiently and securely, independent of the user’s operating system.


front: What is the same-origin policy?
back:
Goal: Two websites should not be able to tamper with each other.
Strategy: each resource is assigned an origin. JS can only access resources from its own origin.
Origin: scheme + hostname + port


front: How can 2 origins (let's say 2 frames) communicate?
back:
window.postMessage (HTML5) allows for sending data messages between two windows/frames across domains.


front: What is JIT compilation?
back:
JIT compilation, also known as dynamic translation, is compilation done at run-time rather than ahead of time (AOT).


front: What is PyPy?
back:
PyPy is a replacement for CPython. It is built using the RPython language that was co-developed with it. RPython is a subset of Python and can be translated to C. The main reason to use it instead of CPython is speed: it runs generally faster due to JIT compilation.
PyPy implements Python 2.7.10. It supports all of the core language, passing the Python test suite (with minor modifications that were already accepted in the main python in newer versions). It supports most of the commonly used Python standard library modules.


front: What is an SMT solver?
back:
A satisfiability modulo theories solver solves for large interconnected logic formulas to determine if a given formula can be satisfied. These are helpful for determining the outcome or inputs for a program using symbolic execution.


front: How do we find that a condition exists that will cause a program to have a predicted outcome?
back:
Using an SAT solver (using logic tests) and an SMT solver (that plugs in numbers), and tells the SAT solver where it got it wrong. They provide feedback in a cycle to each other until a condition can be found.


front: What is transactional memory?
back:
Transactional memory attempts to simplify concurrent programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing.


front: What is software transactional memory?
back:
Software transactional memory provides transactional memory semantics in a software runtime library or the programming language, and requires minimal hardware support (typically an atomic compare and swap operation, or equivalent). As the downside, software implementations usually come with a performance penalty, when compared to hardware solutions.


front: Does PyPY have a GIL?
back:
Yes. The GIL is very difficult to remove. You can use pypy-stm instead, which uses software transactional memory, but will suffer a performance penalty.


front: How can a server deal with a SYN flood attack?
back:
When it detects a large number of SYN packets at once, or the size of its SN (sequence number) data structure reaches a certain threshold of entries, it can switch to a stateless version, where it send SN responses as signed values with a timestamp, and if it receives one back it lets them through without needing a lookup table.


front: What is a stack canary?
back:
It's a buffer overflow defense where a random value is pushed onto the stack after the saved EBP, and before tearing down the stack frame, the value is checked. Any buffer flow targeting the return instruction pointer would have to have overwritten this value.


front: What type of buffer overflow protection does gcc and Visual Studio employ?
back:
They use a stack check guard of bytes before and after the buffer's allocated memory. Once values are written to the buffer, the bytes are checked to ensure they are still the same.


front: What is scalability?
back:
Scalability is the measure to which a system can adapt to a change in demand for resources, without negatively impacting performance.


front: What is Akka?
back:
An open source project that provides a simpler, single programming model - one way of coding for concurrent and distributed applications - the actor programming model.
Akka’s primary goal is to make it simpler to build applications that are deployed in the cloud or run on devices with many cores and that efficiently leverage the full capacity of the computing power available. It’s a toolkit that provides an actor model, runtime, and required supporting tools for building scalable applications.


front: What is an actor?
back:
Briefly, actors are a lot like message queues without the configuration and message broker installation overhead. They’re like programmable message queues shrunk to microsize—you can easily create thousands, even millions of them. They don’t “do”
anything unless they’re sent a message.
Messages are simple data structures that can’t be changed after they’ve been created, or in a single word, they’re immutable.
Actors can receive messages one at a time and execute some behavior whenever a message is received. Unlike queues, they can also send messages (to other actors).
Everything an actor does is executed asynchronously. Simply put, you can send a message to an actor without waiting for a response. Actors aren’t like threads, but messages sent to them are pushed through on a thread at some point in time. How actors are connected to threads is configurable - this is not a hardwired relationship.
For now the most important aspect of actors is that you build applications by sending and receiving messages. A message could be processed locally on some available thread, or remotely on another server. Exactly where the message is processed and where the actor lives are things you can decide later, which is very different compared to hardcoding threads and RPC style networking. Actors make it easy to build your application out of small parts that resemble networked services, only shrunk to microsize in footprint and administrative overhead.


front: What is an IDL-based encoding?
back:
An interface description language or interface definition language (IDL) encoding. 
It requires a schema definitions. They offer peace of mind with respect to data format and validation for consumers while sacrificing flexibility in the schema’s evolution.


front: What is a coroutine?
back:
An object representing activity that eventually completes. Also refers the the function we call that returns a coroutine.
In Python, coroutines are generators.


front: What is AQP?
back:
Approximate query processing. It means pulling a sample of data instead of taking time to process an exact result. It is often used when a data storage involves terabytes or more.


front: How would you visualize billions of items in a graph?
back:
In many cases, you don't need to graph every point, just use visualization-aware sampling. Sometime 1% or less will do.


front: How does Google use multi-homed datacenters?
back:
A multi-homed system runs live in multiple datacenters all the time. Each datacenter processes work all the time, and work is dynamically shared between datacenters to balance load. When one datacenter is slow, some fraction of work automatically moves to faster datacenters. When a datacenter is completely unavailable, all its work is automatically distributed to other datacenters.


front: What is an example of a circuit breaker?
back:
Start sending 503s if your service is choked to avoid numerous simultaneous retries that just make the system worse.


front: What does an eviction policy try to predict?
back:
An eviction policy tries to predict which entries are most likely to be used again in the near future, thereby maximizing the hit ratio


front: What is request coalescing?
back:
When many requests arrive for some content that’s missing in the cache (cache miss), only one instance request will proceed to the backend to fetch the content on behalf of all to avoid a flood.


front: When might you need to use a NoSQL database
back:
You don’t have any relational data.
If you need to store > 5 TB of data or you have an incredibly data intensive workload.
Your application has super low-latency requirements.
You need really high throughput.


front: What is AMP?
back:
AMP is a restricted subset of HTML designed to make the web fast on mobile devices.
Provides a shared library of scripts so they don’t have to downloaded every time.
Sets standards for the architecture of advertising so advertising doesn't infect pages.
Shared mechanism for collecting data for analytics so you don’t have N different packages on a page gathering stats.


front: What is a benefit of making processes asynchronous?
back:
Flexibility in the architecture. Getting users on hooked on synchronous low-latency interactions doesn't allow for architecture flexibility.


front: What is BASE?
back:
basically available
soft state
eventually consistent

A BASE based system is more tolerant to latency because it is an inherently partitioned and loosely coupled architecture and it uses eventual consistency.


front: What is the CAP theorem?
back:
The CAP theorem, also named Brewer's theorem, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:

- Consistency (all nodes see the same data at the same time)
- Availability (every request receives a response about whether it succeeded or failed)
- Partition tolerance (the system continues to operate despite arbitrary partitioning due to network failures)


front: What is zero copy?
back:
Applications that use zero copy request that the kernel copy the data directly from the disk file to the socket, without going through the application. Zero copy greatly improves application performance and reduces the number of context switches between kernel and user mode.


front: What is privilege separation?
back:
Separating an application into different areas so a vulnerability in one area doesn't affect the entire application.


front: When is security enforced on a file?
back:
Security is checked when the file descriptor is created. Then it's up to the user to be careful and secure the file descriptor.


front: What is ptrace?
back:
ptrace is a system call found in several Unix and Unix-like operating systems. By using ptrace, one process can control another, enabling the controller to inspect and manipulate the internal state of its target.


back: setuid()
front:
During system bootstrapping, what call is performed by the system to give a non-root user the ownership of a process?


front: What does chroot do?
back:
Changes the root directory (/) for a user to be a directory on the filesystem where they can't escape.


front: What is a confused deputy?
back:
A confused deputy is a computer program that is innocently fooled by some other party into misusing its authority. It is a specific type of privilege escalation. In information security, the confused deputy problem is often cited as an example of why capability-based security is important, as capability systems protect against this whereas access control list-based systems do not.
The classic example is a Fortran compiler that creates a billing record for each use. A user was able to tell the compiler to output a binary with the same name as the billing file, overwriting it.


front: What is ambient authority, or ambient privilege?
back:
The decision about whether a process or agent can perform an action is based on information not explicitly stated, but inherited instead.


front: What is a capability?
back:
The privilege to act upon something given your ownership of it, and the inability to act on something using an intermediate process' privileges. An example would be a function where you pass a file descriptor as an argument and the function uses your capability, not its own.


front: What is a requirement of enabling sandboxing?
back:
The kernel must be able to support it by disallowing system calls that reference global namespaces:
- file paths starting at root - must be relative
- network
- PIDs - use process descriptors instead


front: How is RSA decryption optimized for speed?
back:
- c^d mod p and c^d mod q are processed in parallel and merged at the end using the Chinese remainder theorem
- put into Montgomery format
- sliding windows to exponentiate on bits of exponent
- perhaps a single extra reduction
- convert back from Montgomery format
- merge using CRT


front: What is RISC?
back:
Reduced Instruction Set Architecture. 
- more registers
- fewer, fixed-sized instructions
- used in PowerPC, ARM, SPARC, MIPS


front: What is Little Endianness?
back:
The least significant bytes of a word or larger are stored in the lowest address. All bytes are the same. There is no Endianness within a byte.


front: What is Chef?
back:
A configuration tool. You write or reuse recipes that declare the state you wish your server to be in. It calculates the delta and builds out for you.


front: What is an example of a non-cryptographic hash function?
back:
MurmurHash is an efficient, non-cryptographic hash function suitable for general hash-based lookup. The name comes from two basic operations, multiply (MU) and rotate (R), used in its inner loop. It has an avalanche effect. The current version is MurmurHash3 which yields a 32-bit or 128-bit hash value.


front: How could you process calculations on elements of an array in parallel?
back:
Using recursion, divide and conquer, breaking down the array into smaller segments, then merging the values as the recursion unwinds. Non-mutation of the array means locking is not required.


back: The memory bandwidth of your RAM. It can become a bottleneck.
front:
What factor should you keep in mind when doing parallel computation on different parts of a large data structure?


front: Why should you avoid starting and joining a task or thread on the same line or proximity?
back:
Execution on the current thread will block until it completes, thereby obviating the concurrent call.


front: What factors affect performance?
back:
- processor speed 
- number of processors
- memory access latency and throughput
- cache behavior
- runtime behavior (garbage collection, JIT compilation, thread scheduling)


front: What is Amdahl's Law?
back:
It gives the theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved.


front: What aspects are important in measuring and benchmarking performance, parallel or otherwise?
back:
- multiple repetitions
- statistical treatment - mean and variance
- eliminate statistical outliers
- ensuring steady-state (warm-up)
- preventing anomalies (garbage collection, JIT compilation, compiler optimizations in benchmark code that misrepresents real-world)


front: What is the commutative property?
back:
The condition that a group of quantities connected by operators gives the same result whatever the order of the quantities involved. So order of operands doesn't matter, but grouping may matter.


front: What are some examples of operations that are both associative and commutative?
back:
- Addition and multiplication of integers
- Union, intersection, and  symmetric difference of sets
- Addition of vectors
- Addition of matrices of fixed dimension
- Addition and multiplication of polynomials


front: What is the rule of thumb before optimizing or parallelizing?
back:
Ensure the code works correctly first. Then, if you want to get fancy, you can begin to optimize your code for greater speed.


front: Does Python have an opcode cache?
back:
In a way. It outputs a .pyc file, containing the bytecode. When a module is imported for the first time, or when the source is more recent than the current compiled file, a .pyc file containing the compiled code will usually be created in the same directory as the .py file. When you run the program next time, Python uses this file to skip the compilation step.


back: ask:
front:
How would you design the feature in LinkedIn where it computes how many hops there are between you and another person?


front: What are some key things to remember when scaling a large system?
back:
1) Asynchronous is good  (use queues, topics/pub-sub)
2) Parallel is good  (multi-threading, load balancing etc.)
3) Avoid points of contention e.g. synchronization
4) Avoid writing to disk until you must - cache like crazy
5) Scale out not up
6) At web scale the speed of light is a problem
7) At web scale everything fails - networks, load balancers etc.


front: What is Thrift?
back:
Apache Thrift is a framework for scalable cross-language services development. It combines a software stack with a code generation engine to build services that work efficiently and seamlessly between different languages. It handles serialization and has its own communication protocol.
IDL-based.


front: How does/did Facebook use memcache and mySQL in 2009?
back:
No joins in production. They have many logical databases for all of their types: people, events, place info, etc. They treat the web tier as a CPU, memcache as system memory, and the database as disk. Everything has an ID and you use the ID to query memcache using a multiget. Any misses are fetched from the database and cached in memcache.


front: What is an out-of-band cache?
back:
A cache layer that does not synch with persistent storage. When changes are made to the database, there are no notifications to synchronize with the cache. The cache entry would need to be updated or evicted by other means.


front: What is a monad?
back:
In functional programming, monads are a way to build computer programs by joining simple components in predictable and robust ways. A monad is a structure that represents computations defined as sequences of steps: a type with a monad structure defines what it means to chain operations together, or nest functions of that type. This allows the programmer to build pipelines that process data in a series of steps (i.e. a series of actions applied to the data), in which each action is decorated with additional processing rules provided by the monad. A monad is defined by a return operator that creates values, and a bind operator used to link the actions in the pipeline.


front: Theta represents what?
back:
A tight asymptotic bound on a function, in other words if both f and g have approximately the same rate of growth.


front: What is data normalization?
back:
Normalization is a systematic approach of decomposing tables to eliminate data redundancy and undesirable characteristics like insertion, update and deletion anomalies.

Normalization is used for mainly two purpose,
- eliminating redundant (useless) data
- ensuring data dependencies make sense


front: What are the requirements for first normal form?
back:
- each cell has a single value
- all items in a column must be of the same type
- rows are uniquely identified by a unique ID or a composite key


front: What are the requirements for fourth normal form?
back:
No multi-valued dependencies, meaning records should not be duplicated in a table just because more than one item is associated. This creates records that are duplicates except for one field.


front: What are some solid principles to keep in mind for scaling?
back:
- Keep it very simple
- Don’t re-invent the wheel
- Go with boring, proven and well-supported technologies when you can
- Build for what you will need over the next 12-18 months
- Make different things look the same
- Cache to protect the database
- Good enough is good enough


front: What is WSGI?
back:
WSGI is the Web Server Gateway Interface. It is a specification that describes how a web server communicates with web applications, and how web applications can be chained together to process one request. It was outlined in PEP 3333.

A WSGI server (meaning WSGI compliant) only receives the request from the client, pass it to the application and then send the response returned by the application to the client.


front: What is Fabric?
back:
Fabric is a Python (2.5-2.7) library and command-line tool for streamlining the use of SSH for application deployment or systems administration tasks.


front: What is Apache Solr?
back:
Solr is an open source enterprise search platform built on Apache Lucene.
Solr is highly reliable, scalable and fault tolerant, providing distributed indexing, replication and load-balanced querying, automated failover and recovery, centralized configuration and more.


back: Fan-in, where you can overload routers due to increased internal network traffic.
front:
What tends to become an issue as you add services in a datacenter and have to ping more caches and services to fulfill a request?


front: What is a benefit of sharding a database as it grows, and what determines the size?
back:
Keeping the index in cache ensures a user lookup doesn't have to hit the disk, lookups can be served from RAM. How much RAM you have will determine the index size which will hint at the underlying data size.


front: What is a message broker?
back:
Message broker is an intermediary program module that translates a message from the formal messaging protocol of the sender to the formal messaging protocol of the receiver. Message brokers are elements in telecommunication networks where software applications communicate by exchanging formally-defined messages. Message brokers are a building block of Message oriented middleware.


front: What are some examples of message brokers?
back:
Apache ActiveMQ
Apache Kafka
Apache Qpid
Celery
Gearman
HornetQ (Red Hat)
IBM Integration Bus
JBoss Messaging (JBoss)
JORAM
Microsoft BizTalk Server (Microsoft)
Microsoft Azure Service Bus (Microsoft)
NATS (MIT Open Source License, written in Go)
Open Message Queue
Oracle Message Broker (Oracle Corporation)
QDB (Apache License 2.0, supports message replay by timestamp)
RabbitMQ (Mozilla Public License, written in Erlang)
SAP PI (SAP AG)
Spread Toolkit
Tarantool, a NoSQL database, with a set of stored procedures for message queues
WSO2 Message Broker
Enduro/X Transactional Message Queue (TMQ)


front: What is Ehcache?
back:
Ehcache is an open source, standards-based cache that boosts performance, offloads your database, and simplifies scalability. It's the most widely-used Java-based cache.


front: What is Kafka?
back:
Apache Kafka is pub-sub messaging rethought as a distributed commit log.
Kafka is a distributed, partitioned, replicated commit log service. It provides the functionality of a messaging system, but with a unique design.
A single Kafka broker can handle hundreds of megabytes of reads and writes per second from thousands of clients.


front: What is GAE?
back:
Google App Engine is a platform for building scalable web applications and mobile backends. App Engine provides you with built-in services and APIs such as NoSQL datastores, memcache, and a user authentication API, common to most applications.


front: What is GDS?
back:
Google Cloud Datastore is a NoSQL document database built for automatic scaling, high performance, and ease of application development. Cloud Datastore features include:

Atomic transactions.
Massive scalability with high performance.
Flexible storage and querying of data.
Balance of strong and eventual consistency. 
Encryption at rest.
Fully managed with no planned downtime.


front: What is the problem that serialization introduces?
back:
The overhead of serializing and deserializing. It's all expensive, and for Python, it can be terribly slow.


front: What does the Python bisect module do?
back:
The bisect module, part of the standard library, provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach.


front: What is PycURL?
back:
PycURL is a Python interface to libcurl. PycURL can be used to fetch objects identified by a URL from a Python program, similar to the urllib Python module. PycURL is mature, very fast, and supports a lot of features.
PycURL is targeted at an advanced developer - if you need dozens of concurrent, fast and reliable connections or any of the sophisticated features listed above then PycURL is for you.
The main drawback of PycURL is that it is a relatively thin layer over libcurl without any of those nice Pythonic class hierarchies. This means it has a somewhat steep learning curve unless you are already familiar with libcurl's C API.


front: How does PycURL compare to requests?
back:
PycURL can handle a large number of multiple concurrent requests. When reusing connections, it can perform more than 2,000 requests per second.

pycurl takes about 73 CPU-microseconds to issue a request when reusing a connection
requests takes about 526 CPU-microseconds to issue a request when reusing a connection
pycurl takes about 165 CPU-microseconds to open a new connection and issue a request (no connection reuse), or ~92 microseconds to open
requests takes about 1078 CPU-microseconds to open a new connection and issue a request (no connection reuse), or ~552 microseconds to open


front: What is ZooKeeper?
back:
Apache ZooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services. All of these kinds of services are used in some form or another by distributed applications. Each time they are implemented there is a lot of work that goes into fixing the bugs and race conditions that are inevitable. Because of the difficulty of implementing these kinds of services, applications initially usually skimp on them, which make them brittle in the presence of change and difficult to manage. Even when done correctly, different implementations of these services lead to management complexity when the applications are deployed.
Has Java and C interfaces.


front: What is orthogonality?
back:
In mathematical terms, it means being perpendicular.

Orthogonality in programming language design is the ability to use various language features in arbitrary combinations with consistent results.

Orthogonality is a system design property which guarantees that modifying the technical effect produced by a component of a system neither creates nor propagates side effects to other components of the system. Typically this is achieved through the separation of concerns and encapsulation, and it is essential for feasible and compact designs of complex systems. The emergent behavior of a system consisting of components should be controlled strictly by formal definitions of its logic and not by side effects resulting from poor integration, i.e., non-orthogonal design of modules and interfaces. Orthogonality reduces testing and development time because it is easier to verify designs that neither cause side effects nor depend on them.


front:
When dealing with scaling, how can you deal with rapidly increasing counters, like YouTube video views?

back:
You can add randomness to a monotonic counter, because as long as people can see it is increasing somewhat monotonically, it doesn't need to be 100% accurate. And avoids need to lock it in a transaction.


front: What is exponential backoff and when is it used?
back:
Binary exponential backoff or truncated binary exponential backoff refers to an algorithm used to space out repeated retransmissions of network or other service requests, often as part of congestion avoidance.


front: What does adding jitter in system design help you avoid?
back:
If your system doesn’t jitter then you get thundering herds. Distributed applications are really weather systems. Debugging them is as deterministic as predicting the weather. Jitter introduces more randomness because surprisingly, things tend to stack up.


front: What is an example of adding jitter to a caching system?
back:
Cache expirations. For a popular video they cache things as best they can. The most popular video they might cache for 24 hours. If everything expires at one time then every machine will calculate the expiration at the same time. This creates a thundering herd.
By jittering you are saying randomly expire between 18-30 hours. That prevents things from stacking up. They use this all over the place. Systems have a tendency to self synchronize as operations line up and try to destroy themselves. Fascinating to watch. You get slow disk system on one machine and everybody is waiting on a request so all of a sudden all these other requests on all these other machines are completely synchronized. This happens when you have many machines and you have many events. Each one actually removes entropy from the system so you have to add some back in.


front:
What Python package provides tools for adapting or extending functions and other callable objects, without completely rewriting them?

back:
functools
offers:
Decorators
Comparison
Rich Comparison
Collation Order
Caching
Reducing a Data Set
Generic Functions


front: What is a proxy server?
back:
A proxy server is an intermediate piece of hardware/software that receives requests from clients and relays them to the backend origin servers. Typically, proxies are used to filter requests, log requests, or sometimes transform requests (by adding/removing headers, encrypting/decrypting, or compression).


front: What is collapsed forwarding?
back:
A proxy server can collapse the same (or similar) requests together into one request, and then return the single result to the requesting clients.

Another great way to use the proxy is to not just collapse requests for the same data, but also to collapse requests for data that is spatially close together in the origin store (consecutively on disk).


front: What should be handling requests first, a proxy server or a cache?
back:
Generally it is best to put the cache in front of the proxy. This is because the cache is serving data from memory, it is very fast, and it doesn't mind multiple requests for the same result. But if the cache was located on the other side of the proxy server, then there would be additional latency with every request before the cache, and this could hinder performance.


front: What is the role of a load balancer?
back:
The role is to distribute load across a set of nodes responsible for servicing requests. This allows multiple nodes to transparently service the same function in a system. Their main purpose is to handle a lot of simultaneous connections and route those connections to one of the request nodes, allowing the system to scale to service more requests by just adding nodes.


front: What is a drawback of advanced features in a load balancer?
back:
Advanced features can make problem diagnosis cumbersome. For example, when it comes to high load situations, load balancers will remove nodes that may be slow or timing out (because of too many requests), but that only exacerbates the situation for the other nodes.


front: What is a benefit of adding asynchrony to a system?
back:
It keeps clients from holding connections to servers when waiting for a response for a task that could simply be deferred. This reduces load on servers that are performing writes, for example, and lets them perform a task when ready, not on-demand.


front: What is the difference between a synchronous system and an asynchronous system?
back:
In a synchronous system, there is no differentiation between request and reply, and they therefore cannot be managed separately. In an asynchronous system the client requests a task, the service responds with a message acknowledging the task was received, and then the client can periodically check the status of the task, only requesting the result once it has completed.

While the client is waiting for an asynchronous request to be completed it is free to perform other work, even making asynchronous requests of other services.


front: Does asynchronous code tend to be CPU-bound or I/O bound?
back:
Asynchronous code tends to be CPU bound, because anything that would block is simply deferred to later, until the blocking operation completes. This means that threads in asynchronous / non-blocking applications are much more likely to use their full time quantum before the kernel scheduler preempts them.


front: What is the optimal number of threads?
back:
And if there's the same number of runnable threads as there are hardware threads, the kernel is very likely to reschedule threads on the same core, which significantly helps performance.


front: What is the typical time slice for a process on a Linux box?
back:
Linux kernels are often compiled with HZ=100, which entails that processes are given time slices of 10ms.


front: How does Linux handle CPU affinity?
back:
Default Linux kernels don't do a good job at keeping CPU affinity, even on idle machines. You must explore alternative schedulers or use taskset or cpuset to control affinity yourself.


front: What is futex?
back:
A futex (short for "fast userspace mutex") is a Linux kernel system call that programmers can use to implement basic locking, or as a building block for higher-level locking abstractions such as semaphores and POSIX mutexes or condition variables.


front: How do context switches perform under virtualization?
back:
On average, it's 2.5x to 3x more expensive to do a context switch when using virtualization. My guess is that this is due to the fact that the guest OS can't update the page table itself, so when it attempts to change it, the hypervisor intervenes, which causes an extra 2 context switches (one to get inside the hypervisor, one to get out, back to the guest OS).


front: What is a Frame Check Sequence?
back:
The Frame Check Sequence (FCS) field is used to determine if errors occurred in the transmission and reception of the frame. Error detection is added at the Data Link layer because this is where data is transferred across the media.


front: How does Google handle a search request?
back:
Scatter/gather
In this model, the dispatcher multicast the request to all workers of the pool. Each worker will compute a local result and send it back to the dispatcher, who will consolidate them into a single response and then send back to the client.


front: What is an example of bulk synchronous processing?
back:
Parallel Graph Transformation

The main goal of Graph transformation is to modify the graph. This include modifying the properties of existing nodes and arcs, creating new arcs / nodes and removing existing arcs / nodes. The modification logic is provided by a user-defined function, which will be applied to all active nodes.


front: Execution Orchestrator
back:
This model is based on an intelligent scheduler / orchestrator to schedule ready-to-run tasks (based on a dependency graph) across a clusters of dumb workers.

example: Microsoft Dryad


front: What are balancing methods used by load balancers?
back:
assignment of a request: random, round-robin, random with weighting for machine capacity, etc
matched with current status (available for requests, not responding, elevated error rate, etc).


front: What are the 3 choices in load balancers? The 3 kinds, not balancing mechanisms.
back:
- Smart client, a software based mechanism for determining the availability of a server.
- Hardware load balancer, such as Citrix NetScaler, are remarkably expensive, and they are also "non-trivial" to configure.
- Software load balancer: HAProxy


front: What is write-through cache?
back:
Write-through cache directs write I/O onto cache and through to underlying permanent storage before confirming I/O completion to the host. This ensures data updates are safely stored on, for example, a shared storage array, but has the disadvantage that I/O still experiences latency based on writing to that storage. Write-through cache is good for applications that write and then re-read data frequently as data is stored in cache and results in low read latency.


front: What is write-back cache?
back:
Write-back cache is where write I/O is directed to cache and completion is immediately confirmed to the host. This results in low latency and high throughput for write-intensive applications, but there is data availability exposure risk because the only copy of the written data is in cache. As we will discuss later, suppliers have added resiliency with products that duplicate writes. Users need to consider whether write-back cache solutions offer enough protection as data is exposed until it is staged to external storage. Write-back cache is the best performing solution for mixed workloads as both read and write I/O have similar response time levels.


front: What is read-through cache?
back:
An item is accessed from cache, and if it's a cache miss, the data will be read from persistent storage (perhaps with a callback) and then placed into cache. The response is then sent back to the host.


front: What is HDFS?
back:
Hadoop File System (HDFS) is a Java-based file system that provides scalable and reliable data storage, and it was designed to span large clusters of commodity servers.


front: What is Hortonworks?
back:
Hortonworks is a software company focused on the development and support of Apache Hadoop, a framework that allows for the distributed processing of large data sets across clusters of computers.


front: What is a platform layer?
back:
Web applications to communicate with a platform layer which in turn communicates with your databases. 

First, separating the platform and web application allow you to scale the pieces independently. If you add a new API, you can add platform servers without adding unnecessary capacity for your web application tier. 

Second, adding a platform layer can be a way to reuse your infrastructure for multiple products or interfaces (a web application, an API, an iPhone app, etc) without writing too much redundant boilerplate code for dealing with caches, databases, etc.

Third, a sometimes underappreciated aspect of platform layers is that they make it easier to scale an organization. At their best, a platform exposes a crisp product-agnostic interface which masks implementation details. If done well, this allows multiple independent teams to develop utilizing the platform's capabilities, as well as another team implementing/optimizing the platform itself.


front: What is the Paxos algorithm?
back:
Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures.


front: What problem does consistent hashing help solve?
back:
If you're using a caching scheme like server = hash(i) mod m, and one server in the cluster drops out, consistent hashing is needed to avoid swamping your servers when all the caches need to rehash their entities.


front: What is the relationship between consistent hashing and memcache?
back:
Consistent hashing can be used with memcache not even knowing about it.  It is interesting to note that it is only the client that needs to implement the consistent hashing algorithm - the memcached server is unchanged.


front: What are some examples of NoSQL solutions?
back:
Google BigTable
HBase (based on Hadoop)
Hypertable
Amazon DynamoDB
Voldemort
Cassandra
Riak
Redis
CouchDB
MongoDB


front: What is MVCC?
back:
Multiversion concurrency control (MCC or MVCC), is a concurrency control method commonly used by database management systems to provide concurrent access to the database and in programming languages to implement transactional memory.


front: What is the S in SOLID?
back:
The single responsibility principle. There should never be more than one reason for a class to change. We can relate the “reason to change” to “the responsibility of the class”. So each responsibility would be an axis for change.


front: What does concurrent.futures do?
back:
The concurrent.futures modules provides interfaces for running tasks using pools of thread or process workers. The APIs are the same, so applications can switch between threads and processes with minimal changes.


front: What is the O in SOLID?
back:
The Open/Closed Principle (OCP) states that the design and writing of the code should be done in a way that new functionality should be added with minimum changes in the existing code. The design should be done in a way to allow the adding of new functionality as new classes, keeping as much as possible existing code unchanged.
"open for extension / closed for modifications"

--

During the 1990s, the open/closed principle became popularly redefined to refer to the use of abstracted interfaces, where the implementations can be changed and multiple implementations could be created and polymorphically substituted for each other.

In contrast to Meyer's usage, this definition advocates inheritance from abstract base classes. Interface specifications can be reused through inheritance but implementation need not be.


front: What is the L in SOLID?
back:
The Liskov substitution principle (LSP)
We must make sure that the new derived classes just extend without replacing the functionality of old classes. Otherwise the new classes can produce undesired effects when they are used in existing program modules.

Liskov's Substitution Principle states that if a program module is using a Base class, then the reference to the Base class can be replaced with a Derived class without affecting the functionality of the program module.

This principle is just an extension of the Open Close Principle and it means that we must make sure that new derived classes are extending the base classes without changing their behavior.


front: What is the I in SOLID?
back:
The Interface Segregation Principle (ISP) states that clients should not be forced to implement interfaces they don't use. Instead of one fat interface many small interfaces are preferred based on groups of methods, each one serving one submodule.


front: What is the D in SOLID?
back:
Dependency inversion principle (DIP)
High-level modules should not depend on low-level modules. Both should depend on abstractions.
Abstractions should not depend on details. Details should depend on abstractions.


front: What are 3 things CDNs use to ensure availability?
back:
Local clustering can improve fault-tolerance and scalability. Mirroring (deploying clusters in a few locations) and multihoming (using multiple ISPs to connect to the Internet). 
Clustering, mirroring, and multihoming are common approaches for sites with stringent reliability and scalability needs.


front: What is hyper-threading?
back:
Hyper-threading enables a single processor core to be used for two or more concurrent executions with just a little extra hardware.


front: What is DMA?
back:
DMA (Direct Memory Access) allows devices, with the help of the Northbridge, to store and receive data in RAM directly without the intervention of the CPU.


front: Where are SRAM and DRAM used?
back:
SRAMs are used in Caches because of higher speed and DRAMs are used for main memory in a PC because of higher densities.


front: What is the difference between SRAM and DRAM?
back:
DRAM stands for Dynamic Random Access Memory. It is a type of semiconductor memory in which the memory is stored in the form of a charge. Each memory cell in a DRAM is made of a transistor and a capacitor. The data is stored in the capacitor. Capacitors loose charge due to leakage and hence DRAM's are volatile devices. To keep the data in the memory, the device must be regularly refreshed whereas SRAM is static, so it will retain a value as long as power is supplied. SRAM is typically faster than DRAM since it doesn't have refresh cycles. Since each SRAM memory cell is comprised of 6 Transistors unlike a DRAM memory cell, which is comprised of 1 Transistor and 1 Capacitor, the cost per memory cell is far greater in an SRAM compared to a DRAM.


front: What is the difference between a CPU core and a CPU thread?
back:
The difference between a core and a thread is that separate cores have separate copies of (almost) all the hardware resources. The cores can run completely independently unless they are using the same resources–e.g., the connections to the outside - at the same time. Threads, on the other hand, share almost all of the processor’s resources.
Intel’s implementation of threads has only separate registers for the threads and even that is limited, some registers
are shared.


front: What is SMP?
back:
symmetric multi-processor

In symmetric multi-processor (SMP) systems the caches of the CPUs cannot work independently from each other. All processors are supposed to see the same memory content at all times. The maintenance of this uniform view of memory is called “cache coherency”.


front: How does a multi-processor CPU maintain cache coherency?
back:
- A dirty cache line is not present in any other processor’s cache.
- Clean copies of the same cache line can reside in arbitrarily many caches.


front: What is Spanner?
back:
Spanner is a scalable, globally-distributed database designed, built, and deployed at Google. At the highest level of abstraction, it is a database that shards data across many sets of Paxos state machines in datacenters spread all over the world. Replication is used for global availability and geographic locality; clients automatically failover between replicas. Spanner automatically reshards data across machines as the amount of data or the number of servers changes, and it automatically migrates data across machines (even across datacenters) to balance load and in response to failures. Spanner is designed to scale up to millions of machines across hundreds of datacenters and trillions of database rows.


front: What is Marzullo's algorithm?
back:
Marzullo's algorithm, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. A refined version of it, renamed the "intersection algorithm", forms part of the modern Network Time Protocol.


front: What is Google File System?
back:
A scalable distributed file system for large distributed data-intensive applications. It provides fault tolerance while running on inexpensive commodity hardware, and it delivers high aggregate performance to a large number of clients.
It deals with multi-GB and TB files by appending to files, as that is the predominant usage pattern of large data files.


front: What is BNF?
back:
BNF (Backus Normal Form or Backus–Naur Form) is one of the two main notation techniques for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols; the other main technique for writing context-free grammars is the van Wijngaarden form.


front: What is MapReduce?
back:
MapReduce, developed by Google in 2004, is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.


front: What is a Zipf distribution?
back:
The Zipf distribution, sometimes referred to as the zeta distribution, is a discrete distribution commonly used in linguistics, insurance, and the modeling of rare events.


front: What is AddressSanitizer?
back:
AddressSanitizer is a fast memory error detector. AddressSanitizer finds out-of-bounds (for heap, stack, and globals) accesses and use-after-free bugs at the cost of 73% slowdown on average and a 3.4x memory size; the tool has no false positives.
AddressSanitizer uses shadow memory to provide accurate and immediate bug detection. The conventional wisdom is that shadow memory either incurs high overhead through multi-level mapping schemes or imposes prohibitive address space requirements by occupying a large contiguous region. Our novel shadow state encoding reduces our shadow space footprint enough that we can use a simple mapping, which can be implemented with low overhead.
It has been included as a compilation option in LLVM since 3.1.


front: What is transitive closure?
back:
transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops?


front: What is CUDA?
back:
CUDA (Compute Unified Device Architecture) is a parallel computing platform and application programming interface (API) model created by NVIDIA.[1] It allows software developers and software engineers to use a CUDA-enabled graphics processing unit (GPU) for general purpose processing – an approach known as GPGPU. The CUDA platform is a software layer that gives direct access to the GPU's virtual instruction set and parallel computational elements, for the execution of compute kernels.[2]


front: What is Borg?
back:
The first unified container-management system developed at Google. It was built to manage both long-running services and batch jobs.


front: What is MPM?
back:
Within Google, MPM (Midas Package Manager) is used to build and deploy container images. It corresponds to the Docker image registry for Docker containers.


front: What are 3 benefits of containers?
back:
1. Containers encapsulate the application environment, abstracting away many details of machines and operating systems from the application developer and the deployment infrastructure.
2. Because well-designed containers and container images are scoped to a single application, managing containers means managing applications rather than machines. This shift of management APIs from machine-oriented to application oriented dramatically improves application deployment and introspection.
3. Decoupling of image and OS makes it possible to provide the same deployment environment in both development and production, which, in turn, improves deployment reliability and speeds up development by reducing inconsistencies and friction.


front: What is Protocol buffers?
back:
Protocol buffers (aka protobuf) are Google's language-neutral, platform-neutral, extensible mechanism for serializing structured data. IDL-based.

You define how you want your data to be structured once, then you can use special generated source code to easily write and read your structured data to and from a variety of data streams and using a variety of languages.


front: Why is using Protocol buffers better than pickling?
back:
Python pickling doesn't deal well with schema evolution, and also doesn't work very well if you need to share data with applications written in C++ or Java.


front: What is gRPC?
back:
It’s an open source framework for RPC by Google. gRPC uses HTTP/2 and Google’s own Protobuf to provide a scalable and low latency communication. With gRPC comes a new version of Protobuf (proto3) for high performance binary serialization which includes new features and is easier to use than its predecessors.


front: What is Redis?
back:
Redis is an in-memory data structure store, used as database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs and geospatial indexes with radius queries. Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via Redis Sentinel and automatic partitioning with Redis Cluster.


front: What commands can be used to make a Redis queue somewhat reliable?
back:
LPUSH
RPOPLPUSH - pop right, pushing onto another list for processing, atomically,
BRPOPLPUSH - same as above, but blocking
RPOP

Redis is more susceptible to data loss in the event of abrupt termination or power failures.


front: What is RabbitMQ?
back:
RabbitMQ is a messaging broker - an intermediary for messaging.

Messages are routed through exchanges before arriving at queues. RabbitMQ features several built-in exchange types for typical routing logic. For more complex routing you can bind exchanges together or even write your own exchange type as a plugin.

It can be used as a durable queue, work queues, pub/sub, topic handler, and even for rpc.


front: What is pika?
back:
Pika is a pure-Python implementation of the AMQP 0-9-1 protocol that tries to stay fairly independent of the underlying network support library. Can use with RabbitMQ.


front: What is Celery?
back:
Celery is an asynchronous task queue/job queue based on distributed message passing. It is focused on real-time operation, but supports scheduling as well. You use it with a message broker, and it manages the task execution.

The execution units, called tasks, are executed concurrently on a single or more worker servers using multiprocessing, Eventlet, or gevent. Tasks can execute asynchronously (in the background) or synchronously (wait until ready).

The recommended message broker is RabbitMQ, but support for Redis, Beanstalk, MongoDB, CouchDB, and databases (using SQLAlchemy or the Django ORM) is also available.


front: What is ZeroMQ?
back:
A socket-based system, can be used as a queue, pub/sub, etc.

Carries messages across inproc, IPC, TCP, TIPC, multicast.
Smart patterns like pub-sub, push-pull (pipeline), and router-dealer.


front: What is IPC?
back:
Inter-process communication or interprocess communication (IPC) refers specifically to the mechanisms an operating system provides to allow processes it manages to share data. Typically, applications can use IPC categorized as clients and servers, where the client requests data and the server responds to client requests.


front: What is Kafka?
back:
Apache Kafka is a distributed, partitioned, replicated commit log service. It provides the functionality of a messaging system, but with a unique design.


front: What is MessagePack?
back:
MessagePack is an efficient binary serialization format. It lets you exchange data among multiple languages like JSON. But it's faster and smaller. Small integers are encoded into a single byte, and typical short strings require only one extra byte in addition to the strings themselves.

No IDL.


front: What is Avro?
back:
Apache Avro is a data serialization system. IDL-based.
Rich data structures. 
A compact, fast, binary data format. 
A container file, to store persistent data. 
Remote procedure call (RPC).
Code generation is not required to read or write data files nor to use or implement RPC protocols. Code generation as an optional optimization, only worth implementing for statically typed languages.


front: What is a Bloom filter?
back:
A Bloom filter is a data structure used to quickly test membership in a set where the number and size of possible elements would be very large. Too large to keep in memory.
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter). The more elements that are added to the set, the larger the probability of false positives.


front: How can you easily generate multiple hashes for the same element?
back:
Double hashing. This method gives you as many hashes as you need:
hash(x,m) = (hasha(x) + i * hashb(x)) mod m

In Python:
import mmh3
mmh3.hash64('foo') # two 64 bit signed ints, in a tuple
now you have 2 64-bit hashes. Substituting for i gives you multiple hashes for a Bloom filter.


front: What is DFT?
back:
Discrete Fourier Transform - converts a finite sequence of equally-spaced samples of a function into an equivalent-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.


front: What is a cache-oblivious algorithm?
back:
A cache-oblivious algorithm does not mean that the algorithm does not take advantage of the cache; to the contrary, it does so quite effectively. What it means is that the algorithm does not need to know the cache line size; it works effectively for all cache line sizes simultaneously, removing the need to tune or optimize for a given machine.

Optimal cache-oblivious algorithms are known for the Cooley–Tukey FFT algorithm, matrix multiplication, sorting, matrix transposition, and several other problems.


front: How can you augment a splay tree so you can find how many items are between x and y?
back:
Store size of subtrees at each node. 
Find x, splay to root. Each splay, insert, and delete must maintain size in node.
Find y, and along the way add up the sizes in the left subtrees, and 1 for each visited left-hand node.
Splay y to root to ensure balance.


front: What is the Ford-Fulkerson algorithm?
back:
The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a specialization of Ford–Fulkerson.


front: What is the running time for the disjoint set data structure?
back:
Due to merging smaller disjoint sets into larger ones (called union by rank) (during union) and performing path compression (during find), the amortized time per operation is only O(alpha(n)), where alpha(n) is the inverse of the function and A is the extremely fast-growing Ackermann function. Since alpha(n) is the inverse of this function, alpha(n) is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

The worst-case for find() is Theta(log u) where u is the number of unions, and no finds have been done to allow for path compression yet.


front: In testing, what is an oracle?
back:
Software testers and software engineers can use an oracle as a mechanism for determining whether a test has passed or failed. The use of oracles involves comparing the output(s) of the system under test, for a given test-case input, to the output(s) that the oracle determines that product should have.


front: What do you test interfaces with a trust boundary?
back:
With lots of different inputs, including random inputs to ensure that the system can handle or appropriately error out, not crash.


front: What should be avoided to ensure testing is easier/possible?
back:
- static methods and properties
- final keyword
- use of new in methods (use dependency injection)


front: What are some guidelines to keep in mind to not violate the dependency inversion principle?
back:
- No variable should have a concrete class type. An abstract type is better.
- No class should derive from a concrete class.
- No method should override an implemented method of any of its base classes.

These are guidelines and may not be feasible all the time.


front: What is a trap/exception?
back:
A special instruction that a program performs to interrupt the process and give control to the kernel.


front: What does the scheduler do?
back:
Schedulers are special system software which handles process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run.


front: What is separate chaining?
back:
In hash table conflict resolution, each bucket is independent and has some sort of linked list of entries with the same index. The time for hash table operations is the time to find the bucket (which is constant) plus the time for the list operation.

In a good hash table, each bucket has zero or one entries, and sometimes two or three, but rarely more than that. Therefore, structures that are efficient in time and space for these cases are preferred. Structures that are efficient for a fairly large number of entries per bucket are not needed or desirable. If these cases happen often, the hashing function needs to be fixed.


front: What is open addressing?
back:
In hash table conflict resolution, all entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found. When searching for an entry, the buckets are scanned in the same sequence, until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. The name "open addressing" refers to the fact that the location ("address") of the item is not determined by its hash value. (This method is also called closed hashing; it should not be confused with "open hashing" or "closed addressing" that usually mean separate chaining.)


front: Where can octet order (Endianness) problems crop up in files?
back:
In binary files, if you aren't consistent with choosing an order. Files encoded in utf8 or ASCII don't have this issue.


front: What defines a complete binary tree, and give an example?
back:
The same number of nodes at all levels of the tree, except at leaf level where it fills in left to right. A heap stored as an array is an example.


front: What is a 2-3-4 tree?
back:
2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that is commonly used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:

- 2-node has one data element, and if internal has two child nodes;
- 3-node has two data elements, and if internal has three child nodes;
- 4-node has three data elements, and if internal has four child nodes.


front: In a b-tree, how many children are there per node?
back:
root: 1 to 2t-1 keys
non-root: t-1 to 2t-1 keys
t could be up to 100, or more.
There are n keys and n+1 children.
Leaves are all the same level.


front: Give an example of how a b-tree might be organized.
back:
1024 children per node.
Store root in memory.
3 nodes accessed gets us 1024^3 disk pages.
4 nodes accessed gets us 1024^4 disk pages.


front: What is a suffix tree?
back:
A suffix tree is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.

The construction of such a tree for the string S takes time and space linear in the length of S. Once constructed, several operations can be performed quickly, for instance locating a substring in S, locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provide one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.


front: In brief, how does selection sort work?
back:
Find the minimum item on each pass, past the previous minimum, and swap it into the leftmost position after the previous minimum.


front: What is counting sort?
back:
Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.


front: What is radix sort?
back:
Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. 
Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least digit and move towards the most significant digit. MSD radix sorts work the other way around.


front: How to choose q for radix sort?
back:
Choose q within a power of 2 of n. Ensures the number of passes is small. Best rule is n rounded down to the next power of 2.
To save memory, round sqrt(n) down to the next power of 2. Twice as many passes.


front: What is the Day–Stout–Warren (DSW) algorithm?
back:
The Day–Stout–Warren (DSW) algorithm is a method for efficiently balancing binary search trees — that is, decreasing their height to O(log n) nodes, where n is the total number of nodes. Unlike a self-balancing binary search tree, it does not do this incrementally during each operation, but periodically, so that its cost can be amortized over many operations.


front: What is the insertion sort algorithm?
back:
for (i = 0; i < n; ++i) {
    j = i;
    while (j > 0 && a[j - 1] > a[j]) {
        swap(a, j, j - 1);
        j -= 1;
    }
}


front: Give the code for selection sort.
back:
for (i = 0; i < n; ++i) {
    min_index = i:
    for (j = i; j < n; ++j) {
        if (a[j] < a[min_index]) {
            min_index = j;
        }
    }
    swap(a, i, min_index)
}


back: Topological sort
front:
What do you call a linear ordering of a directed graph of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering?


front: What is a good method for performing a topological sort?
back:
1. Calculate in-degree for each node. O(v + e)
2. Go through 0s, add to queue.
3. For each item in queue, look at each connection, and decrement in-degree of each, if they got to 0, add to queue, repeat.


front: What is Prim's algorithm?
back:
def prim(self):
    """
    Returns a dictionary of parents of vertices in a minimum spanning tree
    :rtype: dict
    """
    s = set()
    q = queue.PriorityQueue()
    parents = {}
    start_weight = float("inf")
    weights = {}  # since we can't peek into queue

    for i in self.get_vertex():
        weight = start_weight
        if i == 0:
            q.put(([0, i]))
        weights[i] = weight
        parents[i] = None

    while not q.empty():
        v_tuple = q.get()
        vertex = v_tuple[1]

        s.add(vertex)

        for u in self.get_neighbor(vertex):
            if u.vertex not in s:
                if u.weight < weights[u.vertex]:
                    parents[u.vertex] = vertex
                    weights[u.vertex] = u.weight
                    q.put(([u.weight, u.vertex]))

    return parents


front: What is the pseudocode Kruskal's algorithm?
back:
KRUSKAL(G):
A = ∅
foreach v ∈ G.V:
   MAKE-SET(v)
foreach (u, v) in G.E ordered by weight(u, v), increasing:
   if FIND-SET(u) ≠ FIND-SET(v):
      A = A ∪ {(u, v)}
      UNION(u, v)
return A


front: What is Kruskal's algorithm?
back:
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).


front: How can you get the strongly connected components of a graph?
back:
1. DFS - calculate the finish times for each node
2. Reverse the edges in the graph
3. Call DFS on nodes in reverse graph in reverse order of finishing times.


front: How to find the longest path on a weighted DAG?
back:
1. Set all edges to their negative weight.
2. Topological sort 
3. follow the topological sort, relaxing edges


front: What is the diameter of a graph?
back:
The shortest path of the farthest nodes. That is, it is the greatest distance between any pair of vertices. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.


front: In plain words, how does Kruskal's algorithm work?
back:
1. Create a set T and list for result
2. Make a list of all edges in G
3. Sort edges by weight, from least to greatest.
4. Iterate edges in sorted order.
5. For each edge, if u and v are not in T, add u and v to T, and add edge to result list.


front: What can most dynamic programming problems be expressed as?
back:
Finding the shortest path in a DAG. Formulating it this way ensures you can solve it in linear or linearithmic time.


front: What is the general outline of a backtracking algorithm?
back:
def solve(conf):
    if (no more choices):
        return conf
    
    choices = get_available_choices

    for choice in choices:
        c = pick one
        if solve(conf using c):
            return true
        unmake choice c

    return false


front: What kinds of problems is dynamic programming best suited for?
back:
- optimizing left to right sequences (strings, tree nodes as array, permutations)
- search all possibilities while storing results to avoid recomputing


front: What is the Floyd-Warshall algorithm?
back:
The Floyd–Warshall algorithm is a dynamic programming algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).


front: What is a Markov chain?
back:
A Markov chain consists of states linked by transitions labeled with probabilities. The states do not have to be words. They could represent any state.


front: What does it mean when a problem is NP-Hard?
back:
It is as hard as any other problem in NP. A problem X is NP-Hard if every problem Y in NP-Hard reduces to X.


front: Name some NP-Complete problems.
back:
- tsp
- knapsack problem
- satisfiability
- 3D matching
- tricoloring
- subset sum
- rectangle packing
- bin packing
- vertex cover
- set cover


front: What is one way of doing approximate traveling salesman?
back:
Select a vertex as root.
Build a MST.
Do a preorder traversal, store nodes in H.
Return H (a Hamiltonian cycle)


front: How can an LRU cache be implemented with a linked list?
back:
When an item is accessed, it moves to the head of the list.
The trailing items can be overwritten with new items, or removed.


front: What does Skylake architecture look like?
back:
Skylake: 

L1 Data cache = 32 KB, 64 B/line, 8-WAY. 64 cache lines per cache way
L1 Instruction cache = 32 KB, 64 B/line, 8-WAY. 64 cache lines per cache way
L2 cache = 256 KB, 64 B/line, 4-WAY
L3 cache = 8 MB, 64 B/line, 16-WAY


front: What is a TLB?
back:
A translation lookaside buffer (TLB) is a cache that memory management hardware uses to improve virtual address translation speed. The majority of desktop, laptop, and server processors includes one or more TLBs in the memory management hardware, and it is nearly always present in any hardware that utilizes paged or segmented virtual memory.


front: In a direct mapped or set associative cache, what is special about the cache size?
back:
Main memory is divided into pages, and a memory page maps directly to the cache way size. So an item in a cache page can be mapped to any one of 8 cache ways in an 8-way associative cache. A direct mapped cache simply has one cache way, but it works the same way.


front: Is it always letters we are looking for in compression?
back:
No. Hardly.
We are looking to compress discrete symbols, not letters. If we have a few words, they could be symbols.
We try to balance longest chains of symbols and the lowest entropy.


front: What is Zopfli?
back:
Zopfli is data compression software that encodes data into DEFLATE, gzip and zlib formats. It achieves higher compression than other DEFLATE/zlib implementations, but takes much longer to perform the compression. It was first released in February 2013 by Google.


front: What is the Chinese remainder theorem?
back:
If one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.


front: What is polymorphism in OO?
back:
A property of OO in which an abstraction operation may be performed in different ways in different classes, but share an interface.
Also can mean multiple methods of the same name but different signature.


front: What is dynamic binding?
back:
Dynamic binding, also called dynamic dispatch, is the process of linking procedure call to a specific sequence of code (method) at run-time. Dynamic binding is also known as late binding or run-time binding. Dynamic binding is an object oriented programming concept and it is related with polymorphism and inheritance.


front: What is an interface in OO?
back:
Similar to an abstract data type, but simply defines the expected behaviors of a class, but does not suggest an implementation.


front: What is a framework?
back:
A reusable piece of software that implements a generic solution to a generalized problem. It saves time by being a close model of the problem domain and can reach 100% with details coded by the implementer.


front: What is an OCL?
back:
Object constraint language. A specification language designed to formally specify constraints in software modules. An OCL expression specifies a logical fact about the system that must remain true.


front: What is the Chain of Responsibility pattern?
back:
Avoid coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it.


front: What is the Command pattern?
back:
Encapsulate a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations.


back: Chain of Responsibility
front:
What design pattern avoids coupling the sender of a request to its receiver by giving more than one object a chance to handle the request?


back: Command pattern
front:
What design pattern encapsulates a request as an object, thereby letting you parameterize clients with different requests?


front: What is the Interpreter pattern?
back:
Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.


back: Interpreter pattern
front:
What design pattern, given a language, defines a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language?


front: What is the Iterator pattern?
back:
Provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation.


back: Iterator pattern
front:
What design pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation?


front: What is the Mediator pattern?
back:
Defines an object that encapsulates how a set of objects interact. Promotes loose coupling by keeping objects from referring to each other explicitly and it lets you vary their interactions independently.


front: What is the Memento pattern?
back:
Without violating encapsulation, capture and externalize an object's internal state so that the object can be restore to this state later.


back: Memento pattern
front:
What design pattern captures and externalize an object's internal state so that the object can be restore to this state later?


front: What is the Observer pattern?
back:
Defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.


back: Observer pattern
front:
What design pattern defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically?


front: What is the State pattern?
back:
Allows an object to alter its behavior when its internal state changes. The object will appear to change its class.


front: What is the Strategy pattern?
back:
Defines a family of algorithms, encapsulates each one, and makes them interchangeable. Lets the algorithm vary independently from clients that use it.


back: Strategy pattern
front:
What design pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable, and lets the algorithm vary independently from clients that use it?


front: What is the Template Method pattern?
back:
Defines the skeleton of an algorithm in an operation, deferring some steps to subclasses. Lets subclasses redefine certain steps of an algorithm without changing the algorithm's structure.


back: Template Method pattern
front:
What design pattern defines the skeleton of an algorithm in an operation, deferring some steps to subclasses?


front: What is the Visitor pattern?
back:
Represents an operation to be performed on the elements of an object structure. Lets you define a new operation without changing the classes of the elements on which it operates.


back: Visitor pattern
front:
What design pattern represents an operation to be performed on the elements of an object structure and lets you define a new operation without changing the classes of the elements on which it operates?


front: What is the Adapter pattern?
back:
Converts the interface of a class into another interface clients expect. Lets classes work together that couldn't otherwise because of incompatible interfaces.


back: Bridge pattern
front:
What design pattern decouples an abstraction from its implementation so that the two can vary independently?


front: What is the Composite pattern?
back:
Compose objects into tree structures to represent part-whole hierarchies. Lets clients treat individual objects and compositions of objects uniformly.


front: What is the Decorator pattern?
back:
Attaches additional responsibilities to an object dynamically. Provides a flexible alternative to sub-classing for extending functionality.


back: Decorator pattern
front:
What design pattern attaches additional responsibilities to an object dynamically and provides a flexible alternative to sub-classing for extending functionality?


front: What is the Facade pattern?
back:
Provides a unified interface to a set of interfaces in a subsystem. Defines a high-level interface that makes the subsystem easier to use.


back: Facade pattern
front:
What design pattern provides a unified interface to a set of interfaces in a subsystem and defines a high-level interface that makes the subsystem easier to use.


front: What is the Abstract Factory pattern?
back:
Provides an interface for creating families of related or dependent objects without specifying their concrete class.


back: Abstract Factory pattern
front:
What design pattern provides an interface for creating families of related or dependent objects without specifying their concrete class?


front: What is the Builder pattern?
back:
Separates the construction of a complex object from its representation, so the same construction process can create different representations.


back: Builder pattern.
front:
What design pattern separates the construction of a complex object from its representation, so the same construction process can create different representations?


front: What is the Factory Method pattern?
back:
(Technically it's an idiom)
Defines an interface for creating an object, but lets subclasses decide which class to instantiate. Lets a class defer instantiation to subclasses.


back: Factory method (technically an idiom, not a design pattern)
front:
What design pattern defines an interface for creating an object, but lets subclasses decide which class to instantiate?


front: What is the Prototype pattern?
back:
Specifies the kinds of objects to create using a prototypical instance, and creates new objects by copying this prototype.


back: Prototype pattern
front:
What design pattern specifies the kinds of objects to create using a prototypical instance, and creates new objects by copying this prototype?


back: Singleton pattern
front:
What design pattern ensures a class only has one instance and provides a global point of access to it?


front: What is the Law of Demeter?
back:
Each unit should have only limited knowledge about other units - only units "closely" related to the current unit. Each unit should only talk to friends, not strangers. Only talk to immediate friends.


front: What does an exclusive cache style?
back:
An eviction from L1D pushes the cache line down into L2, which has the same cache line size. Each eviction is progressively more expensive.


front: What is the Fast Fourier Transform?
back:
A fast Fourier transform (FFT) algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse. Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors.


front: What is a skip list?
back:
A data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one. Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for.

A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4).


front: What operations does a van Emde Boas tree support and what are the time complexities?
back:
All are O(log log M), where M is the total number of items that can be stored = 2^m
Or O(log m) where m is the actual number of items stored
Space: O(M)

Search
Insert
Delete
Predecessor
Successor


front: What are the complexities for treap operations?
back:
For all the basic maintenance operations, they are O(log n) average case and O(n) worst case.
- Search
- Insert
- Delete

For these operations, O(m log n/m) for treaps of sizes m and n, with m ≤ n. 
- union
- intersection
- difference


front: What are Catalan numbers?
back:
Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They can be thought of as the set of balanced parentheses. 
Do not think of Catalan numbers as pseudoprimes. There are only 3 Catalan pseudoprimes.


front: What is Karatsuba multiplication?
back:
It reduces the multiplication of two n-digit numbers to at most n^1.585 single-digit multiplications in general (and exactly n^log(base2)3 when n is a power of 2). The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.


front: How does a Graham scan work in finding convex hull?
back:
At O(n log n), uses a sort and then a simple single pass of all the points, and making only left turns as it goes around the perimeter counter-clockwise. When the next point is a right turn, it backtracks past all points (using a stack and popping points off) until that turn turns into a left turn.


front: How does the Jarvis march work in finding convex hull?
back:
Starting with the leftmost point p: 
Go through each point to the right of that point, and using p as a pivot, find which point is the most clockwise. O(n)
Get the most clockwise point as the new p - O(1)
Loop again with new p

This continues until the starting point is reached O(h) - where h is the number of hull points


front: What are 3 situations where timing of inputs important in testing?
back:
- when SUT interacts directly with hardware devices
- when SUT interfaces with other machines on the network
- SUT is multithreaded


front: What is a mock object?
back:
An object used to replicate the interfaces and interactions of a larger system that can be bolted on to the SUT.


front: What is system testing?
back:
- not concerned with internals
- does system as a while perform acceptably for the important use cases


front: What is differential testing?
back:
Running test inputs into 2 different implementations and then testing for equality. This is useful for testing multiple versions of the software.


front: What does code coverage not tell you?
back:
- missing errors of omission
- code that misses a specification item
- does not tell us that code looped the correct number of times


front: What should you do when you discover that not all code is covered?
back:
Don't blindly write tests to cover all cases.
Rethink the tests. Perhaps they are interpreting the functionality incorrectly.


front: What are some coverage metrics?
back:
- line coverage
- statement coverage (multiple statements on a line)
- branch coverage
- mc/dc coverage
- loop coverage


front: What is mc/dc coverage?
back:
modified condition / decision

- Required for certain types of avionics software
- Tests every possible branch and condition


front: What is infeasible code?
back:
Code that can never be true.
Infeasible code is code that is either not forward- or not backward-reachable. Infeasible code is not necessarily an error but it is a good indicator that something is wrong with the code and, e.g., in avionics, infeasible code is forbidden by current standards.


front: What is a skip list?
back:
A data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items.
O(log N) expected time for all operations, O(N) worst case.


front: What is a treap?
back:
Tree + heap
A random priority is assigned to every key and must maintain two properties:
- They are in order with respect to their keys, as in a typical binary search tree
- They are in heap order with respect to their priorities, that is, no key has a key of lower priority as an ancestor
O(log N) expected time for all operations, O(N) worst case.


front: What is a max-heap?
back:
A queue in which each element has a "priority" assigned to it. Elements with higher priorities are served before lower priorities.


front: What is a binary heap?
back:
A collection of keys arranged in a complete heap-ordered binary tree, represented in level order in an array (not using the first entry). The parent of the node in position k is in position [k/2] and the two children of the node in position k are in position 2k and 2k+1.


front: What are heuristics?
back:
Any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Heuristics can be mental shortcuts that ease the cognitive load of making a decision. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgment, stereotyping, profiling, or common sense


front: What is internal sorting?
back:
An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. For sorting larger datasets, it may be necessary to hold only a chunk of data in memory at a time, since it won't all fit. The rest of the data is normally held on some larger, but slower medium, like a hard-disk. Any reading or writing of data to and from this slower media can slow the sortation process considerably.


front: What is external sorting?
back:
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.

Mergesort is typically preferred.


front: What are long-term issues involved in machine learning?
back:
- technical debt
- lack of clear abstraction barriers 
- changing anything changes everything
- feedback loop - usage based on your model changes the model
- attractive nuisance (using a successful model in one domain where it doesn't fit in another)
- non-stationarity - stick with current data, or get new, and how much of old data to reuse
- tracking data dependencies - where did the data come from, how to get new data


front: What is supervised learning?
back:
Supervised learning is the machine learning task of inferring a function from labeled training data. The training data consist of a set of training examples. In supervised learning, each example is a pair consisting of an input object (typically a vector) and a desired output value (also called the supervisory signal).


front: What is a regression problem?
back:
One that predicts a continuously valued output. May refer specifically to the estimation of continuous response variables, as opposed to the discrete response variables used in classification.


front: What is a classification problem?
back:
The problem of identifying to which of a set of categories (sub-populations) a new observation belongs, on the basis of a training set of data containing observations (or instances) whose category membership is known.


front: What is unsupervised learning?
back:
Unsupervised learning is the machine learning task of inferring a function to describe hidden structure from unlabeled data. Since the examples given to the learner are unlabeled, there is no error or reward signal to evaluate a potential solution. This distinguishes unsupervised learning from supervised learning and reinforcement learning.


front: What is gradient descent?
back:
Gradient descent is a first-order iterative optimization algorithm. To find a local minimum of a cost function using gradient descent, one takes steps proportional to the negative of the gradient (partial derivative or tangent) of the function at the current point.


front: Why is feature scaling important?
back:
Without feature scaling, it can take gradient descent much longer to find the local minimum. The function may oscillate in small movements for much longer.


front: How can you calculate mean normalization over a set of features?
back:
for each x: xi = (xi - avg(x)) / (max_x - min_x)

(max_x - min_x) can be replaced with the standard deviation


front: How can you get your data to fit better using higher order terms in linear regression?
back:
You can take the data and square it, cube it, etc. 

x1 = (somevalue)^2
x7 = (somevalue)^4

This is applied to data, not the function. The function still is theta1*x1 + theta2*x2, etc


front: What can affect invertibility in a matrix?
back:
- 2 more more features are linearly dependent or redundant (size in meters and size in ft) - remove redundant features
- too few training examples (m) to features (n): m <= n  (remove some features or use regularization)


front: What is the normal equation?
back:
An equation that can minimize J(theta), solving for theta, instead of using gradient descent.

Also called ordinary least squares (OLS) or linear least squares, it's a method for estimating the unknown parameters in a linear regression model, with the goal of minimizing the sum of the squares of the differences between the observed responses in the given dataset and those predicted by a linear function of a set of explanatory variables.


front: What is a dot product?
back:
The dot product of two vectors is the sum of their componentwise products.
v_1 * w_1 + ... + v_n * w_n


front: What is the mode?
back:
Most-common value(s) in a set of data. Could have more than one if there are 2 subsets with the same number of values.


front: What is dispersion?
back:
Dispersion refers to measures of how spread out our data is. Typically they’re statistics for which values near zero signify not spread out at all and for which large values (whatever that means) signify very spread out.


front: What is a random variable?
back:
A random variable is a variable whose possible values have an associated probability distribution.

A very simple random variable equals 1 if a coin flip turns up heads and 0 if the flip turns up tails. A more complicated one might measure the number of heads observed when flipping a coin 10 times or a value picked from range(10) where each number is equally likely.


front: What is PCA and what is it used for?
back:
Principal component analysis. We use it to extract one or more dimensions that capture as much of the variation in the data as possible.


front: What is a model?
back:
A specification of a mathematical (or probabilistic) relationship that exists between different variables.


front: What is quick select?
back:
A selection algorithm to find the kth smallest element in an unordered list. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side - the side with the element it is searching for. This reduces the average complexity from O(n log n) to O(n).


front: What is preemption?
back:
Preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch.


front: What is an inverted index?
back:
An index data structure storing a mapping from content, such as words or numbers, to its locations in a database file, or in a document or a set of documents (named in contrast to a Forward Index, which maps from documents to content). The purpose of an inverted index is to allow fast full text searches, at a cost of increased processing when a document is added to the database.


front: What is set partition?
back:
A partitioning of elements of some universal set into a collection of disjointed subsets. Thus, each element must be in exactly one subset.


front: What is a maximum spanning tree?
back:
A spanning tree of a weighted graph having maximum weight. It can be computed by negating the edges and running either Prim's or Kruskal's algorithms.


front: What is a minimum product spanning tree and when would you use it?
back:
The cost of a tree is the product of all the edge weights in the tree, instead of the sum of the weights. Since log(a*b) = log(a) + log(b), the minimum spanning tree on a graph whose edge weights are replaced with their logarithms gives the minimum product spanning tree on the original graph.
You would use it to minimize the product.


front: What is a rolling hash?
back:
A rolling hash (also known as a rolling checksum) is a hash function where the input is hashed in a window that moves through the input.

One of the main applications is the Rabin-Karp string search algorithm, which uses the rolling hash.


front: What is the Rabin-Karp algorithm?
back:
Compute hash codes of each substring whose length is the length of s, such as a function with the property that the hash code of a string is an additive function of each individual character. Get the hash code of a sliding window of characters and compare if the hash matches.


front: What is sharding?
back:
Sharding is a type of database partitioning that separates very large databases the into smaller, faster, more easily managed parts called data shards.


front: What is von Neumann Architecture?
back:
A model for modern computer organization created by John von Neumann, that had two main features:
1) Both data & instructions are stored in the same place
2) Units that store information are different from units that process information


front: What is the fetch-execute cycle?
back:
A 4 part system that describes how actions are performed in the CPU. There are 4 parts to this cycle:
1) Fetch instructions
2) Decode instructions
3) Get data if needed
4) Execute the instructions


front: What does a Control Unit (CU) do?
back:
Controls, organizes and deals with all the process and instruction the CPU receives. It is also in charge of the Fetch-Execute Cycle. Has two special purpose registers: the Instruction Register and the Program Counter.


front: What is the Bellman–Ford algorithm?
back:
An algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.


front: What is a Hamiltonian cycle?
back:
Given an undirected graph G = (V, E), does there exist a simple
cycle Γ that contains every node in V ?
Certificate is a permutation of the n nodes, contain each node in v exactly once, there is an edge btw each pair of adj nodes in the permutation.


front: What is the set cover problem?
back:
Given a set U of elements, a collection S1, S2, ..., Sm of subsets of
U, and an integer k, does there exist a collection of ≤ k of these sets whose union is equal to U ?


front: How would you divide up a data set for training and testing?
back:
Split your data set, so that two-thirds of it is used to train the model, after which we test/measure the model’s performance on the remaining third.


front: How would you split up a data set in order to choose from multiple models?
back:
In such a situation, you should split the data into three parts: a training set for building models, a validation set for choosing among trained models (called the cross-validation set), and a test set for judging the final model.


front: What is the trade-off between precision and recall?
back:
A model that predicts “yes” when it’s even a little bit confident will probably have a high recall but a low precision; a model that predicts “yes” only when it’s extremely confident is likely to have a low recall and a high precision.

Alternatively, you can think of this as a trade-off between false positives and false negatives. Saying “yes” too often (high recall) will give you lots of false positives; saying “no” too often will give you lots of false negatives (high precision).


back: One thing to try is adding more features.
front:
What can you do when your model has high bias (which means it performs poorly even on your training data)?


front: What can you do if your model suffers from overfitting due to high variance?
back:
You can remove features. Another solution is to obtain more training examples (if you can).
Or use regularization.


front: What is L-BFGS?
back:
Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm using a limited amount of computer memory. It is a popular algorithm for parameter estimation in machine learning.


front: How should you initialize Theta for a neural network?
back:
Initialize as a matrix of random reals between 0 and 1. Constrain within a range of +/- epsilon using Theta * 2*epsilon - epsilon.


back: The number of classes you are classifying.
front:
What are the number of neurons (units) at the output layer of a neural network performing classification?


front: How many hidden layers should there be in a neural network?
back:
Start with 1 as a default, and if more than one, have the same number of units at each layer. The more the better. The number of units in each hidden layer should be more than, or a multiple of, the input units.


back: The error decreases, but too high a degree of polynomial will cause overfitting.
front:
Machine learning: What tends to happen with the training error in a linear model as the degree of polynomial increases?


back: It starts high (high bias) and decreases, reaching a minimum, and then increases (high variance).
front:
Machine learning: What tends to happen with the cross-validation error in a linear model as the degree of polynomial increases?


