Coding university Flashcards
What is Hamming Code?
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.
Using bitwise operations, how would you test that a number is a power of 2
bool isPowerOfTwo = (x & (x - 1);
What does ELF stand for?
Executable and Linkable Format. It’s a common standard file format for executables, object code, shared libraries, and core dumps.
example of a latency device
CPU core
example of a throughput device
GPU core
What is the Hamming Distance?
A number used to denote the number of differences between two binary strings of the same length.
What are the 5 steps of the compiling process?
Lexical Analysis
Parsing
Semantic Analysis
Optimization
Code Generation
What is parsing?
Combining tokens and groups of tokens into a tree structure (a parse tree).
What is lexical analysis?
The process of dividing program text into words or tokens.
What is code generation?
Producing a translation from a high-level program to assembly code. (Linker and Archiver taker over from here to produce machine code)
How would you turn OFF the 3rd bit from the end in a bitstring?
x &= ~(1 «_space;2)
Write a function that calculates the Hamming distance.
def hamming_distance(x, y):
difference = x ^ y
count = 0
while difference != 0:
count += 1
difference &= difference - 1
return count
Write a function to calculate the Hamming weight of an integer. (Kernighan method)
int countSetBits(int n) {
int count = 0;
while (n) {
n = n & (n - 1); \++count;
}
return count;
}
Write a function that calculates the Hamming weight in constant time. Divide and Conquer strategy
int countSetBits(unsigned int n) {
n = n - ((n»_space; 1) & 0x55555555);
n = (n & 0x33333333) + ((n»_space; 2) & 0x33333333);
n = (n + (n»_space; 4)) & 0x0F0F0F0F;
n = n + (n»_space; 8);
n = n + (n»_space; 16);
return n & 0x0000003F;
}
Write a function that tells you if a number is even, using bitwise operation
def is_even(x):
return x & 1 == 0
Write a function to add 2 integers using bitwise operations.
def add(a, b):
while a:
c = b & a
b ^= a
c <<= 1
a = c
return b
Write a function to get the sign of an integer
def get_sign(x):
return -(x < 0)
Write a function to calculate the absolute value of a 32-bit integer
def myabs(x):
high_bit_mask = x >> 31 return (x ^ high_bit_mask) - high_bit_mask
What is a red-black tree?
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
What is a splay tree?
A self-adjusting binary search tree where recently accessed elements are moved to the root so they are quick to access again.
What is a treap?
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
What is typical cache line size?
64 bytes. 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
What is latency?
Latency is the delay from input into a system to desired outcome. The time interval between between a stimulus and response.
What is a y-fast trie?
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.
What is an x-fast trie?
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.
What is a van Emde Boas tree?
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 details —-
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.
What is a compressed trie?
It’s a trie where the non-branching paths are compacted into a single edge.
What relationship of the keys do you lose with a hash table?
The ordering of the keys.
Is quicksort stable?
No
Can quicksort be done in-place?
Yes
Can merge sort be done in-place?
No. It requires O(n) space
Is merge sort stable?
Yes
Is insertion sort stable?
Yes
Can insertion sort be done in-place?
Yes
Can selection sort be done in-place?
Yes
Is selection sort stable?
No
Is heap sort stable?
No
Can heap sort be done in-place?
Yes
Write merge sort in C (check answer carefully)
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);
}
}
Write a MergeSort class in Python (check answer carefully)
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
Write quick sort in C with only one method and random pivot (check answer carefully)
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);
}
}
Write a QuickSort class in Python (check answer carefully)
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)
In what case would perfect hashing be practical?
When you don’t need to support inserts or deletes. The data is static.
How does perfect hashing handle collisions?
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.
What is the optimal load factor for a hash table?
O(sqrt(n))
What is the expected load factor for a hash table?
n/m, where n = items, m = buckets) n/m is also called alpha.
What is the technical running time for operations on a hash table?
O(1 + alpha), where alpha is the load factor (n/m). Table doubling operations are amortized.
What is the worst-case search time of perfect hashing?
O(1)
What is the worst-case space required for perfect hashing?
O(n)
What’s the best-case running time of binary search?
O(1) - we get lucky and find the element right at the midpoint.
What’s the worst-case running time of binary search?
O(log n)
What are the downsides of using an adjacency matrix to represent a graph?
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.
When is using an adjacency list expensive?
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.
When are adjacency lists most useful?
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.
What is the space required for a graph using an adjacency list?
O(n + e)
Given a fully balanced binary tree with x nodes, what is the height of the tree in nodes?
log(base2) x + 1
Given a fully balanced k-ary tree with x nodes, what is the height of the tree in nodes?
log(basek) x + 1
A binary tree with height h can contain at most how many nodes?
2^(h+1) − 1 nodes
For a k-ary tree with height h, the upper bound for the maximum number of leaves is:
k^h
What is the complexity of Dijkstra’s shortest-path algorithm?
O(e log v), where e is the number of edges.
It must scan each edge, and gets and updates values on the heap.
What is a drawback of using an adjacency matrix for an undirected graph?
Half of the entries in the matrix are duplicates.
What is the memory needed to store an adjacency list?
Theta( |V| + |E| )
What is the memory needed to store an adjacency matrix?
Theta(|V|^2)
How would you implement a queue with a linked list?
Use a tail pointer. Push new items at the tail, pop items at the head. Both operations are constant-time.
How would you implement a stack with a linked list?
Push and pop items at the head. Both operations are constant-time.
What preference of nodes vs leaves does preorder traversal give on a tree?
Nodes first, leaves later.
What preference of nodes vs leaves does postorder traversal give on a tree?
Leaves first, internal nodes later.
What could you use in DFS to turn a recursive algorithm into an interative one?
A stack
What do you use to keep track of nodes to visit in BFS?
queue
Using a stack to keep track of unvisited nodes gives what kind of traversal?
DFS
Using a queue to keep track of unvisited nodes gives what kind of traversal?
BFS
In a highly connected graph of n vertices, how many cycles can there be?
(n - 1)! - enumerating is possible (using backtracking), but there will be a lot.
What can use to find if a graph is bipartite?
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.
How can you find a cycle in a graph?
DFS. If you discover an edge that connects to an ancestor (previously discovered vertex), you have a cycle.
What is an articulation vertex?
A vertex of a graph whose deletion disconnects the graph.
How can you find an articulation vertex?
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.
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?
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.
What path does BFS find in a graph?
The shortest path tree from start to all nodes (unweighted)
What’s the upper bound on the number of edges in a graph G(V, E)?
|V|^2
In Python, initialize a list of lists called x with 100 elements.
x = [[] for i in range(100)]
In Python, declare a named tuple called Edge, with attributes vertex and weight.
from collections import namedtuple
Edge = namedtuple(‘Edge’, [‘vertex’, ‘weight’])
What is the optimal substructure property tell us about shortest paths?
That a subpath of a shortest path is also a shortest path.
C++: How would you initialize a vector of 25 integers to all zeroes?
std::vector mynums(25);
What is a Dunder method?
A magic method in Python, such as __getitem__ and __len__.
What is the sum of numbers from 1 to 2^n?
2^(n+1) - 1
The sum of a sequence of powers is roughly equal to the next value in the sequence.
How many ways can you rearrange a string of n unique characters
n!
Permutations.
How many ways can you arrange k characters from n unique characters?
n! / (n - k)!
Permutation of n elements of size k.
How many subsets (ordering doesn’t matter) of size k are there in n unique characters?
n! / k!(n - k)!
This is n choose k.
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]
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
What should you avoid in your base case in recursion
Too many base case scenarios. Just have one base case so you can return as quickly as possible. Avoid ““arm’s length”” recursion.
What is the bandwidth of a graph?
The longest edge in the permutation that gives you the shortest edges.
When talking dynamic programming, what is feasibility?
The rules the algorithm must adhere to in reaching its solution.
When talking dynamic programming, what is optimality?
An algorithm has optimality if the subsolutions of an optimal solution of the problem are themsleves optimal solutions for their subproblems.
What is dynamic programming?
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.
What is the complexity for a naive recursive Fibonacci function
Θ(φ^n), where phi(φ) is the golden ratio (1 + sqrt(5)) / 2.
approx: 1.618
Write a dynamic programming version of computing Fibonacci for n.
def fib(n):
fibValues = [0,1]
for i in range(2, n+1):
fibValues.append(fibValues[i-1] + fibValues[i-2])
return fibValues[n]
Write a dynamic programming implementation of longest common subsequence of 2 strings.
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
What is the difference between __str__ and __repr__?
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.
How many subsets are there in n items?
2^n
What is a contiguously-allocated structures, and give examples
Contiguously-allocated structures are composed of single slabs of memory, and include arrays, matrices, heaps, and hash tables.
What are linked data structures and give examples.
Linked data structures are composed of distinct chunks of memory bound together by pointers, and include lists, trees, and graph adjacency lists.
What are some benefits of arrays?
Constant-time access given the index
- Space efficiency
- Memory locality
Why is memory locality important?
Physical continuity between successive data accesses helps exploit the high-speed cache memory on modern computer architectures.
What are some advantages to linked lists over arrays?
- 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.
What are some advantages to arrays over linked lists?
- 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.
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.
”””””””
- 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)
What is a finalizer in Python?
A finalizer is a destructor, named __del__. __del__() is run when the runtime is about to destroy the object.
What are 2 advantages of reference counting?
- easy to implement
- collects garbage incidentally without large pauses in execution.
What are 2 disadvantages of reference counting?
- it cannot collect circular references
- manipulating reference counts at each assignment is very slow.
What is cyclic garbage collection?
Detects and removes cycles unreachable by the program.
How is garbage collection done in PyPy?
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.
How does mark and sweep work?
(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.
What is copying garbage collection (stop and copy)?
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.
How could you implement an LRU cache?
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.”
What is a direct mapped cache? 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.
What is a fully-associative cache? “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.
Disadvantage of a fully-associative cache?
expensive due to parallel checks
complexity of implementing this scheme
How do some processors handle caching for data and instructions?
There will be a slightly slower (3-4 clocks latency) separate cache for data.
What is an N-way set associative cache? 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.
Is GET idempotent?
YEs
Is PUT idempotent?
Yes
Is POST idempotent?
No
Is DELETE idempotent?
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.
What is idempotent?
The property that a method has side-effects of making more than one identical requests is the same as for a single request.
What is HMAC?
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.
What is a MAC?
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.
How does RSA work?
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.
What is the phi function?
It answers the number of integers <= n that do not share a common factor with n.
What is phi(n) if n is prime?
n-1
What is the gcd of a number a and prime p when p is prime?
1, unless a is a pseudoprime (Carmichael number)
What is the largest output size of SHA-3?
512 bits
What are desirable properties of one-way functions?
- collision resistant
- target collision resistant
- non-malleable
If a one-way function is collision-resistant, does that mean it’s also target collision-resistant?
Yes
If a one-way function is target collision-resistant, does that mean it’s also collision-resistant?
no
What is symmetric key encryption?
There is a known encryption function, and one key is used to encrypt and decrypt. The key has to be shared between 2 parties.
How does Diffie-Hellman key exchange work?
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.
Is Diffie-Hellman key exchange perfect?
No. A man in the middle can intercept one side, and communicate with parties A and B independently.
How is RSA (using product of large primes) better than using NP-Complete algorithms for encryption? 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.
What is Vigenere cipher?
Improvement on Caesar cipher. Letters are shifted based on a shifted dictionary. ““Polyalphabetic cipher””
What is a one-time pad encryption?
“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.”
What is block size in cryptography?
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.
What is the limiting factor of compression?
For lossless compression, it’s entropy. For lossy compression, it’s our acceptance with the amount of loss.
What is LZ* compression based on?
Cataloging the positions and lengths of redundant patterns and combining the values with a dictionary.
What is LZMA?
It’s a variant of LZ77 that uses Markov chains. It’s used in the 7z compression algorithms used in 7-zip.
What is DEFLATE?
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.
How does LZ77-based compression work?
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.
What is Huffman encoding?
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.
What is the primary factor of compression?
Probability of redundant portions of input.
How can you maximize compression?
By deeply analyzing the given input to reduce redundancy as much as possible.
What compression scheme uses Burrows-Wheeler transform?
BZip2
What is the Burrows-Wheeler transform?
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.
For Gzip in web servers, what is the usual setting?
6
What is the min and max compression settings in command line gzip?
0-9
How can you make JSON better compressable with Gzip?
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.
What are Dense Codes?
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.
What is the LZ in LZ compression?
Lempel-Ziv
What is OS hardware virtualization?
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.
What is a process?
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.
What is a context switch?
The copying out and in of register state to switch from running one process to running another.
What is base and bound?
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.
How does the OS know how to handle an interrupt?
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.
How are base and bound enforced?
They are stored in registers. Access is restricted by the hardware.
When a process forks, what happens?
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.
What does fork() return?
It returns the child process id to the parent, and 0 to the child. < 0 if error.
What does wait() do?
Causes the parent process to pause until the child terminates.
What does exec() do?
It’s a system call to change the currently running program to something else.
What comes back from wait()?
on success, returns the process ID of the terminated child; on error, -1 is returned.
What is a signal?
A system call to send a notification to another process.
In a child process, what can you do with fork and then exec?
Create a completely new process and then exit.
What is a shell?
A job control program. It allows a programmer to create and manage a set of programs to do some task.
How does the kernel handle reads and writes?
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.
What’s the difference between the fread, read, fwrite, write I/O calls?
The ones with f are high-level I/O and streamed and buffered by the kernel. The non-f are low-level I/O.
When a system call is made, where are parameters stored?
In registers.
What is a socket?
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.
What sockets are in modern use?
Local sockets to local machine, called UNIX sockets, and TCP/IP and UDP/IP.
What is the GIL?
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.)
When is the GIL released?
During I/O (disk IO, network IO, output to display) including when a thread uses sleep.
“What is a ““tick”” in CPython?”
Approximately 1 machine instruction.
What happens every 100 ““ticks”” in the CPython interpreter?
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.
What is a lock in CPython?
It’s a binary semaphore. It’s not a mutex lock.
What happens when the heap gets too large?
It does a page fault, and the kernel will allocate more memory.
What happens when the heap and stack meet in memory?
A guard page is hit and the process is killed.
Where is information about a process stored?
In a PCB (process control block).
Where is information about a thread stored?
In a TCB (thread control block).
What do multiple threads in the same process share?
Heap, file descriptors, code, static data.
What do threads in a process NOT share?
Registers and stack.
What can happen with thread stacks if one goes into a deep recursion?
One thread’s stack can grow into another thread’s stack and write over it. A guard page can help to protect from that.
What can cause a thread to give control back to the dispatcher?
Thread returns control voluntarily (yield, requesting I/O (which blocks), wait for signal from another thread) or gets preempted by an interrupt.
How long does it take to do a process context switch?
3-4 microseconds.
How long does it take to perform a thread context switch?
100ns
How often do context switches happen?
Every 10-100 ms.
Context switch time increases sharply with the size of what?
The working set - the subset of memory used by the process in a time window. Cache etc.
What happens in a system call to get the OS to switch to kernel mode?
A trap.
How many threads should you run per process?
One per core
How is concurrency accomplished?
By multiplexing CPU time.
What’s the difference between parallelism and concurrency?
Concurrency means running multiple blocks of instructions independently. Parallelism means running instructions at the same time, as on multiple cores at once.
What is oversubscription?
Spawning more threads than available cores.
What is a race condition?
When the outcome of a deterministic procedure becomes non-deterministic based on differences in subprocess timing.
What can you put in place to exclusively use a resource without another process interfering?
A mutex, or even better, a lock guard.
