DOCSEARCHbyAlgolia
Submit Docs

Jingzhen Blog

website·Indexed 30 days ago

https://jingzhen.vercel.app/

A technical blog featuring content on algorithms and data structures, including dynamic programming, greedy algorithms, backtracking, BFS, DFS, hash tables, and binary search.

Tokens
163.4K
Snippets
447
Records
592
Agent score
73%

What's inside Jingzhen

  1. Overview of Java Thread Pool Framework

    Java provides a thread pool framework in the java.util.concurrent package to manage and reuse threads, reducing the overhead of frequent thread creation and destruction. The framework consists of three primary components:

    • Executor: The top-level interface defining the basic execute(Runnable command) method.
    • ExecutorService: Extends Executor to provide lifecycle management and task submission methods like submit() and shutdown().
    • Executors: A utility class providing static factory methods to create common types of thread pools.

  2. Overview of ConcurrentHashMap characteristics

    ConcurrentHashMap is a thread-safe, high-performance hash table implementation in the java.util.concurrent package. Key characteristics include:

    • Thread Safety: Supports concurrent read/write operations without external synchronization.
    • High Concurrency: Uses CAS (Compare-And-Swap) and fine-grained locking to avoid full-table locking.
    • Lock-free Reads: Most read operations are non-blocking, utilizing volatile keywords and memory barriers for visibility.
    • Null Constraints: Does NOT allow null keys or null values; attempting to insert either will throw a NullPointerException.
    • Weak Consistency: Iterators provide weak consistency and do not guarantee that data remains unchanged during traversal.

  3. Understand the JVM Lock Upgrade Mechanism

    The JVM optimizes concurrency performance through a lock upgrade mechanism that dynamically adapts to competition levels. Locks transition through three stages:

    1. Biased Locking: Used when there is no competition.
    2. Lightweight Locking: Uses spin-locks to optimize low-level competition.
    3. Heavyweight Locking: Blocks threads to handle intense competition.

    This mechanism relies on the Mark Word in the object header, which records the lock state and controls the transition between these levels.

  4. Determine if two strings are isomorphic

    Two strings s and t are isomorphic if the characters in s can be replaced to get t while preserving the order of characters. The mapping must be one-to-one: each character in s must map to exactly one character in t, and no two different characters in s can map to the same character in t. Characters can map to themselves.

    Constraints:

    • String lengths are equal.
    • Lengths range from 1 to 5 * 10^4.
    • Strings consist of valid ASCII characters.

  5. Understand the relationship between Lock and AQS

    In Java, Lock is a high-level interface that defines the interaction between the user and the lock (e.g., lock() and unlock()), hiding implementation details. AbstractQueuedSynchronizer (AQS) is the underlying framework used by implementers to handle synchronization state, thread queuing, waiting, and waking.

    Key relationships:

    • Lock is the interface; AQS is the abstract base class providing the implementation logic.
    • AQS uses a volatile int state variable and a FIFO queue (CLH queue) to manage synchronization.
    • Common synchronizers like ReentrantLock, CountDownLatch, and Semaphore are built upon AQS.

  6. Determine if a number is a Happy Number

    A 'Happy Number' is defined by the following process: starting with a positive integer, replace the number with the sum of the squares of its digits. Repeat this process until the number equals 1 (where it stays), or it loops endlessly in a cycle that does not include 1. If the process ends in 1, the number is a happy number.

  7. Understand ThreadLocal basic concepts and usage

    ThreadLocal is used in Java to provide independent variable copies for each thread. Each thread can access and modify its own copy without affecting other threads, providing thread isolation and avoiding concurrency issues without complex synchronization. It is commonly used to store context-specific data like userId or traceId that needs to be accessible across multiple method calls in a single thread without passing them as parameters through every method signature.

  8. Understand ThreadLocal internal architecture

    ThreadLocal provides thread-local variables where each thread has its own independently initialized copy of the variable.

    Key components include:

    • Thread Instance: Each thread contains a ThreadLocalMap field.
    • ThreadLocalMap: An internal class of Thread that stores all ThreadLocal variables for that specific thread. It consists of a series of Entry objects.
    • Entry: A key-value pair where the key is a weak reference to the ThreadLocal instance and the value is the thread-specific variable copy.
    • Weak References: Using weak references for keys allows the GC to reclaim the ThreadLocal object when it is no longer in use, though the value may persist if not explicitly cleared.

  9. Find the intersection node of two single linked lists

    Given the head nodes of two single linked lists, headA and headB, the goal is to find the node where the two lists intersect. If no intersection exists, return null. The lists are guaranteed to have no cycles, and the original structure must be preserved after the function returns.

  10. Find the largest monotone increasing integer less than or equal to n

    A monotone increasing integer is defined as an integer where every pair of adjacent digits x and y satisfies x <= y. To find the largest such integer less than or equal to a given n, use a greedy approach: traverse the digits from right to left. When a digit is smaller than the one preceding it, decrement the preceding digit and mark the current position as the start of a sequence that must be converted to '9's. This ensures the resulting number is the largest possible while maintaining the monotone increasing property.
    class Solution {
    public int monotoneIncreasingDigits(int N) {
        // Convert integer N to a character array for digit manipulation
        char[] arr = Integer.toString(N).toCharArray();

        int len = arr.length;
        int marker = len; // Marks the start position to be changed to '9'

        // Traverse the array backwards to find violations of the monotone increasing property
        for (int i = len - 1; i > 0; i--) {
            if (arr[i] < arr[i - 1]) {
                // Decrement the preceding digit to maintain the property
                arr[i - 1]--;
                // Update marker: all digits from this index onwards should become '9'
                marker = i;
            }
        }

        // Fill all positions from the marker to the end with '9'
        for (int i = marker; i < len; i++) {
            arr[i] = '9';
        }

        // Convert the character array back to an integer
        return Integer.parseInt(new String(arr));
    }
}

  11. Implement an LRU Cache data structure

    An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items. When the capacity is reached and a new item is inserted, the least recently accessed item is evicted.

    Key requirements:

    • LRUCache(int capacity): Initialize the cache with a positive integer capacity.
    • int get(int key): Return the value of the key if it exists, otherwise return -1. This operation must move the accessed key to the 'most recently used' position.
    • void put(int key, int value): Update the value if the key exists, or insert the key-value pair if it doesn't. If the insertion exceeds the capacity, the least recently used item must be evicted.
    • Time Complexity: Both get and put must operate in O(1) average time complexity.

  12. Implement data sharing between threads in Java

    Depending on the requirements for thread safety and lifecycle, use one of the following patterns to share data between a parent and child thread:

    1. Shared Variables: Use static or instance variables. Use volatile, synchronized blocks, or Atomic classes (e.g., AtomicInteger) to ensure visibility and atomicity.
    2. Constructor/Object Passing: Pass a shared data object into the child thread's constructor or runnable. This avoids global state and improves maintainability.
    3. InheritableThreadLocal: Use this for context-like data that should be automatically copied from parent to child upon thread creation.
    4. BlockingQueue: Use a BlockingQueue for producer-consumer patterns where the parent produces data and the child consumes it asynchronously.
    // Example of Shared Variable with volatile for visibility
private static volatile int sharedData = 0;

// Example of Shared Object with synchronization
static class SharedData {
    private int value;
    public synchronized void setValue(int value) { this.value = value; }
    public synchronized int getValue() { return this.value; }
}