Top 15 Must‑Know System Design & Coding Interview Questions Explained

Preface

Hello, I'm Su San. Recently a reader went to a Shopee interview, so I share the real interview questions.

Sort a linked list

Difference between symmetric and asymmetric encryption algorithms

How TCP guarantees reliability

Five I/O models

Hystrix working principle

Delayed task handling

HTTPS request process

Transaction isolation levels and repeatable‑read implementation

When indexes become ineffective

What is virtual memory

Ranking implementation (e.g., exam score ranking)

Distributed lock implementation

Zero‑copy

synchronized keyword

Distributed ID generation schemes and Snowflake algorithm

1. Sort a Linked List

Given the head node of a linked list, sort it in ascending order and return the sorted list.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

The problem can be solved with a two‑pointer + merge sort algorithm in four steps:

Use fast and slow pointers to find the middle node.

Cut the list at the middle.

Recursively sort the left and right sub‑lists with merge sort.

Merge the two sorted sub‑lists.

Complete code:

class Solution{<br/>    public ListNode sortList(ListNode head){<br/>        if(head == null || head.next == null) return head;<br/>        ListNode slow = head;<br/>        ListNode fast = head;<br/>        while(fast.next != null && fast.next.next != null){<br/>            fast = fast.next.next;<br/>            slow = slow.next;<br/>        }<br/>        ListNode mid = slow.next;<br/>        slow.next = null;<br/>        ListNode left = sortList(head);<br/>        ListNode right = sortList(mid);<br/>        return merge(left, right);<br/>    }<br/>    public ListNode merge(ListNode left, ListNode right){<br/>        ListNode dummy = new ListNode(0);<br/>        ListNode tail = dummy;<br/>        while(left != null && right != null){<br/>            if(left.val <= right.val){<br/>                tail.next = left;<br/>                left = left.next;<br/>            }else{<br/>                tail.next = right;<br/>                right = right.next;<br/>            }<br/>            tail = tail.next;<br/>        }<br/>        if(left != null) tail.next = left;<br/>        else if(right != null) tail.next = right;<br/>        return dummy.next;<br/>    }<br/>}<br/>

2. Difference Between Symmetric and Asymmetric Encryption

Key concepts:

Plaintext: unencrypted data.

Ciphertext: encrypted data.

Key: parameter used for encryption/decryption; can be symmetric or asymmetric.

Encryption: process of turning plaintext into ciphertext.

Decryption: reverse process.

Symmetric encryption uses the same key for both encryption and decryption. Common algorithms: AES, 3DES, DES, RC5, RC6 .

Asymmetric encryption uses a pair of keys (public and private). The public key encrypts data; only the matching private key can decrypt. Common algorithms: RSA, ElGamal, DSA, Diffie‑Hellman, ECC .

3. How TCP Guarantees Reliability

Three‑way handshake for connection establishment and four‑way handshake for termination ensure reliable start and end.

TCP is stateful: it tracks sent, acknowledged, and missing packets, guaranteeing ordered delivery and error‑free transmission.

Control mechanisms include checksum, ACK responses, timeout retransmission, duplicate data discard, flow control (sliding window), and congestion control.

4. Five I/O Models

4.1 Blocking I/O

The calling process blocks until the kernel has prepared data and copied it to user space.

4.2 Non‑Blocking I/O

If the kernel data isn’t ready, the call returns an error immediately, allowing the application to poll later.

4.3 I/O Multiplexing – select

Using select, a process can monitor multiple file descriptors and returns when any become ready for reading.

Limitations of select:

Maximum number of connections is limited (typically 1024 on Linux).

After select returns, the kernel must iterate over the fd set to find ready descriptors.

4.4 I/O Multiplexing – epoll

epoll solves select ’s drawbacks by using an event‑driven mechanism: register a fd with epoll_ctl, and when the fd becomes ready the kernel notifies the process via callbacks, eliminating the need to scan all fds.

4.5 Signal‑Driven I/O

The kernel sends a signal (e.g., SIGIO) when data is ready, allowing the application to perform other work instead of polling.

4.6 Asynchronous I/O (AIO)

AIO returns immediately after the request is submitted; the kernel notifies the application via a signal when the operation completes.

5. Hystrix Working Principle

Hystrix provides two command objects: HystrixCommand and HystrixObservableCommand, representing a single dependency request.

HystrixCommand and HystrixObservableCommand encapsulate a request to a remote service.

Execution steps:

Build the command.

Execute the command (four ways): R execute() – synchronous, blocking. Future queue() – asynchronous, returns a Future. Observable observe() – creates and subscribes to an Observable. Observable toObservable() – cold Observable, executes on subscription.

Check if the response is cached.

Check if the circuit breaker is open; if open, go directly to fallback.

