DOCSEARCHbyAlgolia
Submit Docs

Ricky Wei's Technical Blog

website·Indexed 29 days ago

https://rickywei.github.io/blog/

A collection of technical notes and guides covering algorithms (KMP, Z Algorithm, Digit DP, Median Greedy), system design (Message Queues, API Authentication), and database techniques such as MySQL recursive queries using Common Table Expressions (CTE).

Tokens
3.5K
Snippets
11
Records
20
Agent score
75%

What's inside Ricky Wei's Blog

  1. Identify Message Queue (MQ) application scenarios

    Message Queues are primarily used for three architectural patterns:

    1. Decoupling: Upstream (producers) and downstream (consumers) interact via the MQ rather than directly. This allows adding new downstream modules (e.g., adding a billing analysis module to an order flow) without modifying the producer. This requires that the producer does not need to know the processing result of the consumer.
    2. Traffic Shaving (Peak Clipping): Protects downstream systems from being overwhelmed by spikes in web requests by buffering them in the MQ and allowing the downstream database or service to consume them at its own processing pace.
    3. Asynchrony: Enables multiple different downstream systems to consume the same message simultaneously, or multiple identical downstream consumers to process different messages in parallel.

  2. Minimize total distance to a set of points using Median Greedy

    To minimize the sum of distances from all numbers in a set to a single target value $x$, $x$ should be the median of the set.

    Proof logic:

    1. Sort the array in ascending order: $[a_0, ..., a_{n-1}]$.
    2. For the outermost pair $a_0$ and $a_{n-1}$, any $x$ between them results in a constant distance sum of $a_{n-1} - a_0$. If $x$ is outside this range, moving it toward the pair decreases the total distance.
    3. Repeating this logic for inner pairs ($a_1$ and $a_{n-2}$, etc.) converges on the median.
    4. If the number of elements $n$ is odd, the median is unique. If $n$ is even, any value between the two middle elements (inclusive) works.

  4. Understand the KMP algorithm and the 'next' array

    The KMP algorithm is used to determine if a string s contains a substring p. It optimizes the search process by using a next array (also known as the prefix function).

    next[i] represents the length of the longest proper prefix of the substring ending at index i that is also a suffix of that same substring. When a mismatch occurs at index j in the pattern p, instead of restarting the search from the next character in s, the algorithm uses the next array to skip unnecessary comparisons by shifting the pattern to the last known valid prefix match.

  5. Understand the Z Algorithm (Z-function)

    The Z Algorithm (also known as Extended KMP) is used to compute the Z-function for a string s. For each index i, the Z-function z[i] represents the length of the Longest Common Prefix (LCP) between the suffix of s starting at index i (the substring s[i, n-1)) and the original string s itself.

  6. Implement Digit DP for both upper and lower bounds

    To count numbers in a closed interval $[low, high]$, pad the low string with leading zeros to match the length of high. The DFS state must track both bounds:

    • limit_low: Boolean indicating if the current digit is restricted by the lower bound.
    • limit_high: Boolean indicating if the current digit is restricted by the upper bound.
    • select: Boolean indicating if a non-zero digit has been placed yet.
    • last: The value of the previous digit (used for conditions like 'stepping numbers' where adjacent digits must differ by 1).

    Memoization is only valid when both !limit_low and !limit_high are true and select is true.

    class Solution {
 public:
  int countSteppingNumbers(string low, string high) {
    const int MOD = 1e9 + 7;
    int n = high.size(), dp[n][10];
    low = string(n - low.size(), '0') + low;
    memset(dp, -1, sizeof(dp));

    function<int(int, bool, bool, bool, int last)> dfs = [&](int i, bool limit_low, bool limit_high, bool select, int last) -> int {
      if (i == n) return select;
      if (!limit_low && !limit_high && select && dp[i][last] != -1)
        return dp[i][last];
      
      int res = 0;
      if (!select && low[i] == '0') {
        res = dfs(i + 1, true, false, false, last);
      }
      
      int lo = limit_low ? low[i] - '0' : 0;
      int hi = limit_high ? high[i] - '0' : 9;
      
      for (int d = max(lo, 1 - select); d <= hi; ++d) {
        if (last != -1 && abs(d - last) != 1) continue;
        res = (res + dfs(i + 1, limit_low && d == lo, limit_high && d == hi, true, d)) % MOD;
      }
      
      if (!limit_low && !limit_high && select) dp[i][last] = res;
      return res;
    };

    return dfs(0, true, true, false, -1);
  }
};

  7. Implement API identity and permission management for open platforms

    To identify and authorize requests in an open platform API, use a combination of AppId and AppKey:

    • AppId: A unique identifier (e.g., UUID) assigned to each developer to identify who is requesting the resource.
    • AppKey: Used to differentiate permissions within the same AppId (e.g., creating sub-accounts with specific roles like 'read-only').

  8. Verify API requests and signatures on the server

    The server should perform the following validation steps in order to authenticate a request:

    1. Verify that the AppId and AppKey are valid and belong together.
    2. Verify that the AppKey has the required permissions for the specific API endpoint.
    3. Verify that the timestamp is within the allowed time window.
    4. Verify that the nonce has not been used previously.
    5. Re-calculate the signature using the same rules and the stored AppSecret to ensure it matches the provided signature.

  9. Prevent API replay attacks using timestamps and nonces

    To prevent replay attacks, include both a timestamp and a nonce (random value) in the signed parameters:

    1. Timestamp: The server verifies that the request occurred within a narrow time window (e.g., timestamp <= now <= timestamp + 60s).
    2. Nonce: The server tracks used nonces (e.g., using Redis with a TTL) to ensure a specific request is not processed more than once.

    Using only a timestamp allows replays within the window; using only a nonce allows replays after the nonce expires. Using both ensures maximum security.

    # Example: Store nonce in Redis to prevent reuse for 60 seconds
