Coding university Flashcards

Question

What is an x-fast trie?

Answer 1

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.

Answer 2

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.

Answer 3

It's a trie where the non-branching paths are compacted into a single edge.

Answer 4

The ordering of the keys.

Answer 5

No. It requires O(n) space

Answer 6

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); } }

Answer 7

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

Answer 8

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); } }

Answer 9

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)

Answer 10

When you don't need to support inserts or deletes. The data is static.

Answer 11

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.

Answer 12

O(sqrt(n))

Answer 13

n/m, where n = items, m = buckets) n/m is also called alpha.

Answer 14

O(1 + alpha), where alpha is the load factor (n/m). Table doubling operations are amortized.

Answer 15

O(1) - we get lucky and find the element right at the midpoint.

Answer 16

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.

Answer 17

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.

Answer 18

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.

Answer 19

log(base2) x + 1

Answer 20

log(basek) x + 1

Answer 21

2^(h+1) − 1 nodes

Answer 22

O(e log v), where e is the number of edges. It must scan each edge, and gets and updates values on the heap.

Answer 23

Half of the entries in the matrix are duplicates.

Answer 24

Theta( |V| + |E| )

Answer 25

Theta(|V|^2)

Answer 26

Use a tail pointer. Push new items at the tail, pop items at the head. Both operations are constant-time.

Answer 27

Push and pop items at the head. Both operations are constant-time.

Answer 28

Nodes first, leaves later.

Answer 29

Leaves first, internal nodes later.

Answer 30

(n - 1)! - enumerating is possible (using backtracking), but there will be a lot.

Answer 31

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.

Answer 32

DFS. If you discover an edge that connects to an ancestor (previously discovered vertex), you have a cycle.

Answer 33

A vertex of a graph whose deletion disconnects the graph.

Answer 34

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.

Answer 35

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.

Answer 36

The shortest path tree from start to all nodes (unweighted)

Answer 37

x = [[] for i in range(100)]

Answer 38

from collections import namedtuple Edge = namedtuple('Edge', ['vertex', 'weight'])

Answer 39

That a subpath of a shortest path is also a shortest path.

Answer 40

std::vector mynums(25);

Answer 41

A magic method in Python, such as __getitem__ and __len__.

Answer 42

2^(n+1) - 1 The sum of a sequence of powers is roughly equal to the next value in the sequence.

Answer 43

n! Permutations.

Answer 44

n! / (n - k)! Permutation of n elements of size k.

Answer 45

n! / k!(n - k)! This is n choose k.

Answer 46

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

Answer 47

Too many base case scenarios. Just have one base case so you can return as quickly as possible. Avoid ""arm's length"" recursion.

Answer 48

The longest edge in the permutation that gives you the shortest edges.

Answer 49

The rules the algorithm must adhere to in reaching its solution.

Answer 50

An algorithm has optimality if the subsolutions of an optimal solution of the problem are themsleves optimal solutions for their subproblems.

Answer 51

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.

Answer 52

Θ(φ^n), where phi(φ) is the golden ratio (1 + sqrt(5)) / 2. approx: 1.618

Answer 53

def fib(n): fibValues = [0,1] for i in range(2, n+1): fibValues.append(fibValues[i-1] + fibValues[i-2]) return fibValues[n]

Answer 54

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

Answer 55

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.

Answer 56

Contiguously-allocated structures are composed of single slabs of memory, and include arrays, matrices, heaps, and hash tables.

Answer 57

Linked data structures are composed of distinct chunks of memory bound together by pointers, and include lists, trees, and graph adjacency lists.

Answer 58

Constant-time access given the index - Space efficiency - Memory locality

Answer 59

Physical continuity between successive data accesses helps exploit the high-speed cache memory on modern computer architectures.

Answer 60

- 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.

Answer 61

- 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.

Answer 62

""""""" * 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)

Answer 63

A finalizer is a destructor, named __del__. __del__() is run when the runtime is about to destroy the object.