Check thread‑pool / semaphore / queue status.

Execute the actual task.

Record execution metrics for circuit‑breaker health.

If the command fails, run the user‑defined fallback.

Return the result (as an Observable or direct value).

6. Delayed Task Handling

Common scenarios: order auto‑cancellation after 30 minutes, sending SMS 15 minutes after registration, etc. Typical solutions:

JDK DelayQueue Time‑wheel algorithm

Database schedulers (e.g., Quartz)

Redis ZSET Message‑queue delayed queues

7. HTTPS Request Process

HTTPS = HTTP + SSL/TLS; SSL/TLS encrypts data, HTTP transports it.

SSL = Secure Sockets Layer, TLS = Transport Layer Security (successor of SSL 3.0).

HTTPS flow:

User enters an HTTPS URL; browser connects to server port 443.

Server presents its digital certificate (public key).

Client validates the certificate; if valid, it generates a symmetric session key and encrypts it with the server’s public key.

Client sends the encrypted session key to the server.

Server decrypts the session key with its private key and uses it to encrypt/decrypt subsequent data.

8. Transaction Isolation Levels and Repeatable‑Read Implementation

8.1 Four Isolation Levels

To prevent dirty reads, non‑repeatable reads, and phantom reads, databases define four isolation levels: Read Uncommitted, Read Committed, Repeatable Read, Serializable .

Read Uncommitted : allows dirty reads, non‑repeatable reads, and phantom reads.

Read Committed : prevents dirty reads but still allows non‑repeatable and phantom reads.

Repeatable Read : prevents dirty and non‑repeatable reads; phantom reads may still occur.

Serializable : highest isolation; eliminates all three anomalies but reduces concurrency.

Typical concurrency problems per level:

Read Uncommitted – dirty, non‑repeatable, phantom. Read Committed – non‑repeatable, phantom. Repeatable Read – phantom. Serializable – none.

8.2 Read View Visibility Rules

In InnoDB, a Read View determines which versions of rows are visible to a transaction. Key variables:

m_ids : list of active transaction IDs. max_limit_id : next transaction ID to be assigned. min_limit_id : smallest active transaction ID. creator_trx_id : ID of the transaction that created the read view.

Visibility checks:

If trx_id < min_limit_id, the version was committed before the read view and is visible.

If trx_id >= max_limit_id, the version was created after the read view and is invisible.

If min_limit_id ≤ trx_id < max_limit_id, three sub‑cases apply:

If trx_id is in m_ids and equals creator_trx_id, the row is visible (it was created by the current transaction).

If trx_id is in m_ids but not equal to creator_trx_id, the row is invisible (still uncommitted by another transaction).

If trx_id is not in m_ids, the row was committed before the read view and is visible.

8.3 How Repeatable Read Is Implemented

Repeatable‑read isolation is achieved via MVCC (Multi‑Version Concurrency Control). Each transaction sees a consistent snapshot (the read view) throughout its lifetime, preventing non‑repeatable reads.

Steps for a SELECT under MVCC:

Obtain the transaction’s own version ID.

Create a read view.

Fetch rows and compare each row’s version ID with the read view.

If a row is not visible, retrieve the appropriate version from the undo log.

Return the rows that satisfy the visibility rules.

In InnoDB, MVCC is realized by combining Read View with an Undo Log that stores historical snapshots.

8.4 Example of Repeatable Read

Two transactions A (ID 100) and B (ID 101) operate on a core_user table. Transaction A creates a read view (min = 100, max = 102, creator = 100). After B updates the row to “Cao Cao” and commits, A’s subsequent query still sees the original “Sun Quan” because it reuses the same read view.

9. When Indexes Fail

Using OR in the WHERE clause.

Missing quotes around string literals.

Wildcard patterns with LIKE that start with %.

Querying a composite index without using its leftmost column.

Applying MySQL built‑in functions to indexed columns.

Arithmetic operations on indexed columns.

Using != or <> on indexed columns.

Using IS NULL or IS NOT NULL on indexed columns.

Mismatched encoding in join columns.

When the optimizer estimates a full table scan to be cheaper than using the index.

10. What Is Virtual Memory

Virtual memory provides each process with its own address space. The OS maps virtual pages to physical pages, allowing programs to request virtual memory while the hardware uses physical memory.

Benefits:

Virtual address space can be larger than physical memory.

Multiple virtual pages can map to the same physical page.

Zero‑copy leverages virtual memory: by mapping the same physical page into both kernel and user spaces, data copying between them is avoided.

11. Ranking Implementation (e.g., Exam Score Ranking)

Redis zset (sorted set) is commonly used for leaderboards.

zadd key score member [score member ...]
zrank key member

