How it works
G
picture loading error handler

Google Interview

1227 thought(s)1.2K
thoughts
111 readers
Star icon blackStar icon greyStar icon greyStar icon greyStar icon grey 3 %
ahmed kamel taha
Get

This flashcard deck made by jwasham contains knowledge about google interview. For more details, please follow https://github.com/jwasham/google-interview-university

This flashcard deck made by jwasham contains knowledge about google interview. For more details, please follow https://github.com/jwasham/google-interview-university
interview
computer science
development

Key thoughts

What is Hamming Code?
9
What is the square root of 256?
8
2^16
6
Using bitwise operations, how would you test that a number is a power of 2?
4
What does ELF stand for?
3
example of a latency device
4
example of a throughput device
3
What is the Hamming Distance?
3
What are the 5 steps of the compiling process?
3
What is parsing?
2
What is lexical analysis?
2
What is code generation?
2
4 * 16
3
2 ^ 4
2
2^3
2
2^5
2
2^6
2
2^7
2
2^8
2
2^9
2
2^10
3
2^11
2
2^12
2
2^13
2
2^14
2
2^15
2
2^32
2
size of char in bits
2
size of char in bytes
2
size of bool in bits
2
size of short in bits
2
size of short in bytes
2
size of int in bits
2
size of int in bytes
2
size of long in bits
2
size of long in bytes
2
size of long long in bits
2
size of long long in bytes
2
size of float in bits
2
size of float in bytes
2
size of double in bits
2
size of double in bytes
1
size of wchar_t in bits
1
size of wchar_t in bytes
1
Write a function that reverses a linked list, with this argument: pointer to pointer to the head node.
1
Delete a given value from a BST rooted at given node. Returns a pointer to node.
1
Get the successor of a value in a BST rooted by given node. Returns int.
Using recursion, insert a value into a tree: root = insert(node*, int)
Using an iterative approach, insert a value into a BST: insert(node*, int)
Write a method is_binary_search_tree that returns true if a given tree is a BST (use helper function).
Using an iterative approach, write a function find_node(bst_node* root, int target) that returns the node with the given target value in a BST.
Using an recursive approach, write a function: find_node(bst_node* node, int value) that returns the node with the given target value in a BST.
Function that returns the height (in nodes) of a BST: int get_height(bst_node* node)
How many levels in a complete binary tree of size n?
How can build heap be done in linear time?
C or Python: Sort an array of numbers using heap sort.
How are queues usually implemented?
How is a deque usually implemented?
How would you swap 2 integers using only bitwise operations?
How would you turn ON the 3rd bit from the end in a bitstring?
How would you turn OFF the 3rd bit from the end in a bitstring?
Write a function that calculates the Hamming distance.
Write a function to calculate the Hamming weight of an integer. (Kernighan method)
Write a function that calculates the Hamming weight in constant time. Divide and Conquer strategy.
Write a function that tells you if a number is even, using bitwise operation.
Write a function to add 2 integers using bitwise operations.
Write a function to get the sign of an integer.
Write a function to calculate the absolute value of a 32-bit integer.
Write a binary search function that works iteratively, taking a target int, array of ints, and size of the array, returning the index of the found item, or -1.
Write a binary search function that works recursively, returning the index of the found item, or -1.
In C or Python, Write a universal hashing function for a string, taking as arguments a string and the capacity of the hashtable.
Describe the universal hashing function for an integer. What arguments would it need? What would it look like?
What is a Binary Search Tree?
What is an AVL tree?
What is a red-black tree?
1
What is a splay tree?
What is a treap?
What is typical cache line size?
What is latency?
1
What is a y-fast trie?
What is an x-fast trie?
What is a van Emde Boas tree?
What is a compressed trie?
What relationship of the keys do you lose with a hash table?
Sed command to take a file separated by spaces, turn spaces into newlines, and then sort it alphabetically.
Print columns 2, 3, and 6 from the date command.
Take a file delimited by : and make it tab-delimited.
Output a file with line numbers.
Is quicksort stable?
Can quicksort be done in-place?
Can merge sort be done in-place?
Is merge sort stable?
Is insertion sort stable?
Can insertion sort be done in-place?
Can selection sort be done in-place?
Is selection sort stable?
Is heap sort stable?
Can heap sort be done in-place?
Write merge sort in C (check answer carefully)
Write a MergeSort class in Python (check answer carefully)
Write quick sort in C with only one method and random pivot (check answer carefully)
Write a QuickSort class in Python (check answer carefully)
In what case would perfect hashing be practical?
How does perfect hashing handle collisions?
What is the optimal load factor for a hash table?
What is the expected load factor for a hash table?
What is the technical running time for operations on a hash table?
What is the worst-case search time of perfect hashing?
What is the worst-case space required for perfect hashing?
What's the best-case running time of binary search?
What's the worst-case running time of binary search?
What are the downsides of using an adjacency matrix to represent a graph?
When is using an adjacency list expensive?
When are adjacency lists most useful?
What is the space required for a graph using an adjacency list?
What's the maximum unsigned number you can represent with 4 bits?
What's the maximum unsigned number you can represent with 8 bits?
What's the maximum unsigned number you can represent with 16 bits?
What's the maximum unsigned number you can represent with 6 bits?
What's the maximum unsigned number you can represent with 15 bits?
What's the maximum signed number you can represent with 4 bits?
What's the maximum signed number you can represent with 16 bits?
What's the maximum signed number you can represent with 8 bits?
What's the maximum signed number you can represent with 9 bits?
1
What's the maximum unsigned number you can represent with 32 bits?
What's the maximum signed number you can represent with 32 bits?
How do you get the logarithm of a number n given a base b?
How can you write log(base b)(ac)?
How can you write log(base b)(a/c)?
How else can you write log(base b)(a^c)?
How you can express log(base b)a as another base?
Why is log(base2)(2^n) == n?
What is the arithmetic series: 1 + 2 + 3 + 4 + ... (n - 1) + n?
1
What is the value of the geometric (exponential) series when x != 1: 1 + x + x^2 + x^3 + ... x^n ?
1
What is the sum of this series when it's infinite and x < 1? 1 + x + x^2 + x^3 + ... x^n ?
What is the sum of the harmonic series for the nth harmonic number: 1 + 1/2 + 1/3 + 1/4 .. + 1/n
What is the maximum unsigned integer you can represent with n bits?
Given a fully balanced binary tree with x nodes, what is the height of the tree in nodes?
Given a fully balanced k-ary tree with x nodes, what is the height of the tree in nodes?
A binary tree with height h can contain at most how many nodes?
For a k-ary tree with height h, the upper bound for the maximum number of leaves is:
What is the complexity of Dijkstra's shortest-path algorithm?
What is a drawback of using an adjacency matrix for an undirected graph?
What is the memory needed to store an adjacency list?
1
What is the memory needed to store an adjacency matrix?
How would you implement a queue with a linked list?
How would you implement a stack with a linked list?
What preference of nodes vs leaves does preorder traversal give on a tree?
What preference of nodes vs leaves does postorder traversal give on a tree?
What could you use in DFS to turn a recursive algorithm into an interative one?
What do you use to keep track of nodes to visit in BFS?
Using a stack to keep track of unvisited nodes gives what kind of traversal?
Using a queue to keep track of unvisited nodes gives what kind of traversal?
In a highly connected graph of n vertices, how many cycles can there be?
What can use to find if a graph is bipartite?
How can you find a cycle in a graph?
1
What is an articulation vertex?
How can you find an articulation vertex?
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?
1
What path does BFS find in a graph?
What's the upper bound on the number of edges in a graph G(V, E)?
In Python, initialize a list of lists called x with 100 elements.
In Python, declare a named tuple called Edge, with attributes vertex and weight.
What is the optimal substructure property tell us about shortest paths?
C++: How would you initialize a vector of 25 integers to all zeroes?
C++: How could you make a string called thing2 have the first 5 characters of thing1?
C++: We want to call parent constructor in our MyClass constructor, with an arg int called foo. What does this look like in .h and .cc? Parent is ParentClass.
What is a Dunder method?
What is the sum of numbers from 1 to 2^n?
How many ways can you rearrange a string of n unique characters?
1
How many ways can you arrange k characters from n unique characters?
How many subsets (ordering doesn't matter) of size k are there in n unique characters?
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]
What should you avoid in your base case in recursion?
What is the bandwidth of a graph?
When talking dynamic programming, what is feasibility?
When talking dynamic programming, what is optimality?
What is dynamic programming?
What is the complexity for a naive recursive Fibonacci function?
Write a dynamic programming version of computing Fibonacci for n.
Write a dynamic programming implementation of longest common subsequence of 2 strings.
Python: Implement the Floyd-Warshall algorithm (all pairs shortest paths).
What is the difference between __str__ and __repr__?
C: Method to find a given item x in a linked list. Head is a List *, x's data type is item_type
C: Method to insert a given item x into a linked list. Head is a List *, x's data type is item_type
C: Method to return the nth item from the end of a linked list.
How many subsets are there in n items?
Python: Given an array of non negative numbers and a total, is there subset of numbers in this array which adds up to given total.
What is a contiguously-allocated structures, and give examples.
What are linked data structures and give examples.
What are some benefits of arrays?
Why is memory locality important?
What are some advantages to linked lists over arrays?
What are some advantages to arrays over linked lists?
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.
Codeless question: Write a function to find the middle node of a singly-linked list.
Codeless question: Write a function to compare whether two binary trees are identical. Identical trees have the same key value at each position and the same structure.
Codeless quesiton: Write a program to convert a binary search tree into a linked list.
Codeless Question: You are given a search string and a magazine. You seek to generate all the characters in search string by cutting them out from the magazine. Give an algorithm to efficiently determine whether the magazine contains all the letters in the search string.
Codeless question: Give an algorithm for finding an ordered word pair (e.g., “New York”) occurring with the greatest frequency in a given webpage. Which data structures would you use?
Codeless question: Given a set of n numbers, how do you find the pair of numbers that have the smallest difference between them?
Codeless question: Are there any duplicates in a given set of n items?
Codeless question: Given a set of n items, which element occurs the largest number of times in the set? Bonus: How do you find out how many times some element k appears?
Codeless question: Give an efficient algorithm to determine whether two sets (of size m and n, respectively) are disjoint.
Python: Function that reads file numbers.txt and outputs numbers-mult.txt where each number in numbers.txt is multiplied by its line number.
What is a uniform distribution?
What is a normal distribution?
What is an n-gram?
What's the maximum unsigned number you can represent with 9 bits?
Whats the average height of a binary search tree after n insertions?
What is the runtime of randomized quicksort?
No answer: Write a function to find the square root of a number within the tolerance of 0.0001
Alter a binary search function to find the start and end indexes of the incidences of a number k in a sorted list.
Codeless question: If you are given a million integers to sort, what algorithm would you use to sort them? How much time and memory would that consume?
Codeless question: Describe advantages and disadvantages of the most popular sorting algorithms.
Codeless: Implement an algorithm that takes an input array and returns only the unique elements in it.
Codeless: You have a computer with only 2Mb of main memory. How do you use it to sort a large file of 500 Mb that is on disk?
Python: Default arguments are okay to use with the following caveat.
Python: Give an example of a conditional expression.
Python: break this string 'a/b/c' into a list of ['a', 'b', c']
Python: split a word or sentences into characters.
What's the difference between foo.sort() and sorted(foo) where foo is a list?
Can you sort a tuple?
Python: How would you remove indices 6 to 11 in a list foo?
Python: How can you tell if an index is in a list?
Python: How to output today's date, like August 10, 2016
Python: How to output today's date, like 8/10/2016 (August, not October)
What's the probability of getting heads twice? P(HH)
What's the probability of getting heads, tails, heads? P(HTH)
What's the probability of getting heads 200 times in a row?
What's the Probability of getting head, tails or tails, heads? P(HT U TH)
What's the probability of getting exactly 3 heads in 8 flips?
You have 26 letters in an alphabet. How many ways you can arrange 3 letters from that alphabet where repeated letters is OK?
You have 26 letters in an alphabet. How many ways you can arrange 3 letters from that alphabet without repeating a letter?
Given an alphabet of 26 letters, how many times you can you choose 3 letters, if ordering of the letters doesn't matter?
What is 0! ?
There are 4 people. How many ways can they shake each other's hands without shaking the same person's hand twice?
Right-propagate the rightmost 1-bit, producing all 1's if x = 0 (e.g., 01011000 01011111):
Isolate the right-most bit in x.
How would you swap 2 integers with no temporary variables and no bitwise operations?
What is P?
What is EXP?
What is R? (not real numbers)
Is the Halting Problem in R?
1
What does NP mean? What is an NP algorithm?
What makes a problem NP-Complete?
What is Fib(0) ?
What is Fib(3) ?
What is Fib(2) ?
What is a PTAS?
What is a pointer?
1
Give 2 examples of common data structures that contain reference cycles.
What is a weak reference in Python?
How does garbage collection work in CPython?
What is reference counting?
What is a finalizer in Python?
What are 2 advantages of reference counting?
What are 2 disadvantages of reference counting?
What is cyclic garbage collection?
How is garbage collection done in PyPy?
What is a pointer?
How does mark and sweep work?
What is copying garbage collection (stop and copy)?
How could you implement an LRU cache?
What is a direct mapped cache?
What is a fully-associative cache?
Disadvantage of a fully-associative cache?
How do some processors handle caching for data and instructions?
What is an N-way set associative cache?
Describe the memory hierarchy of a Core i7 processor.
When is entropy at its maximum?
As predictability increases, what happens to entropy?
As it relates to compression, as entropy increases, does our ability to compress increase?
What does low entropy mean?
What is entropy?
What is a Caesar cipher?
What is a polyalphabetic cipher?
What is the entropy of n equally likely outcomes?
Is GET idempotent?
Is PUT idempotent?
Is POST idempotent?
Is DELETE idempotent?
What is idempotent?
What is HMAC?
What is a MAC?
How does RSA work?
What is the phi function?
What is phi(n) if n is prime?
What is the gcd of a number a and prime p when p is prime?
What does SHA stand for?
What is the largest output size of SHA-3?
What are desirable properties of one-way functions?
If a one-way function is collision-resistant, does that mean it's also target collision-resistant?
If a one-way function is target collision-resistant, does that mean it's also collision-resistant?
What is symmetric key encryption?
How does Diffie-Hellman key exchange work?
Is Diffie-Hellman key exchange perfect?
How is RSA (using product of large primes) better than using NP-Complete algorithms for encryption?
What is Vigenere cipher?
What is a one-time pad encryption?
What is block size in cryptography?
What is the limiting factor of compression?
What is LZ* compression based on?
What is LZMA?
What is DEFLATE?
How does LZ77-based compression work?
What is Huffman encoding?
What is the primary factor of compression?
How can you maximize compression?
What compression scheme uses Burrows-Wheeler transform?
What is the Burrows-Wheeler transform?
For Gzip in web servers, what is the usual setting?
What is the min and max compression settings in command line gzip?
How can you make JSON better compressable with Gzip?
What are Dense Codes?
What is the LZ in LZ compression?
What is OS hardware virtualization?
What is a process?
What is a context switch?
What is the scheduler?
What causes operating systems to crash most of the time?
What is a process VM?
What is a system VM?
How does the OS abstract the environment for a process?
What is fault isolation?
What is a thread?
What's the maximum address in memory for a 32 bit processor?
What is the execution sequence for a program?
What does the program counter point to?
What is the stack pointer?
What is the heap pointer?
What is multiprogramming?
What triggers a context switch?
What is dual-mode operation?
How does the OS run a program?
How does a user program interact with the kernel?
What happens when the hardware needs something to happen?
What happens when a program makes an exception?
What is base and bound?
How does the OS know how to handle an interrupt?
What is the difference between PC and uPC?
How are base and bound enforced?
How does x86 do segments and stacks?
When a process forks, what happens?
What does fork() return?
What does wait() do?
What does exec() do?
What comes back from wait()?
What is a signal?
In a child process, what can you do with fork and then exec?
What is a shell?
What is a microsecond? Also known as μs
What is a nanosecond?
What is a picosecond?
How does the kernel handle reads and writes?
What's the difference between the fread, read, fwrite, write I/O calls?
When a system call is made, where are parameters stored?
What is a socket?
What sockets are in modern use?
What is the GIL?
When is the GIL released?
What is a "tick" in CPython?
What happens every 100 "ticks" in the CPython interpreter?
What is a lock in CPython?
What happens when the heap gets too large?
What happens when the heap and stack meet in memory?
Where is information about a process stored?
Where is information about a thread stored?
What do multiple threads in the same process share?
What do threads in a process NOT share?
What can happen with thread stacks if one goes into a deep recursion?
What can cause a thread to give control back to the dispatcher?
How long does it take to do a process context switch?
How long does it take to perform a thread context switch?
How often do context switches happen?
Context switch time increases sharply with the size of what? (by 100x or more.)
What happens in a system call to get the OS to switch to kernel mode?
How many threads should you run per process?
How is concurrency accomplished?
What's the difference between parallelism and concurrency?
What is oversubscription?
What is a race condition?
What can you put in place to exclusively use a resource without another process interfering?
How do you use a mutex in Python?
What does a future do?
What is a promise?
What is livelock?
How long does a terminated process stay in the terminated state?
In Python, what can you use to fork a process?
What does the concurrent.futures module offer?
What is an interrupt?
What happens during an interrupt?
What really happens when you fork a process?
What is multiprocessing?
What does a PCB contain?
What is special about an interrupt handler?
What are the five states a process can be in?
What is the difference between filter() and map()?
What is synchronization?
What is a critical section?
What is the priority inversion problem?
What is busy-waiting?
What is a semaphore?
What's another name for a mutual exclusion?
What is a monitor?
What should locks and condition variables each be used for?
What is a condition variable?
What is a special feature of condition variables?
What are the 3 methods on a condition variable?
What type of scheduling do most modern processors use?
What are some things the scheduler tries to accomplish?
What is a drawback of context switching?
What's the convoy effect?
What is the round robin scheduling scheme?
What are pros of the round-robin scheduling scheme?
What is a con of the round-robin scheduling scheme?
How long does context switching take?
What is starvation?
How does a process' priority get changed?
What are some methods of avoiding deadlock?
What is the banker's algorithm for preventing deadlock?
How does the banker's algorithm solve the dining lawyers problem?
Does the CPU use virtual addresses or physical addresses?
What translates virtual to physical addresses?
What are the four conditions needed for a deadlock?
How many bits represent an IPv4 address?
How many bits represent an IPv6 address?
Name some of the protocols used within the TCP/IP application layer.
What is NTP?
What are some protocols in the TCP/IP transport layer?
What are some TCP/IP network layer protocols?
What are some TCP/IP network access layer protocols?
What is a PDU?
What is the PDU for OSI layer 7?
What are the PDUs for the the OSI transport layer?
What is the PDU for the TCP/IP internet layer?
What are the 2 PDUs of the OSI Network Access layer?
What is the port for DNS?
What is the port for telnet?
What is the port for ssh?
What is the port range for clients?
How many bits are in an ethernet frame?
What does MAC stand for?
What is the PDU and the addressing at the data link layer?
What devices are at the data link layer?
What devices are at the Internet/Network layer?
What is the PDU and the addressing at the Internet/Network layer?
What is the PDU and the addressing at the Transport layer?
What devices are at the Transport layer?
What is a socket in HTTP?
What is involved in the 3 way handshake (TCP)?
Does Kerberos use symmetric or asymmetric encryption?
What are the 7 layers of the OSI model?
What are the 4 layers of TCP/IP?
How is an SSL certificate generated by the certificate authority (CA)?
What is the secure flag on a cookie?
When does a Python multi-threaded program terminate?
In Python, if a thread is set to daemon, what happens when the thread sleeps?
If a thread is a daemon, what happens when you do a join()?
What does WebRTC stand for?
Give an example of the thread-per-connection pattern.
Give an example of the thread pool model.
Fibonacci in Python
What is contained in a packet?
What is TLS?
What is the purpose of the transport layer?
What is DNS spoofing?
What does TCP stand for?
What is special about TCP?
What is HTTP?
What does UDP stand for?
What is the size of a UDP header?
What is the size of a TCP header?
What does ICMP stand for?
What does ICMP allow you to do?
What does SNMP stand for?
What does SNMP do?
Do you need to establish a connection before sending data via UDP?
Tell me about the checksum in a UDP packet.
How many times are packets sent in UDP?
What is special about UDP?
What's special about TCP?
What does OSI stand for?
Why was OSI created?
Is OSI just a model?
What network protocol won the networking wars?
What happens at the Application level of the OSI model?
What happens in the Session layer of the OSI model?
What happens at the Session layer of the OSI model?
What happens at the Transport layer of the OSI model?
What happens at the Network layer of the OSI model?
What happens at the Data Link layer of the OSI model?
What happens at the Physical layer of the OSI model?
How does HTTP/2 save bandwidth?
How does HTTP/2 improve cache breaking?
What is the stream parallelism in HTTP/2?
Is HTTP/2 binary or textual?
How are headers and body treated differently in HTTP/2?
What is priority in HTTP/2?
What is the range of the first octet on a Class A network?
How many network IDs are there on a Class A network?
How many host IDs are supported on a Class A network?
What is the range of the first octet on a Class B network?
How many network IDs are supported on a Class B network?
How many host IDs are supported on a Class B network?
What is the range of the first octet on a Class C network?
How many network IDs are supported on a Class C network?
How many host IDs are supported on a Class C network?
What is a class D network reserved for?
What is unicasting?
What does a network ID end in?
What does a broadcast ID end in?
Who does a broadcast address of 255.255.255.255 send to?
What is a directed broadcast?
What is a limited broadcast address?
What should you make networks as small as possible?
How you divide a network?
What does a /27 CIDR mean?
What does a /24 CIDR mean?
What is a block cipher?
What is QUIC?
What is Capsicum?
What is a global namespace in unixy terms?
What is Google Native Client?
What are web sockets?
What is the same-origin policy?
How can 2 origins (let's say 2 frames) communicate?
What is JIT compilation?
What is PyPy?
What does SMT stand for?
What is an SMT solver?
How do we find that a condition exists that will cause a program to have a predicted outcome?
What is transactional memory?
What is software transactional memory?
Does PyPY have a GIL?
How can a server deal with a SYN flood attack?
What is a stack canary?
What type of buffer overflow protection does gcc and Visual Studio employ?
What is scalability?
What is Akka?
What is an actor?
What is an IDL-based encoding?
What is Tarantool?
What is a coroutine?
What is a future?
What is AQP?
How would you visualize billions of items in a graph?
What is F1/Spanner?
What is Photon?
What is Mesa?
How does Google use multi-homed datacenters?
What is ElasticSearch?
What is an example of a circuit breaker?
What is the name of Google's search ranking algorithm?
What is celery?
LRU is the most popular type of what kind of policy?
What does an eviction policy try to predict?
What is Caffiene?
What is request coalescing?
When might you need to use a NoSQL database
What is AMP?
What is a benefit of making processes asynchronous?
What is BASE?
What is ACID?
What is the CAP theorem?
What is zero copy?
What is a metaclass?
What is privilege separation?
In security, what is a principal?
In Unix, who is the owner of a file?
What privilege do you need to lookup files or directories in a path?
When is security enforced on a file?
What is ptrace?
What can you use to debug a process?
What user privilege is required to bind to ports < 1024?
During system bootstrapping, what call is performed by the system to give a non-root user the ownership of a process?
What are the setuid binaries?
What does chroot do?
What is a confused deputy?
What is an example of a confused deputy in the web frontend world?
What is ambient authority, or ambient privilege?
What is a capability?
What is a requirement of enabling sandboxing?
How is RSA decryption optimized for speed?
How do you change a positive integer to negative?
How do you change a negative integer to positive?
What is Intel architecture?
What size are Intel instructions?
What is RISC?
What Endianness is Intel?
What is Little Endianness?
How many registers are on CISC?
What is the word size on Intel?
What is the double-word size on Intel?
What is Big Endianness?
What is the EAX register used for?
What is the EBX register used for?
What is the ECX register used for?
What is the EDX register used for?
What is the ESI register used for?
What is the EDI register used for?
What is the ESP register used for?
What is the EBP register used for?
What is the EIP register used for?
What are the caller-save registers?
What are the callee-save registers?
Other than the main registers, what other registers can be used?
What is the caller register-saving convention on Linux systems?
What is avalancing?
What is Chef?
What is an example of a non-cryptographic hash function?
How could you process calculations on elements of an array in parallel?
What factor should you keep in mind when doing parallel computation on different parts of a large data structure?
What will be the computation time when processing multiple tasks?
Why should you avoid starting and joining a task or thread on the same line or proximity?
What factors affect performance?
What is Amdahl's Law?
What aspects are important in measuring and benchmarking performance, parallel or otherwise?
When associative operations are used, what does it mean?
What is a synonym of reduce()?
What is the commutative property?
What is a bag?
What is a multiset?
What are some examples of operations that are both associative and commutative?
What are some examples of operations that are associative but not commutative?
What should we worry about floating point addition and multiplication?
What is the rule of thumb before optimizing or parallelizing?
Does Python have an opcode cache?
Design a URL shortening service.
How would you design the feature in LinkedIn where it computes how many hops there are between you and another person?
If you were to design a web platform for online chess games, how would you do that?
What are some key things to remember when scaling a large system?
What is Thrift?
What is Memcache?
How does/did Facebook use memcache and mySQL in 2009?
What is an out-of-band cache?
What is a monad?
What is pyramidpypi?
Big Omega represents what?
Theta represents what?
For graph problems, the complexity Theta(N + M) is known as what?
What is a better way of saying "at least O(n^2)"?
What is data normalization?
What are the requirements for first normal form?
What are the requirements for second normal form?
What are the requirements for third normal form?
What are the requirements for fourth normal form?
What are some use cases of Hadoop?
What are some solid principles to keep in mind for scaling?
What is gunicorn?
What is WSGI?
What is Fabric?
What is Apache Solr?
What is munin?
What tends to become an issue as you add services in a datacenter and have to ping more caches and services to fulfill a request?
What can Redis be used for?
What is a benefit of sharding a database as it grows, and what determines the size?
Why do most businesses end up sharding as they scale?
What is a message broker?
What are some examples of message brokers?
What is Ehcache?
Timing of a L1 cache reference?
Timing of a branch misprediction?
Timing of a L2 cache reference?
Timing of a mutex lock/unlock?
Timing of a main memory reference?
Timing to compress 1KB?
Time to send 2K bytes over 1 Gbps network?
Time to read 4KB randomly from an SSD?
Timing to read 1MB sequentially from memory?
Timing of a disk seek?
Time to read 1MB sequentially from an SSD?
Timing to read 1MB sequentially from disk?
Timing to send a packet CA -> Netherlands -> CA?
Timing of a context switch between processes?
Timing of fork()?
What is the timing overhead for a system call?
What is Kafka?
What is GAE?
What is GDS?
What is the problem that serialization introduces?
What does the Python bisect module do?
What is PycURL?
How does PycURL compare to requests?
What is ZooKeeper?
What is orthogonality?
When dealing with scaling, how can you deal with rapidly increasing counters, like YouTube video views?
What is exponential backoff and when is it used?
What data structure could be used to efficiently manage a leaderboard?
What does adding jitter in system design help you avoid?
What is an example of adding jitter to a caching system?
What value can you make cron or other system intervals so they don't coincide?
What Python package provides tools for adapting or extending functions and other callable objects, without completely rewriting them?
What is a proxy server?
What is collapsed forwarding?
What should be handling requests first, a proxy server or a cache?
What are some popular proxies?
Why do indexes tend to slow down writes?
What is the role of a load balancer?
What is a drawback of advanced features in a load balancer?
What is a benefit of adding asynchrony to a system?
What is the difference between a synchronous system and an asynchronous system?
What are some examples of well-known queue (or can act as a queue) software?
Does asynchronous code tend to be CPU-bound or I/O bound?
What is the optimal number of threads?
What is the typical time slice for a process on a Linux box?
How does Linux handle CPU affinity?
What is futex?
How do context switches perform under virtualization?
What is a Frame Check Sequence?
How does Google handle a search request?
What is an example of bulk synchronous processing?
Execution Orchestrator
What are 2 reasons for using a load balancer?
What are balancing methods used by load balancers?
What are the 3 choices in load balancers? The 3 kinds, not balancing mechanisms.
What are 2 examples of in-memory caches?
What is write-through cache?
What is write-back cache?
What is read-through cache?
What is HDFS?
What is Hortonworks?
What is a platform layer?
What is multi-homing?
Where is weak consistency OK?
What is the Paxos algorithm?
What problem does consistent hashing help solve?
What is the relationship between consistent hashing and memcache?
What are some examples of NoSQL solutions?
What is Paxos an example of?
What is MVCC?
What is the S in SOLID?
What does concurrent.futures do?
What is the O in SOLID?
What is RTTI?
Which SOLID principle is "Make all Member Variables Private." helping to enforce?
What is the L in SOLID?
What is the I in SOLID?
What is the D in SOLID?
What are 3 things CDNs use to ensure availability?
What is hyper-threading?
What is DMA?
What does NUMA stand for?
Where are SRAM and DRAM used?
What is the difference between SRAM and DRAM?
What is the difference between a CPU core and a CPU thread?
What is SMP?
How does a multi-processor CPU maintain cache coherency?
What is Colossus?
What is Spanner?
What is Marzullo's algorithm?
What is Google File System?
What is BNF?
What is MapReduce?
What is a Zipf distribution?
The memory addresses returned by the malloc function are typically aligned to at least ___ bytes.
What is AddressSanitizer?
What is transitive closure?
What is CUDA?
What is Borg?
What is MPM?
What are 3 benefits of containers?
What is Chubby?
What does CSP stand for?
What is Protocol buffers?
Why is using Protocol buffers better than pickling?
What is gRPC?
What is Redis?
What commands can be used to make a Redis queue somewhat reliable?
What is RabbitMQ?
What is pika?
What is Celery?
What does amqp stand for?
What is ZeroMQ?
What is ActiveMQ?
What is IPC?
What is Kafka?
What is MessagePack?
What is Avro?
What is a Bloom filter?
How can you easily generate multiple hashes for the same element?
What is DFT?
What is FFTW?
What data structure allows for insert and delete in constant time?
What is a cache-oblivious algorithm?
How can you augment a splay tree so you can find how many items are between x and y?
In a maximum flow problem, what is the minimum cut?
What is the Ford-Fulkerson algorithm?
What is the running time for the disjoint set data structure?
In testing, what is an oracle?
What do you test interfaces with a trust boundary?
What Python flag turns on optimizations and removes assertions from code?
Why is doing work in a constructor a bad thing?
What should be avoided to ensure testing is easier/possible?
What is another name for a setter?
What is another name for a getter?
What are some guidelines to keep in mind to not violate the dependency inversion principle?
What is another name for O(2^n)?
What is another name for O(n^4)?
What does big-O mean? (briefly)
What does big-Omega mean? (briefly)
What is a trap/exception?
What does the scheduler do?
What are the 2 hardware modes?
What is a PCB and what does it have?
What is stored in a TCB?
What is separate chaining?
What is open addressing?
What is the length of the longest chain in a hash table using separate chaining?
Since uniform hashing is difficult to achieve in practice, what is a great alternative?
How can you test if a number is odd in bitwise operations?
How can you test if a number is even in bitwise operations?
What order of node and its children are involved in a preorder traversal?
What order of node and its children are involved in a postorder traversal?
What order of node and its children are involved in an inorder traversal?
What is another name for a breadth-first search traversal?
Code: Compute the power set of a set of integers S.
What is the proper name for Endianness?
Where can octet order (Endianness) problems crop up in files?
What defines a complete binary tree, and give an example?
In a heap, with a 0-based array, what is parent of i?
In a heap, with a 0-based array, what is left child of i?
In a heap, with a 0-based array, what is right child of i?
In a heap, with a 1-based array, what is right child of i?
In a heap, with a 1-based array, what is left child of i?
In a heap, with a 0-based array, what is parent of i?
What is the height of a m-ary heap?
What is a 2-3-4 tree?
What is the complexity of all operations on a splay tree?
What is the maximum height of a red-black tree?
In a b-tree, how many children are there per node?
What does the max degree of a b-tree depend on?
A b-tree's data is organized to correspond with what?
Give an example of how a b-tree might be organized.
On descending a b-tree, what's the rule?
On insertion in a b-tree, what's the rule?
How many nodes of k leaves are in a compressed trie (big-O)?
What is a suffix tree?
In brief, how does selection sort work?
When can insertion sort run in n log n time?
How can you speed up selection sort with a heap?
What data structure is well suited for a heap sort and which is bad?
What data structure is well suited for a merge sort and which is just okay?
How can you optimize finding a pivot when the segment to pivot is large (not random choice)?
What is counting sort?
What is radix sort?
What is the counting sort running time?
What radix is most natural to use?
How would radix sort work for IEEE floating point numbers?
How to choose q for radix sort?
What operations are a treap optimized for?
What is the Day–Stout–Warren (DSW) algorithm?
What is the insertion sort algorithm?
Is radix sort stable?
What is the algorithmic time complexity of radix sort?
Give the code for selection sort.
All comparison-based sorting is bounded by what complexity?
What do you call a linear ordering of a directed graph of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering?
What is a good method for performing a topological sort?
How many possible trees are there that span all nodes in a graph?
What is Prim's algorithm?
What is the time complexity of Prim's algorithm on an adjacency matrix?
What is the time complexity of Prim's algorithm on an adjacency list and a binary heap?
What is the time complexity of Prim's algorithm on an adjacency list and a Fibonacci heap?
What is the pseudocode Kruskal's algorithm?
What is the time complexity of Kruskal's algorithm?
What is Kruskal's algorithm?
How can you find the number of connected components?
How can you get a topological sort with DFS?
How can you check for a cycle with DFS?
How can you get the strongly connected components of a graph?
How do you reverse the edges in a directed graph represented as an adjacency matrix?
How can you find the shortest path on a DAG?
How to find the longest path on a weighted DAG?
What is the diameter of a graph?
Under what condition can you not use Djikstra's algorithm?
In plain words, how does Kruskal's algorithm work?
What can most dynamic programming problems be expressed as?
What metric can you use to measure the badness of a line in a text justification problem?
How can you tell if a graph is 2-colorable?
What is it called when you have too many base cases in your recursion?
What is the base case of a recursion?
What is the formula for n choose k?
What is the general outline of a backtracking algorithm?
What kinds of problems is dynamic programming best suited for?
What is n choose n?
What is n choose 1?
What is n choose 0?
What is the Floyd-Warshall algorithm?
What is the Bayes' rule (formula)?
How would you calculate P(A|B)?
How would you calculate P(A and B)?
How would you calculate P(A or B)?
What's another way to write P(A and B)?
What is a Markov chain?
Write a function that computes the sqrt(n) using binary search.
What is P(A|A)?
At how many items should you expect a collision when hashing among n buckets?
What is n/n^2?
What is the P( ! B ) ?
What is the probability of at least 1 H in 3 flips?
With a fair coin, what is the probability of getting exactly 1 H in 4 flips?
With a fair coin, what is the probability of getting exactly k H in n flips?
In what domain are most decision problems (P, Exp, R, outside R)?
What does it mean when a problem is NP-Hard?
What does it mean to reduce a problem A to a problem B?
Is "3-D matching" NP-Complete?
Is "triple coloring a graph" NP-Complete?
Is "two coloring a graph" NP-Complete?
Is "subset sum" NP-Complete?
Is "bin packing" NP-Complete?
Is "vertex cover" NP-Complete?
Is "set cover" NP-Complete?
Name some NP-Complete problems.
What is one way of doing approximate traveling salesman?
What suffers from GC pauses?
How can an LRU cache be implemented with a linked list?
How often are DRAM cells data rewritten?
What does Skylake architecture look like?
What is a TLB?
In a direct mapped or set associative cache, what is special about the cache size?
How many bits does a SHA1 produce?
How many bits does a SHA2 and SHA3 produce?
Is it always letters we are looking for in compression?
What is Zopfli?
What is the Chinese remainder theorem?
How do you change a 2s complement positive integer into a negative one?
How do you change a 2s complement negative integer into a positive one?
Which way does the stack grow?
What is polymorphism in OO?
What are the 4 main tenets of OO?
What is dynamic binding?
What is a package?
What is an interface in OO?
What is a framework?
What are hooks?
What is a server?
What is an OCL?
What is the Chain of Responsibility pattern?
What is the Command pattern?
What design pattern avoids coupling the sender of a request to its receiver by giving more than one object a chance to handle the request?
What design pattern encapsulates a request as an object, thereby letting you parameterize clients with different requests?
What is the Interpreter pattern?
What design pattern, given a language, defines a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language?
What is the Iterator pattern?
What design pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation?
What is the Mediator pattern?
What design pattern defines an object that encapsulates how a set of objects interact?
What is the Memento pattern?
What design pattern captures and externalize an object's internal state so that the object can be restore to this state later?
What is the Observer pattern?
What design pattern defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically?
What is the State pattern?
What design pattern allows an object to alter its behavior when its internal state changes?
What is the Strategy pattern?
What design pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable, and lets the algorithm vary independently from clients that use it?
What is the Template Method pattern?
What design pattern defines the skeleton of an algorithm in an operation, deferring some steps to subclasses?
What is the Visitor pattern?
What design pattern represents an operation to be performed on the elements of an object structure and lets you define a new operation without changing the classes of the elements on which it operates?
What is the Adapter pattern?
What design pattern converts the interface of a class into another interface clients expect?
What is the Bridge pattern?
What design pattern decouples an abstraction from its implementation so that the two can vary independently?
What is the Composite pattern?
What design pattern composes objects into tree structures to represent part-whole hierarchies?
What is the Decorator pattern?
What design pattern attaches additional responsibilities to an object dynamically and provides a flexible alternative to sub-classing for extending functionality?
What is the Facade pattern?
What design pattern provides a unified interface to a set of interfaces in a subsystem and defines a high-level interface that makes the subsystem easier to use.
What is the Flyweight pattern?
What design pattern uses sharing to support large numbers of fine-grained objects efficiently?
What is the Proxy pattern?
What design pattern provides a surrogate or placeholder for another object to control access to it?
What is the Abstract Factory pattern?
What design pattern provides an interface for creating families of related or dependent objects without specifying their concrete class?
What is the Builder pattern?
What design pattern separates the construction of a complex object from its representation, so the same construction process can create different representations?
What is the Factory Method pattern?
What design pattern defines an interface for creating an object, but lets subclasses decide which class to instantiate?
What is the Prototype pattern?
What design pattern specifies the kinds of objects to create using a prototypical instance, and creates new objects by copying this prototype?
What is the Singleton pattern?
What design pattern ensures a class only has one instance and provides a global point of access to it?
What are design patterns?
What is the Law of Demeter?
If a cache line size is 64B, and the memory bus is 64 bits wide, how many transfers per cache line?
What does an exclusive cache style?
What manufacturer uses an exclusive cache style?
How does an inclusive cache style work?
What manufacturer uses an inclusive cache style?
What is the Fast Fourier Transform?
What is a skip list?
What operations does a skip list support and what is their avg and worst case times?
What operations does a van Emde Boas tree support and what are the time complexities?
What are the complexities for treap operations?
What are Catalan numbers?
What is Karatsuba multiplication?
What is the time complexity of Ford-Fulkerson?
16^0 ?
16^1 ?
16^2 ?
16^3 ?
16^4 ?
16^5 ?
16^6 ?
16^7
16^8 ?
What is 0xB in decimal?
What is 0xC in decimal?
What is 0xD in decimal?
What is 0xE in decimal?
What is 0xF in decimal?
What is 0xA in decimal?
What is 0xA in binary?
1
What is 0xB in binary?
What is 0xC in binary?
What is 0xD in binary?
What is 0xE in binary?
What is 0xF in binary?
How are the priorities of a treap assigned?
Give an example of a proposition in conjunctive normal form.
How does a half-adder handle an addition?
Is a geometric Steiner tree NP-Complete?
What are the 2 algorithms for convex hull?
1
How does a Graham scan work in finding convex hull?
How does the Jarvis march work in finding convex hull?
What is the worst case time complexity of a Jarvis march?
What is the average complexity of a Jarvis march?
What is white-box testing?
What is black-box testing?
What is unit testing?
What can affect testing, apart from API inputs?
What are 3 situations where timing of inputs important in testing?
What is a mock object?
What is integration testing?
What is system testing?
1
What is differential testing?
What is stress testing?
How can you tell you're testing enough?
What does code coverage not tell you?
What should you do when you discover that not all code is covered?
What are some coverage metrics?
What is mc/dc coverage?
What is path coverage?
What is infeasible code?
Should you include integration tests in code coverage metrics?
What should you do before fixing a reported bug?
Why should tests be idempotent and isolated?
delete (unordered singly linked list)
find (unordered singly linked list)
delete (ordered singly linked list)
find (Binary Search Tree)
add (Binary Search Tree)
Add element to the top of the stack - push
Remove the top element of the stack - pop
Return the value of the top element of the stack without removing it.
1
Add an element to a queue.
Remove an element from the front of the queue. dequeue
Return the element from the front of the queue without removing it. - front
find (unordered array)
add (unordered array)
delete (unordered array)
find (sorted array)
add (sorted array)
delete an element from a sorted array
find (unordered singly linked list)
add (unordered singly linked list)
1
delete (unordered singly linked list)
find (ordered singly linked list)
add (ordered singly linked list)
delete (ordered singly linked list)
find (Binary Search Tree)
add (Binary Search Tree)
delete (Binary Search Tree)
find (Balanced Binary Search Tree)
add (Balanced Binary Search Tree)
delete (Balanced Binary Search Tree)
find (Balanced Binary Search Tree)
add (Balanced Binary Search Tree)
delete (Balanced Binary Search Tree)
What is a skip list?
What is a treap?
1
What is a max-heap?
min (unordered sequence)
insert (unordered sequence)
removeMin (unordered sequence)
min (ordered sequence)
insert (ordered sequence)
removeMin (ordered sequence)
build (ordered sequence)
min (binary heap)
insert (binary heap)
removeMin (binary heap)
build (binary heap)
What is a binary heap?
What is a Adaptable Priority Queue?
What is the time complexity of quicksort?
Lower Bound for Comparison Based Sorting
k-th smallest (full heap)
What is a connected graph?
What is a tree?
What is a cycle?
What is a spanning tree?
Space required for an adjacency list
is_adjacent (u,v) (adjacency matrix)
What is the complexity of an adjacency list DFS?
What is another name for a Min-Cost Spanning Tree?
Bitwise: Isolate the lowest bit that is 1 in x
1
Bitwise: Replace the lowest bit that is 1 with 0
Bitwise: Right propagate the rightmost set bit in x
What are heuristics?
What is stable sorting?
What is another name for a trie?
What is internal sorting?
What is external sorting?
What are 2 advantages of merge sort?
What is disadvantages of merge sort?
What are 3 advantages of heap sort?
What is a disadvantage of heap sort?
What is a articulation vertex?
What is the chromatic number?
What are long-term issues involved in machine learning?
How many rows are in a 12 x 16 matrix?
How many columns are in a 12 x 16 matrix?
In linear algebra a vector of 12 elements has how many rows?
In linear algebra a vector of 12 elements has how many columns?
In linear algebra a 12-dimensional vector has how many rows?
In linear algebra a vector of 12-dimensional vector has how many columns?
When multiplying a 4x3 matrix and a 3x6 matrix, what are the dimensions of the final matrix?
Can you multiply a 3x2 and a 2x3 matrix?
Can you multiply a 3x2 and a 3x2 matrix?
Can you multiply a 3x2 and a 2x6 matrix?
When multiplying a 5x2 matrix and a 2x5 matrix, what are the dimensions of the final matrix?
Is matrix multiplication commutative? Does AxB = BxA?
Is matrix multiplication associative? Does (AxB)xC = Ax(BxC)?
What would the identity matrix look like to multiply with an MxN matrix to get itself?
What must at least be true about a matrix for it to have an inverse?
What does it mean to invert a matrix?
What Python library computes the inverse of a matrix?
What are 2 words for matrices that are invertible?
If A is a matrix and Aij is the ith row, jth column, what is the traspose B?
What is another name for quadratic?
What is supervised learning?
What is a regression problem?
What is a classification problem?
What is unsupervised learning?
What are the 2 types of problems that utilize supervised learning?
In machine learning, what is the symbol m used for?
What is another term for linear regression with one variable?
What is gradient descent?
What is it called when all training examples are used to calculate gradient descent?
What is another term for linear regression with multiple variables?
Why is feature scaling important?
What is is good range to scale features down to?
What is mean normalization?
What is a good range for mean normalization?
How can you calculate mean normalization over a set of features?
Given a sufficiently small alpha, what can you expect from gradient descent?
What does Andrew Ng use to find an appropriate alpha for gradient descent?
How can you get your data to fit better using higher order terms in linear regression?
What can affect invertibility in a matrix?
When can we use the normal equation instead of gradient descent to minimize J(theta)?
What does numpy.allclose() do?
Is feature scaling needed when using the normal equation?
What is the normal equation?
What Python determines the pseudo-inverse of a matrix?
What is treated as false in Python?
What is a dot product?
What is the quantile?
What is the mode?
What is dispersion?
What is covariance?
What is a random variable?
What is PCA and what is it used for?
What is a model?
What is machine learning?
What is the degree of a vertex?
What is quick select?
What is preemption?
What is an inverted index?
What is set partition?
What is a maximum spanning tree?
What is a minimum product spanning tree and when would you use it?
What is a rolling hash?
What is the Euclidean GCD algorithm in Python?
What is the Rabin-Karp algorithm?
What is sharding?
What is von Neumann Architecture?
What is the fetch-execute cycle?
What does a Control Unit (CU) do?
What is the time complexity of breadth-first search?
What is the time complexity of breadth-first search?
What is the time and space complexity of minimum edit distance using dynamic programming?
What is the time complexity of Floyd-Warshall?
What is the log of n! ?
What is the time and space complexity of Bellman-Ford?
What is the Bellman–Ford algorithm?
What is a Hamiltonian cycle?
What is the set cover problem?
What is the time and space complexity of heapsort?
What is the time and space complexity of merge sort?
1
How would you divide up a data set for training and testing?
How would you split up a data set in order to choose from multiple models?
What is a Type 1 error?
What is a Type 2 error?
In statistics, how would you calculate precision?
In statistics, how would you calculate recall?
1
In statistics, what does precision measure?
In statistics, what does recall measure?
How would you calculate the F1 score?
What is another name for the F1 score?
What is the trade-off between precision and recall?
High bias and low variance typically correspond to _______.
Low bias but very high variance typically correspond to _______.
What can you do when your model has high bias (which means it performs poorly even on your training data)?
What can you do if your model suffers from overfitting due to high variance?
What does BFGS stand for?
What is L-BFGS?
What are some alternative algorithms that can optimize for a logistic regression problem?
1
What makes neural networks superior over regression or classification?
How should you initialize Theta for a neural network?
What are the number of neurons (units) at the input layer of a neural network?
What are the number of neurons (units) at the output layer of a neural network performing classification?
How many hidden layers should there be in a neural network?
Machine learning: What tends to happen with the training error in a linear model as the degree of polynomial increases?
Machine learning: What tends to happen with the cross-validation error in a linear model as the degree of polynomial increases?