Answer 64

- easy to implement | - collects garbage incidentally without large pauses in execution.

Answer 65

- it cannot collect circular references | - manipulating reference counts at each assignment is very slow.

Answer 66

Detects and removes cycles unreachable by the program.

Answer 67

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.

Answer 68

(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.

Answer 69

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.

Answer 70

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.

Answer 71

expensive due to parallel checks | complexity of implementing this scheme

Answer 72

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.

Answer 73

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.

Answer 74

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

Answer 75

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.

Answer 76

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.

Answer 77

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.

Answer 78

It answers the number of integers <= n that do not share a common factor with n.

Answer 79

1, unless a is a pseudoprime (Carmichael number)

Answer 80

- collision resistant - target collision resistant - non-malleable

Answer 81

There is a known encryption function, and one key is used to encrypt and decrypt. The key has to be shared between 2 parties.

Answer 82

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.

Answer 83

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.

Answer 84

Improvement on Caesar cipher. Letters are shifted based on a shifted dictionary. ""Polyalphabetic cipher""

Answer 85

"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."

Answer 86

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.

Answer 87

For lossless compression, it's entropy. For lossy compression, it's our acceptance with the amount of loss.

Answer 88

Cataloging the positions and lengths of redundant patterns and combining the values with a dictionary.

Answer 89

It's a variant of LZ77 that uses Markov chains. It's used in the 7z compression algorithms used in 7-zip.

Answer 90

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.

Answer 91

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.

Answer 92

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.

Answer 93

Probability of redundant portions of input.

Answer 94

By deeply analyzing the given input to reduce redundancy as much as possible.

Answer 95

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.

Answer 96

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.

Answer 97

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.

Answer 98

Lempel-Ziv

Answer 99

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.

Answer 100

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.

Answer 101

The copying out and in of register state to switch from running one process to running another.

Answer 102

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.

Answer 103

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.

Answer 104

They are stored in registers. Access is restricted by the hardware.

Answer 105

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.

Answer 106

It returns the child process id to the parent, and 0 to the child. < 0 if error.

Answer 107

Causes the parent process to pause until the child terminates.

Answer 108

It's a system call to change the currently running program to something else.

Answer 109

on success, returns the process ID of the terminated child; on error, -1 is returned.

Answer 110

A system call to send a notification to another process.

Answer 111

Create a completely new process and then exit.

Answer 112

A job control program. It allows a programmer to create and manage a set of programs to do some task.

Answer 113

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.

Answer 114

The ones with f are high-level I/O and streamed and buffered by the kernel. The non-f are low-level I/O.

Answer 115

In registers.

Answer 116

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.

Answer 117

Local sockets to local machine, called UNIX sockets, and TCP/IP and UDP/IP.

Answer 118

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.)

Answer 119

During I/O (disk IO, network IO, output to display) including when a thread uses sleep.

Answer 120

Approximately 1 machine instruction.

Answer 121

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.

Answer 122

It's a binary semaphore. It's not a mutex lock.

Answer 123

It does a page fault, and the kernel will allocate more memory.

Answer 124

A guard page is hit and the process is killed.

Answer 125

In a PCB (process control block).

Answer 126

In a TCB (thread control block).

Answer 127

Heap, file descriptors, code, static data.

Answer 128

Registers and stack.

Answer 129

One thread's stack can grow into another thread's stack and write over it. A guard page can help to protect from that.

Answer 130

Thread returns control voluntarily (yield, requesting I/O (which blocks), wait for signal from another thread) or gets preempted by an interrupt.

Answer 131

3-4 microseconds.

Answer 132

Every 10-100 ms.

Answer 133

The working set - the subset of memory used by the process in a time window. Cache etc.

Answer 134

One per core

Answer 135

By multiplexing CPU time.

Answer 136

Concurrency means running multiple blocks of instructions independently. Parallelism means running instructions at the same time, as on multiple cores at once.

