Ruoke Zhang

0%

RPC Basics

protobuf IDL

  1. Define the .proto file: define Request/Response formats and function signatures.
  2. Protobuf generates CalculatorStub automatically.
    1
2
3
4
5
6
7
8

    channel = grpc.insecure_channel("server-ip:port")

# Client stub (a local proxy for server-side methods)
stub = CalculatorStub(channel)

# Call Stub.Add as if it were a local function
request = AddRequest(num1=2, num2=3)
response = stub.Add(request)
  3. Implement the actual logic for add on the server side.

Semantics

At most once

Common Operations

x.bit_count(): Returns the number of 1s in the binary representation of x. Can also be interpreted as the minimum number of powers of 2 needed to represent x.

Brain Teasers

2749. Minimum Operations to Make the Integer Zero

Let x = num1 - k * num2, then the problem transforms to: Can x be represented using k powers of 2 (duplicates allowed)?

Find the upper and lower bounds of x and enumerate. Plot x = num1 - k * num2 with k as x-axis and x as y-axis. The answer lies in some points on this line in the first quadrant. Analyze the equation x=2^(i1)+…2^(ik) to find possible x values.

    1. Reorganize String (Roblox)
    1. Task Scheduler (Roblox, Snowflake)
    1. Top K Frequent Words (Adobe)
    1. Top K Frequent Elements (Adobe, Bloomberg)
    1. Maximum Number of Events That Can Be Attended (Snowflake)
    1. Find K Pairs with Smallest Sums (Linkedin, Google)
    1. Last Stone Weight (Nvidia)
    1. Find Median from Data Stream (Snowflake)
  • Merge k Sorted Lists (Bloomberg, Snowflake, Nvidia, Microsoft)
    1. Stock Price Fluctuation (Google)
    1. Meeting Rooms III

Prefix Sum

    1. Subarray Product Less Than K (Airbnb)
    1. Max Consecutive Ones III (Microsoft, Expedia)
    1. Subarrays with K Different Integers (Expedia)
    1. Range Sum Query 2D - Immutable (Snowflake)
  • Subarray Sum Equals K (Bloomberg)
  • Product of Array Except Self (Bloomberg, Microsoft)
  • Meeting Rooms II (Microsoft)

Trie

    1. Add and Search Word - Data structure design (Docusign, LinkedIn, Snowflake, Rubrik, Tiktok)
    1. Longest Common Prefix (Bloomberg)
    1. Find the Length of the Longest Common Prefix (Databricks)
  • Implement Trie (Prefix Tree) (Snowflake)
    1. Design In-Memory File System (Snowflake)
    1. Remove Sub-Folders (Snowflake, Google)
    1. Search Suggestions System (Docusign, Amazon)
    1. Word Search II (Microsoft, Google, Airbnb)

Stack

  • Basic Calculator II (Tesla)
  • Max Stack (Linkedin)
  • Nested List Weight Sum II (Linkedin)
  • Valid Parentheses (Nvidia, Expedia)
    1. Evaluate Reverse Polish Notation (Microsoft)
    1. Basic Calculator (Microsoft)
    1. Valid Parentheses (Microsoft)
    1. Longest Valid Parentheses (Tiktok)
    1. Maximal Rectangle (Tiktok)
    1. Largest Rectangle in Histogram (Microsoft)
    1. Simplify Path (Snowflake, Tiktok)
    1. Remove Duplicate Letters (Expedia)
    1. Number of Visible People in a Queue (Expedia)
    1. Minimum Number of Swaps to Make the String Balanced (Expedia)
    1. Sum of Subarray Ranges (Tiktok)

Queue

    1. Design Circular Queue (Tesla, Cloudflare)
    1. Design Hit Counter (Snowflake, Cloudflare, Databricks)
    1. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Google)

Common Mistakes

    1. Design Circular Queue (Tesla, Cloudflare)

Hash

    1. First Missing Positive (Tesla)
    1. Missing Number (Meta, Microsoft, Bloomberg)

Sort

    1. Kth Largest Element in an Array (Microsoft)

