Computer Fundamentals
Heap and Stack
When do you use the heap? When do you use the stack? What is the stack for? Are Go variables on the stack or the heap? Do the heap and stack have limits? If so, what are they related to?
Data Structures
How is space allocated for a slice? Double the capacity and copy the old data over.
What structure is a Go map? What structure is a Go map, is iteration ordered? What is a hash table? What is the lookup efficiency of a hash table? What methods are there for resolving collisions?
Threads
Is more threads always better? Is thread switching expensive?
Is more goroutines always better? You need to distinguish thread scheduling (kernel context switching) from goroutine scheduling (in-process context switching).
Network
TCP Protocol
What is the TCP connection establishment process, and what is its most important work? Negotiating sequence numbers.
The TCP teardown process β why four waves? Because TCP is full-duplex.
Client -> Server: the client actively closes the connection; on which end does TIME_WAIT occur? When does a server typically have many TimeWaits? The end that actively closes. Many TimeWaits prove the service actively closes connections, which means there are many short-lived connections.
Client and Server have already established a TCP connection, and the Client is blocked in a Read call. After the Server process crashes, what happens to the Client? When a process crashes, the operating system closes the file descriptors, and the Server enters the active-close flow.
When transferring a file over TCP, why is it still necessary to verify the correctness of the received file?
HTTP Protocol
Briefly describe the HTTP protocol format: can a text protocol carry binary? How HTTP can transfer images (content-length).
What is the relationship between HTTP and HTTPS? Briefly describe what the HTTPS protocol does; describing the HTTPS handshake process earns bonus points.
What is keepalive in HTTP, and how is keepalive achieved? Only HTTP/1.1 supports keepalive, sending requests sequentially over one TCP connection (following a request-response order); HTTP/2.0 adds multiplexing.
Database
Index Knowledge
What data structure do database indexes use? Why use this data structure?
A table’s string field A already has an index. Can the query condition A == ‘abc’ use the index? Can the query condition A != ‘abc’ use the index? Why? Because A != ‘abc’ cannot be compared in size during the B+ tree lookup, so it cannot further locate the child trees.
A table a has a primary key id. Explain the efficiency difference between select * from a order by id desc limit 10, 1 and select*from a order by id desc limit 100000, 1. Whatever the offset is, that is how many rows must be traversed.
A table has a composite index (A, B). If a query uses A=1, can it use the index? What about B=2? Why?
Limitations of limit
What approach would you use to traverse a table with 300 million rows that has a primary key id?
Algorithms
Assessing Algorithmic Ability
Given 1 million distinct integers in random order, what is the fastest way to split them into two equal parts such that every number in the first part is smaller than every number in the second part? Use the idea of quicksort.
There are 100 sorted arrays in memory, each with 100,000 elements. What is the fastest way to merge them into a single sorted array? Use a heap.
Fundamentals
How do you determine whether a linked list has a cycle?
Golang
Multithreaded Programming
If multiple threads concurrently read and write a map, what result is produced? Why does this result occur? What approaches guarantee concurrency safety?
In Golang, for highly concurrent updates (increments/decrements) to an int64, what approaches guarantee concurrency safety? An understanding of concurrent programming: there can be 3 ways: (1) locks (2) the atomic package (3) channel β multiple producers, single consumer.
Goroutines, Threads, Processes
Describe the goroutine scheduling and switching mechanism.
Channel
Golang chan characteristics: why doesn’t chan use locks, and how is it implemented under the hood?
When does it block, and how do you tell that it will block? 1) chan is implemented under the hood with a lock plus a double-ended queue. 2) Before sending, you can use the cap and len functions to check whether they are equal, but you must hold the lock. The second approach is to use select with default; in real programming, select must include a default branch to handle logic.
Redis
Basic Data Structures
string, list, set, zset, hash β the use cases and implementation principles of each data structure.
Redis usage: how do you implement a distributed lock with Redis? The most junior answer is SETNX. A better answer considers atomicity and uses a Lua script.
Principles
For a key with a TTL set, how does Redis implement key expiration? Being able to name the 2 expiration modes β active and passive (lazy) β is good. Being able to describe the random-sampling flow of the active mode earns bonus points.
What key eviction policies does Redis have? What are their characteristics? The commonly used ones are volatile-lru and volatile-ttl. What is the flow of the LRU algorithm?
Does Redis have a stop-the-world problem? When does it occur? Why? Answer: Redis is a single-process, single-threaded service; if a single task takes too long to process, it severely hurts concurrency performance. For example, during persistence, when handling and returning large values, when deleting an element from a very long list, and so on.
System Design
URL Shortener Service
Given a long URL as input, encode it and return a short URL (the key point is the choice of encoding method, e.g. how to represent the short URL and how much it can represent).
How do you find the long URL from the short URL?
For the HTTP redirect, do you choose 301 or 302? (1) Encoding method: use an ID generator to produce a 64-bit integer, then encode that integer into an alphanumeric English string (note: consider how long the string needs to be); if the answer is a hash method like md5, there will be collision problems.
Use a kv store, where the key is the short URL and the value is the long URL; either redis or mysql works.
The difference between 301 (permanent redirect) and 302 (temporary redirect) lies mainly in search engine behavior. If you want to collect statistics on user request information, use 302.
High-Concurrency ID Generation Service
Globally unique
The ID should be as small as possible
IDs are ordered by time