Answer 137

Spawning more threads than available cores.

Answer 138

When the outcome of a deterministic procedure becomes non-deterministic based on differences in subprocess timing.

Answer 139

A mutex, or even better, a lock guard.

Answer 140

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

Answer 141

Allows us to receive a return value from a function in a child thread.

Answer 142

A promise to send a parameter to a child thread's function later.

Answer 143

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.

Answer 144

Until the parent process does a wait to receive its exit code.

Answer 145

The multiprocessing module. It supports process Pool and Process for making a pool of worker processes or forking temporary subprocesses.

Answer 146

ThreadPoolExecutor ProcessPoolExecutor Executor objects Future objects

Answer 147

A hardware-invoked context switch. The interrupt handler always runs immediately.

Answer 148

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.

Answer 149

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.

Answer 150

Parallel execution on multiple cores.

Answer 151

Everything about a process: - status - register state (when not in ready state) - PID, User, Executable, Priority - Execution time - Memory space, translation

Answer 152

It disables interrupts and runs to completion.

Answer 153

- new (when being created) - ready - running - waiting (for I/O or event coordination) - terminated (waits for parent process to receive its exit code)

Answer 154

Filter uses a function that returns true or false (predicate). Map uses a function that returns a value.

Answer 155

Using atomic operations to ensure cooperation between threads.

Answer 156

A block of code that you lock before entering, then unlock when leaving. This creates a mutual exclusion on shared data.

Answer 157

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.

Answer 158

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.

Answer 159

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.

Answer 160

Binary semaphore.

Answer 161

A lock and zero or more condition variables for managing concurrent access to shared data.

Answer 162

locks - mutual exclusion condition variables - scheduling constraints

Answer 163

A queue of threads waiting for access to something in a critical section.

Answer 164

It allows sleeping inside a critical section by atomically releasing lock at the time we sleep.

Answer 165

wait(&lock) signal() - signals the next waiting member broadcast() - signals all waiting members

Answer 166

Mesa-scheduling.

Answer 167

- minimize response time - maximize throughput - fairness

Answer 168

CPU cache misses as thread comes back from switching and finds the CPU cache doesn't have the values it had before.

Answer 169

Short processes get stuck behind long processes in a FIFO style ready queue.

Answer 170

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.

Answer 171

- better for short jobs (they fit in the time slice) | - fair

Answer 172

Long jobs take longer because context-switching time adds up.

Answer 173

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." How does garbage collection work in CPython? "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." What is reference counting? 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. ```

Answer 174

When low-priority jobs never get run because there are always higher priority jobs running.

Answer 175

The scheduler utilizes heuristics on interactivity, locking, burst behavior, etc.

Answer 176

- 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

Answer 177

- 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" How does the banker's algorithm solve the dining lawyers problem? "When you try to grab a chopstick, it's either: - not the last chopstick - is last chopstick but someone else will have two afterwards

Answer 178

The MMU - the memory management unit

Answer 179

- mutual exclusion - hold and wait - no preemption - circular wait

Answer 180

- http - https - ftp - tftp - ntp - irc - telnet - smtp - ssh - dns - snmp - pop3

Answer 181

Network time protocol

Answer 182

- TCP | - UDP

Answer 183

internet control message protocol

Answer 184

- RJ45 - ISDN - Microwave - Ethernet - Wifi - Fiber optics - ATM - RJ48 - Copper cables

Answer 185

Protocol data unit - generic term used to describe the information at a given layer in the TCP/IP stack

Answer 186

data, determined by what information is being exchanged: text, encrypted text, compressed data

Answer 187

for TCP, it's called a segment for UDP, it's called a datagram

Answer 188

data link layer: frames physical layer: bits

Answer 189

8000-65535

Answer 190

48 bits, represented as a hexadecimal number.

Answer 191

medium access control, a sublayer in the data link layer.

Answer 192

