Ruoke Zhang

0%

Ling Shen Problem List

Linear DP

Alt text

10. Regular Expression Matching

dp[i][j] indicates if s(0,i-1) matches p(0,j-1)

Base case: s empty, p empty → True; s empty, p xx type → True Compare s[i], p[j]: if not match and p[j] is *, and s[i] matches p[j-1], three possibilities: match one letter, zero letters, multiple letters. If not match and p[j] is *, and s[i] doesn’t match p[j-1], check zero letter option.

Reverse Linked List 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    #Answer head might change, so use dummy
    dummy=ListNode(next=head)
    pre=dummy
    #Move pre, cur to positions 1 and 2
    for _ in range(left-1):
        pre=pre.next
    cur=pre.next
    #Record current pre
    p0=pre
    #Reverse from 2 to 4, essentially changing next pointers
    for _ in range(right-left+1):
        nxt=cur.next
        cur.next=pre
        pre=cur
        cur=nxt
    #New pre,cur are 4,5
    #Connect 2 and 5
    p0.next.next=cur
    #Connect 1 and 4
    p0.next=pre
    return dummy.next

Reverse linked list focuses on pre and cur positions before start and after end. In this case, old pre.next becomes new pre, old cur.next becomes new cur. Alt text

Like Design

Use Redis sorted set: key is post ID, set stores user IDs who liked, score is timestamp of like.

When frontend views post details, backend needs to:

  1. Fetch content from database by post ID
  2. Check Redis to determine if current user liked this post
  3. Add liked field to Blog object and return to frontend
1
2
3
4

@PutMapping("/like/{id}")
public Result likeBlog(@PathVariable("id") Long id) {
    return blogService.likeBlog(id);
}

Frontend doesn’t send current like status; backend checks if user liked by checking sorted set for user ID.

Interface

Interface is an abstraction of behavior.

  1. abstract method - Before Java 8, interfaces could only have abstract methods
  2. default method - Provides method body, available since Java 8
  3. static method - Provides method body, available since Java 8, can be called via Interface.method()
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public interface MyInterface {
    // Abstract method
    void abstractMethod();

    // Default method
    default void defaultMethod() {
        System.out.println("This is the interface's default method");
        privateHelperMethod();  // Call private helper method (Note: private methods are Java 9 feature, shown here for completeness)
    }

    // Static method
    static void staticMethod() {
        System.out.println("This is the interface's static method");
    }

    // Private helper method (Java 9 feature, included for completeness)
    private void privateHelperMethod() {
        System.out.println("This is the interface's private helper method");
    }
}

public class MyClass implements MyInterface {
    @Override
    public void abstractMethod() {
        System.out.println("Implementing the interface's abstract method");
    }

    // Can choose to override default method
    @Override
    public void defaultMethod() {
        System.out.println("Overriding the interface's default method");
        MyInterface.super.defaultMethod();  // Call the interface's default method
    }
}

public class Main {
    public static void main(String[] args) {
        MyClass myClass = new MyClass();

        // Call implemented abstract method
        myClass.abstractMethod();

        // Call default method
        myClass.defaultMethod();  // Note this calls the overridden version

        // Call interface's static method
        MyInterface.staticMethod();
    }
}

Abstract Class

Abstract classes usually serve as base classes, like Person, Animal. Because different subclasses may have different method bodies for certain methods, these methods are placed as abstract methods in the abstract class.

Interface

An interface is an abstraction of behavior.

  1. Abstract methods: Before Java 8, interfaces could only have abstract methods.
  2. Default methods: Provide method bodies, available since Java 8.
  3. Static methods: Provide method bodies, available since Java 8, can be called via Interface.method().
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public interface MyInterface {
    // Abstract method
    void abstractMethod();

    // Default method
    default void defaultMethod() {
        System.out.println("This is the default method of the interface");
        privateHelperMethod();  // Call private helper method (Note: private methods are a Java 9 feature, shown here for example only)
    }

    // Static method
    static void staticMethod() {
        System.out.println("This is the static method of the interface");
    }

    // Private helper method (Java 9 feature, but included for completeness)
    private void privateHelperMethod() {
        System.out.println("This is the private helper method of the interface");
    }
}

public class MyClass implements MyInterface {
    @Override
    public void abstractMethod() {
        System.out.println("Implementing the abstract method of the interface");
    }

    // Can choose to override the default method
    @Override
    public void defaultMethod() {
        System.out.println("Overriding the default method of the interface");
        MyInterface.super.defaultMethod();  // Call the default method of the interface
    }
}

public class Main {
    public static void main(String[] args) {
        MyClass myClass = new MyClass();

        // Call the implemented abstract method
        myClass.abstractMethod();

        // Call the default method
        myClass.defaultMethod();  // Note that the overridden version is called here

        // Call the static method of the interface
        MyInterface.staticMethod();
    }
}

Abstract Class

Abstract classes typically serve as base classes, such as Person, Animal. Because the body of certain methods may differ among various subclasses, these methods are placed as abstract methods in the abstract class.

Functional Interface

The definition of a functional interface is that it must contain only one abstract method. It can have many static or default methods (with implementations), but there must be only one abstract method.

This abstract method represents that it can perform some behavior, but what specifically it does is determined by the caller through overriding this abstract method. This can be accomplished through anonymous inner classes or lambda expressions.

Functional Interface

A functional interface is defined as an interface that must contain only one abstract method. It can have many static or default methods (with implementations), but there must be only one abstract method.

This abstract method indicates that it can perform a certain behavior, but the specific action is determined by the caller through overriding this abstract method. This can be achieved using anonymous inner classes or lambda expressions.

Goals

  • Mutual exclusion (e.g., A and B don’t run at the same time) — process mutual exclusion
    • solved with locks
  • Ordering (e.g., B runs after A does something) — process synchronization
    • solved with condition variables OR semaphores

CS 537 Videos 小林coding

Locks

You can think of a lock as a mutex. It’s just a variable with two states: available/acquired. Each thread can acquire and release it. Reference: OSTEP-Locks

Consistency

Cache Update Strategies

  1. Memory Eviction: Redis automatically evicts data when memory is low; cache updated on next request.
  2. TTL Expiry: Set TTL on cached data; deleted automatically when expired; updated on next request.
  3. Active Update: Update cache simultaneously with database modification.

Cache-Database Consistency

Concurrent requests can cause inconsistency regardless of update order (cache first or database first).

Use Cache Aside strategy: cache only updated during read operations.

  • Write strategy: When modifying data, update database and delete cache.
  • Read strategy: When reading data, if cache miss, read from database and update cache.

Update-Then-Delete (Delayed Double Delete)

Thread A reading, Thread B updating simultaneously:

Global ID Generator: Redis Auto-increment

Disadvantages of database auto-increment IDs:

  1. May expose business metrics: users could infer daily coupon sales.
  2. Large coupon volumes lead to oversized IDs; sharding causes ID conflicts.

Alt text

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

// Sign bit 0 + 31-bit timestamp + 32-bit sequence number
public long nextId(String keyPrefix){
    // Generate timestamp
    LocalDateTime now=LocalDateTime.now();
    long nowSecond=now.toEpochSecond(ZoneOffset.UTC);
    long timestamp=nowSecond-BEGIN_TIMESTAMP;
    // Generate sequence number. Same key per day
    String date=now.format(DateTimeFormatter.ofPattern("yyyy:MM:dd"));
    long count=  stringRedisTemplate.opsForValue().increment("icr:"+keyPrefix+":"+date);
    // Combine and return
    return timestamp<<COUNT_BITS|count;
}

keyPrefix represents object type, e.g., coupon order.