Ruoke Zhang

0%

Publish on: Classify at:

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.

Publish on: Classify at:
    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)

Publish on: Classify at:

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.

Publish on: Classify at:

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

Publish on: Classify at:

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.

Publish on: Classify at:

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.

Publish on: Classify at:

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.

Publish on: Classify at:

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.

Publish on: Classify at:

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

Publish on: Classify at:

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

Redo Log

Video (Chinese) Alt text

  1. Provides transaction durability. Redo log is flushed first; dirty pages are flushed later.

Physical Storage Characteristics

  1. File structure

    • Fixed-size files (e.g., ib_logfile0, ib_logfile1)
    • Circular write (ring buffer)
    • Physical appends are always to the end of file

  2. Write pattern

1
2

// Pseudocode for physical writes
write(log_file, log_record, log_size); // always append

Write-Ahead Logging (WAL)

  • Update data pages in the Buffer Pool; the page becomes a dirty page.
  • Write the physical changes (e.g., “page X, offset Y, write Z”) sequentially to the redo log buffer.
  • On COMMIT, behavior depends on innodb_flush_log_at_trx_commit (commonly 1 by default):
ValueBehaviorDurability
1 (default)1) write to OS page cache; 2) fsync() immediatelyFull durability
0Batch write+fsync every 1sMay lose up to 1s of data
2Write to OS page cache but delay fsyncSafe unless OS crashes
  • Dirty page flushing is asynchronous; background threads flush Buffer Pool pages to disk.

Alt text