SETEX AppId+AppKey+nonce 60 ""

  10. Perform basic recursive queries using RECURSIVE CTE

    Recursive CTEs allow a query to refer to its own output. A recursive CTE consists of an initial query (the anchor member) and a recursive query (the recursive member) joined by a UNION ALL. The recursion continues until the recursive member returns an empty result set.
    WITH RECURSIVE cte (n) AS
(
  -- Anchor member: initial starting point
  SELECT 1
  UNION ALL
  -- Recursive member: refers to 'cte' and defines termination condition (n < 5)
  SELECT n + 1 FROM cte WHERE n < 5
)
SELECT * FROM cte;

  11. Implement Digit DP for a single upper bound

    When a problem only specifies an upper bound $n$, use a recursive DFS approach with memoization. Key state variables include:

    • i: The current digit position being processed.
    • limit: A boolean indicating if the current digit is restricted by the upper bound $n$. If true, the digit can only range from $0$ to the digit at $n[i]$.
    • select: A boolean indicating if any non-zero digit has been selected yet (used to handle leading zeros).
    • cnt (or other problem-specific state): Tracks the property being counted (e.g., the number of times digit '1' appears).

    Memoization is only applicable when !limit and select are true, as these states are generic and independent of the specific upper bound constraint.

    class Solution {
 public:
  int countDigitOne(int n) {
    string nums = to_string(n);
    int m = nums.size(), dp[m][10];
    memset(dp, -1, sizeof(dp));

    function<int(int, bool, bool, int cnt)> dfs = [&](int i, bool limit, bool select, int cnt)  -> int {
      if (i == m) return cnt;
      if (!limit && select && dp[i][cnt] != -1) return dp[i][cnt];
      
      int res = 0;
      if (!select) {
        res = dfs(i + 1, false, false, cnt);
      }
      
      int hi = limit ? nums[i] - '0' : 9;
      for (int d = (1 - select); d <= hi; ++d) {
        res += dfs(i + 1, limit && d == hi, true, cnt + (d == 1));
      }
      
      if (!limit && select) dp[i][cnt] = res;
      return res;
    };

    return dfs(0, true, false, 0);
  }
};

  12. Prevent message loss in a Message Queue

    To ensure that messages are not lost during the end-to-end lifecycle, implement the following three mechanisms:

    1. Producer Reliability: The producer must send the message and retry until it receives an acknowledgment (ACK) from the MQ.
    2. Broker Persistence: The MQ must ensure the message is physically written to disk (flushed from page cache) before returning an ACK to the producer.
    3. Consumer Reliability: The consumer must send an ACK back to the MQ only after the message has been successfully processed.