PDU: frame Addressing: physical (MAC) address

Answer 193

Bridges, switches (multi-port bridge). They inspect frames and forward or not.

Answer 194

Routers Layer 3 switches: can be a switch or a router

Answer 195

PDU: packet Addressing IP address

Answer 196

PDU: segment addressing: ports

Answer 197

The combination of an IP address and a port.

Answer 198

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!

Answer 199

Symmetric. It tracks all principals and their keys in its KDC table.

Answer 200

- application - presentation - session - transport - network - data link - physical

Answer 201

- application (application, presentation, session in OSI) - transport - internet (network in OSI) - network access (data link & physical in OSI)

Answer 202

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.

Answer 203

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.

Answer 204

The entire Python program exits when no alive non-daemon threads are left.

Answer 205

If the Python program reaches its end, the thread will be killed even if it's sleeping.

Answer 206

The main thread will wait for it.

Answer 207

Web Real-Time Communication

Answer 208

A web server might spawn a thread per connection, then reuse that thread once the connection ends, or terminate the thread.

Answer 209

A pool of threads can be maintained in order to quickly provide one as a resource for a database connection.

Answer 210

def fib(n): a, b = 1, 1 for i in range(1, n): a, b = b, a + b return a

Answer 211

- source IP - destination IP - data - some portion of the final payload

Answer 212

The successor to SSL. All of SSL's versions have been deprecated due to security issues.

Answer 213

To allow multiple applications to use one network connection simultaneously.

Answer 214

A DNS server is compromised and returns incorrect IP addresses for a some domains.

Answer 215

Transmission Control Protocol

Answer 216

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.

Answer 217

The protocol for client-server communication.

Answer 218

User Datagram Protocol.

Answer 219

Allows devices to communicate and send errors. Can echo to see if a device is on the network.

Answer 220

Simple Network Management Protocol.

Answer 221

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.

Answer 222

No, it's connectionless.

Answer 223

It's a 16-bit checksum. It's only mandatory on IPv6

Answer 224

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.

Answer 225

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.

Answer 226

Open Systems Interconnect

Answer 227

To solve the interoperability problem of having multiple heterogeneous networks.

Answer 228

TCP/IP, based on the OSI model.

Answer 229

This is where applications live and they handle data in many forms.

Answer 230

This layer handles configuration of the data: - encryption - compression - translation to and from different character encodings

Answer 231

This layer guarantees end-to-end delivery of data: - packet ordering - error detection - acknowledgements

Answer 232

This layer's function is to find the shortest path through the network to the destination network. Deals with congestion, bandwidth, etc.

Answer 233

It decides whose turn it is to talk on the network using bus arbitration methods. It finds the physical device on the network.

Answer 234

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

Answer 235

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.

Answer 236

A server can send updated assets using server push when it recognizes a file has changed.

Answer 237

It's fully multiplexed, so it can use 100-1000 streams in a connection.

Answer 238

HTTP/2 is a binary protocol.

Answer 239

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.

Answer 240

Different assets can have different priority so that below the fold content can arrive later.

Answer 241

1-126. We don't use 0 or 127.

Answer 242

2^7 = 128 First bit is 0, bits 1-7 are network IDs

Answer 243

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.

Answer 244

2^14 = 16,384 First 2 bits are 10, bits 3-16 are network IDs

Answer 245

2^16 = 65,536 So there are 65,536 per network

Answer 246

2^21 = 2 million First 3 bits are 110, bits 4-24 are network IDs

Answer 247

2^8 = 256 There are 256 hosts per network

Answer 248

Multicasting

Answer 249

Sending a packet from one host to another.

Answer 250

All hosts within the network.

Answer 251

It's a broadcast to all hosts within another network.

Answer 252

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.

Answer 253

For: - security - maintenance - management

Answer 254

By subnetting.

Answer 255

The first 27 bits are masked with 1s. The remaining 5 bits are reachable in the subnet.

Answer 256