Internally, Redis uses a ziplist or skiplist for storage, suitable for ranking, social likes, etc.

12. Distributed Lock Implementation

Distributed locks coordinate access to shared resources across multiple processes. Redis is a popular choice. SETNX + EXPIRE (separate commands) – vulnerable to lock leakage if the process crashes between the two commands. SETNX + value = expiration timestamp – requires synchronized clocks and lacks a unique owner identifier. SET key value NX EX ttl – atomic but may release the lock before the business logic finishes.

Extended SET with a unique request ID and a Lua script for safe release.

Redisson library – adds a watchdog thread that automatically extends the lock’s TTL while the holder is alive.

12.1 SETNX + EXPIRE (separate)

if (jedis.setnx(key, lock_value) == 1) {<br/>    expire(key, 100); // set TTL<br/>    try { do something } finally { jedis.del(key); }<br/>}<br/>

Problem: if the process crashes after SETNX but before EXPIRE, the lock never expires.

12.2 SETNX + expiration timestamp

long expires = System.currentTimeMillis() + expireTime;<br/>String expiresStr = String.valueOf(expires);<br/>if (jedis.setnx(key, expiresStr) == 1) return true;<br/>String current = jedis.get(key);<br/>if (current != null && Long.parseLong(current) < System.currentTimeMillis()) {<br/>    String old = jedis.getSet(key, expiresStr);<br/>    if (old != null && old.equals(current)) return true;<br/>}<br/>return false;<br/>

Drawbacks: requires synchronized clocks and may suffer from race conditions when multiple clients try to acquire an expired lock.

12.3 SET with NX and EX

if (jedis.set(key, lock_value, "NX", "EX", 100) == 1) {<br/>    try { do something } finally { jedis.del(key); }<br/>}<br/>

Issues: lock may expire before the business logic finishes; another client could delete the lock.

12.4 SET with unique request ID + Lua release

if (jedis.set(key, uni_id, "NX", "EX", 100) == 1) {<br/>    try { do something } finally {<br/>        if (uni_id.equals(jedis.get(key))) jedis.del(key);<br/>    }<br/>}<br/>

Lua script for atomic check‑and‑delete:

if redis.call('get', KEYS[1]) == ARGV[1] then<br/>    return redis.call('del', KEYS[1])<br/>else<br/>    return 0<br/>end;<br/>

12.5 Redisson

Redisson starts a watchdog thread that periodically extends the lock’s TTL while the holder thread is alive, preventing premature expiration.

13. Zero‑Copy

Zero‑copy eliminates copying data between user and kernel spaces.

13.1 Traditional I/O Flow

Four context switches and four data copies (two CPU copies, two DMA copies).

13.2 mmap + write

Using mmap maps a file directly into the process’s address space, sharing the same physical page with the kernel.

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);<br/>

Result: 4 context switches, 3 copies (2 DMA, 1 CPU).

13.3 sendfile

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);<br/>

Result: 2 context switches, 3 copies (2 DMA, 1 CPU).

13.4 sendfile + DMA scatter/gather

Result: 2 context switches, 2 DMA copies – true zero‑copy (no CPU copying).

14. synchronized

The synchronized keyword provides a monitor lock for methods or code blocks.

Compiled bytecode contains monitorenter and monitorexit for synchronized blocks.

Methods marked with the ACC_SYNCHRONIZED flag are synchronized.

14.1 monitorenter / monitorexit / ACC_SYNCHRONIZED

For a synchronized block, the JVM inserts monitorenter before the block and monitorexit after it. For a synchronized method, the method’s flag includes ACC_SYNCHRONIZED.

14.2 Monitor (ObjectMonitor)

In HotSpot, each object has an associated monitor (ObjectMonitor) that manages lock ownership, wait sets, and recursion counts.

14.3 Java Monitor Working Mechanism

Thread attempts to acquire the monitor and enters the entry list.

When acquired, the thread becomes the owner and the lock count increments.

Calling wait() moves the thread to the wait set and releases the monitor. notify() / notifyAll() wakes waiting threads, which then try to reacquire the monitor.

Upon method/block exit, the monitor is released.

14.4 Object Header and Mark Word

Each object header contains a Mark Word (hash code, GC age, lock state, thread ID, etc.) and a class pointer. For heavyweight locks, the Mark Word points to the monitor object.

15. Distributed ID Generation Schemes and Snowflake Algorithm

Common schemes:

UUID

Database auto‑increment IDs

Snowflake algorithm

Baidu UidGenerator

Meituan Leaf

Snowflake generates 64‑bit IDs:

1 bit: sign (always 0 for positive IDs).

41 bits: timestamp (milliseconds since a custom epoch).

10 bits: machine identifier.

12 bits: sequence number within the same millisecond.