Sliding Window

    1. Max Consecutive Ones III (SAP, Salesforce, LinkedIn, Meta, Google)
    1. Longest Repeating Character Replacement (Adobe, Amazon, Bytedance, Bloomberg)
    1. Maximum Number of Occurrences of a Substring (Hubspot, Salesforce)
    1. Longest Substring with At Most Two Distinct Characters (Ebay, Google, Tiktok)
    1. Longest Substring with At Most K Distinct Characters (Microsoft)
    1. Subarray Product Less Than K (Paypal, Oracle, Salesforce)
    1. Smallest Range Covering Elements from K Lists (Lyft, Databricks)
    1. Number of Subarrays of Size K and Average Greater than or Equal to Threshold (LinkedIn)

Prime Numbers

Sieve of Eratosthenes 

1
2
3
4
5
6
7
8
9

# Time complexity O(MX * log log MX)
MX = 1_000_001
is_prime = [False] * 2 + [True] * (MX - 2)  # 0 and 1 are not prime
primes = []
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False  # j is a multiple of prime i

204. Count Primes

p[i] represents the number of primes less than or equal to i. Starting from i=2, p[i]==0 <=> i is prime. Then, starting from ii, mark multiples of i as composite (by setting p[ik]=-1). And, p[i] is assigned p[i-1]+1.

KMP

https://www.zhihu.com/question/21923021/answer/37475572

28. Find the Index of the First Occurrence in a String

Pattern: abababzababab

Step 1: Construct next array while traversing pattern.

  • next[i] represents maximum common prefix-suffix length for s[0:i+1]
  • Initialize j=0, i traverses from 1 to n-1. j position indicates current common prefix-suffix s[:j]
  • During traversal, if common prefix-suffix exists, continuously compare s[i] and s[j]. If different, in loop backtrack j until s[:j] becomes common prefix-suffix. Backtrack to second longest common prefix-suffix, move j to next[j-1]
  • Compare s[i] and s[j] again. If same, move j and assign next[i]

Step 2: Compare two strings abeababeabf abeabf

755. Pour Water

Time Order

2534. Time to Pass a Gate

  1. The simulation ends when everyone has entered/exited.
  2. Time is placed in the inner loop.

Trie

440. K-th Smallest in Lexicographical Order

  • How to get lexicographical order from smallest to largest? Build a deca-tree for numbers and then traverse it in pre-order.
  • How to get the number of children of a node? Use the next node on the same level.

Alt text

TCP Retransmission

  1. Timeout Retransmission: A timer is set, which should be slightly longer than the Round-Trip Time (RTT). If the timer expires before an ACK is received, the segment is immediately retransmitted.
  2. Fast Retransmission: When three consecutive duplicate ACKs are received, the segment is retransmitted immediately.
  3. SACK (Selective Acknowledgment): The receiver can inform the sender which segments have been received and which are missing.
  4. DSACK (Duplicate SACK): If the receiver gets two identical segments (e.g., two 2s), it uses DSACK to inform the sender that it has received duplicates, preventing unnecessary retransmissions due to network latency.

TCP Flow Control

Slow Start

When transmission begins, the sender doubles its congestion window for each ACK received (exponential growth). The initial window size is 1.

Ling Shen Problem List

300. Longest Increasing Subsequence

Ling Shen Video

Define g[i] as the minimum end element of an increasing subsequence of length i+1.

Proof by contradiction: g is a strictly increasing array.

659. Split Array into Consecutive Subsequences

tail[i] is used to represent the number of subsequences ending with i. This way, when i+1 is encountered, it can be placed.

All DML operations (INSERT/UPDATE/DELETE) are first completed in the Buffer Pool

redo log

Video Explanation Alt text

  1. Implements transaction durability. redo log is flushed to disk first, then dirty pages are flushed to disk

Physical Storage Characteristics

  1. File Structure

    • Composed of fixed-size files (such as ib_logfile0, ib_logfile1)
    • Circular write (ring buffer) design
    • Physical writes are always appended to the end of the file

  2. Write Mode