The first 24 bits of the IP address are masked. Only hosts with addresses in the unmasked portion are reachable.

Answer 257

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.

Answer 258

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.

Answer 259

A sandboxing framework that adds capability-based security to unix-like kernels and denies access to global namespaces.

Answer 260

aspects of a system that can be accessed from anywhere: - file paths - networks - PIDs

Answer 261

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.

Answer 262

Full-duplex communication between client and server.

Answer 263

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

Answer 264

window.postMessage (HTML5) allows for sending data messages between two windows/frames across domains.

Answer 265

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.

Answer 266

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. How can a server deal with a SYN flood attack? 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.

Answer 267

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.

Answer 268

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.

Answer 269

Scalability is the measure to which a system can adapt to a change in demand for resources, without negatively impacting performance.

Answer 270

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.

Answer 271

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.

Answer 272

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.

Answer 273

An in-memory noSQL database that uses write-ahead logging for crash resistance and persistence.

Answer 274

An object representing activity that eventually completes. Also refers the the function we call that returns a coroutine. In Python, coroutines are generators.

Answer 275

An object representing a result that may not be available yet.

Answer 276

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.

Answer 277

In many cases, you don't need to graph every point, just use visualization-aware sampling. Sometime 1% or less will do. What is F1/Spanner? Fault-Tolerant Distributed RDBMS (Spanner) Supporting Google's Ad Business (F1)

Answer 278

Fault-tolerant and Scalable Joining of Continuous Data Streams

Answer 279

Geo-Replicated, Near Real-Time, Scalable Data Warehousing

Answer 280

Open Source, Distributed, RESTful Search Engine

Answer 281

Start sending 503s if your service is choked to avoid numerous simultaneous retries that just make the system worse.

Answer 282

Hummingbird. PageRank is just one factor used by the algorithm.

Answer 283

Distributed Task Queue

Answer 284

An eviction policy tries to predict which entries are most likely to be used again in the near future, thereby maximizing the hit ratio

Answer 285

Caffeine is a high performance, near optimal caching library based on Java 8.

Answer 286

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. When might you need to use a NoSQL database "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.

Answer 287

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.

Answer 288

atomicity consistency isolation durability

Answer 289

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)

Answer 290

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.

Answer 291

Any callable (function or class) that implements type()'s function signature.

Answer 292

Separating an application into different areas so a vulnerability in one area doesn't affect the entire application.

Answer 293

An entity with privileges or rights.

Answer 294

The user with the user ID that matches the UID of the inode.

Answer 295

The executable permission.

Answer 296

Security is checked when the file descriptor is created. Then it's up to the user to be careful and secure the file descriptor. What is ptrace? 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.

Answer 297

Changes the root directory (/) for a user to be a directory on the filesystem where they can't escape.

Answer 298

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.

Answer 299

A CSRF attack.

Answer 300

The decision about whether a process or agent can perform an action is based on information not explicitly stated, but inherited instead.

Answer 301

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.

Answer 302

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" How is RSA decryption optimized for speed? "- 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

Answer 303

Subtract 1, flip all bits

Answer 304

Flip all bits, then add 1

Answer 305

Little Endian, but only in memory. In registers, all are Big Endian.

Answer 306

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.

Answer 307

The effect of a hashing method where a small change in the input has a large effect on the output.

Answer 308

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.

Answer 309

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.

Answer 310

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.

Answer 311

The memory bandwidth of your RAM. It can become a bottleneck.

Answer 312

The length of time the longest subcomputation takes.

Answer 313

Execution on the current thread will block until it completes, thereby obviating the concurrent call.

Answer 314

- processor speed - number of processors - memory access latency and throughput - cache behavior - runtime behavior (garbage collection, JIT compilation, thread scheduling)

Answer 315

A set in which elements do not have to be unique.

Answer 316

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.

Answer 317

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.

Answer 318

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.

Answer 319

