Ruoke Zhang

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

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

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

Storage Engine Comparison

1. In InnoDB, primary key index and data are stored together, with the primary key index B+ tree containing complete data rows; in MyISAM, index and data are stored separately, with the B tree storing index values and physical addresses of rows
2. InnoDB supports ACID transactions, MyISAM does not
3. InnoDB supports row-level locking, MyISAM does not

What is Page Split

When inserting new data into a full index page (usually 16KB), the storage engine will split the current page into two pages to accommodate the new data

Reflection

Reflection is Java’s ability to dynamically obtain class information (such as class names, methods, properties, constructors, etc.) and manipulate classes at runtime.

API

Getting Class Objects

1
2
3
4
5
6
7

String str="test";
Class<?> clazz = String.class;

String str = "test"; 
Class<?> clazz = str.getClass();

Class<?> clazz = Class.forName("java.lang.String");

Creating Objects Through Reflection

1
2
3
4
5

Class<?> clazz = Class.forName("com.example.User");
Object obj = clazz.getDeclaredConstructor().newInstance();

Constructor<?> constructor = clazz.getConstructor(String.class, int.class);
Object obj = constructor.newInstance("Alice", 25);

Getting Fields

getDeclaredField(“fieldName”)

Reflection

Reflection is Java’s ability to dynamically obtain class information (such as class name, methods, fields, constructors, etc.) and manipulate classes at runtime.

API

Getting a Class Object

1
2
3
4
5
6
7

String str="test";
Class<?> clazz = String.class;

String str = "test";
Class<?> clazz = str.getClass();

Class<?> clazz = Class.forName("java.lang.String");

Creating Objects via Reflection

1
2
3
4
5

Class<?> clazz = Class.forName("com.example.User");
Object obj = clazz.getDeclaredConstructor().newInstance();

Constructor<?> constructor = clazz.getConstructor(String.class, int.class);
Object obj = constructor.newInstance("Alice", 25);

Getting Fields

getDeclaredField("fieldName")

Global Lock

Generally used when doing full database backup. It blocks write operations and only allows read requests. Therefore, it’s usually chosen during business low-peak periods for full database backup.

1

flush tables with read lock

Table-Level Locks

Table Lock

1. Table shared read lock. Multiple threads can acquire this lock simultaneously. Threads with this lock can read the table but cannot write to it. MyISAM acquires table shared read locks when processing read requests. InnoDB defaults to row locks and handles read requests through MVCC.
2. Table exclusive write lock. Only one thread can acquire this lock and perform write operations on the table. No other threads can read this table.

1

lock tables t_student read;

Table locks are triggered by: ALTER/DROP/TRUNCATE TABLE

https://leetcode.cn/discuss/post/3579164/ti-dan-er-fen-suan-fa-er-fen-da-an-zui-x-3rqn/

Closed Interval Approach

Find Target

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    # Standard binary search framework, returns index of target element, -1 if not found
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        return -1

Find Left Boundary

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right=mid-1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return left

Left-Closed Right-Open

Find Left Boundary

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def left_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid

    return left

If target doesn’t exist, left-bound binary search returns index of smallest element > target.

SMS Verification Code Login

1. User enters phone number on login page and clicks “Get Code”. Backend validates phone format, generates a verification code, stores phone:code in Redis with 2-minute expiry.
2. User enters code and clicks “Login”. Backend compares submitted code with stored value.
3. If user doesn’t exist, create and save to database.
4. Generate random token as login credential; convert User object to Hash and store as token:userHash in Redis.

Login Status Validation

1. Requests carry token in header. RefreshTokenInterceptor intercepts all requests (passes through if no token).
2. Extract token from header, retrieve user Map from Redis using token.
3. If user exists, convert Map to UserDTO, store in ThreadLocal, and refresh token expiry.

LoginInterceptor intercepts all paths except specified public ones. If UserHolder is empty (not logged in), request is rejected.