An in-memory distributed hash table. It supports only a few commands but it is extremely efficient. How does/did Facebook use memcache and mySQL in 2009? 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.

Answer 320

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.

Answer 321

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.

Answer 322

A self-hosted mirror of pypi.

Answer 323

A lower bound on the growth of a function. f grows at least as fast as g.

Answer 324

A tight asymptotic bound on a function, in other words if both f and g have approximately the same rate of growth.

Answer 325

linear in the graph size

Answer 326

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

Answer 327

- 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

Answer 328

All attributes (non-key columns) are dependent on the key

Answer 329

All fields can only be determined by the key in the table and no other column.

Answer 330

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.

Answer 331

- reporting on user behavior over many events | - log processing of 100s of billions of rows

Answer 332

- 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

Answer 333

A Python WSGI HTTP Server

Answer 334

- a noSQL key-value store - caches - queues

Answer 335

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.

Answer 336

To support massive concurrent writes.

Answer 337

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.

Answer 338

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)

Answer 339

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.

Answer 340

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.

Answer 341

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.

Answer 342

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.

Answer 343

The overhead of serializing and deserializing. It's all expensive, and for Python, it can be terribly slow.

Answer 344

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.

Answer 345

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." How does PycURL compare to requests? "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

Answer 346

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.

Answer 347

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.

Answer 348

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.

Answer 349

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.

Answer 350

A b-tree where each node manages a subset of the range of the worst to best scores.

Answer 351

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.

Answer 352

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.

Answer 353

Use distinct prime numbers for periodicities.

Answer 354

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

Answer 355

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).

Answer 356

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).

Answer 357

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.

Answer 358

HAProxy Squid Varnish

Answer 359

Since you must both write the data and update the index.

Answer 360

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.

Answer 361

BeanstalkD RabbitMQ ActiveMQ Redis

Answer 362

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.

Answer 363

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.

Answer 364

Linux kernels are often compiled with HZ=100, which entails that processes are given time slices of 10ms. How does Linux handle CPU affinity? 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.

Answer 365

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.

Answer 366

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)

Answer 367

Memcached and Redis are both examples of in-memory caches

Answer 368

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.

Answer 369

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.

Answer 370

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.

Answer 371

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.

Answer 372

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.

Answer 373

Running a service across multiple datacenters.

Answer 374

- caching - VOIP - real-time mutiplayer games

Answer 375

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.

Answer 376

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.

Answer 377

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.

Answer 378

Google BigTable HBase (based on Hadoop) Hypertable Amazon DynamoDB Voldemort Cassandra Riak Redis CouchDB MongoDB

Answer 379

quorum-based 2PC (2 phase commit) protocol

Answer 380

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.

Answer 381

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.

Answer 382

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.

Answer 383

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.

Answer 384

The open/closed principle (OCP)

Answer 385

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.

Answer 386

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.

Answer 387

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.

Answer 388

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.

Answer 389

Hyper-threading enables a single processor core to be used for two or more concurrent executions with just a little extra hardware.

Answer 390

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.

Answer 391

Non-Uniform Memory Architecture

Answer 392

SRAMs are used in Caches because of higher speed and DRAMs are used for main memory in a PC because of higher densities. What is the difference between SRAM and DRAM? 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.

Answer 393

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.

Answer 394

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”.

Answer 395

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.

Answer 396

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.

Answer 397

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.

Answer 398

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.

Answer 399

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.

Answer 400

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.

Answer 401

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?

Answer 402

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]

Answer 403

The first unified container-management system developed at Google. It was built to manage both long-running services and batch jobs.

Answer 404

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

Answer 405

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.

Answer 406

A distributed lock service (master election) built on Borg.

Answer 407

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.

Answer 408

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.

Answer 409

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.

Answer 410

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. Redis is more susceptible to data loss in the event of abrupt termination or power failures.

Answer 411

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.

Answer 412

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." What does amqp stand for? Advanced Message Queuing Protocol