Ruoke Zhang

0%

Publish on: Classify at:

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.

Publish on: Classify at:

ClassFile

After a Java source file is compiled by javac, it becomes a .class bytecode file and then runs on the JVM. A ClassFile is a structured specification; all .class files must conform to this format. Alt text

Basic Info

Alt text

  1. magic number: 0xCAFEBABE. Every .class must start with these 4 bytes.
  2. Version number, representing the compiler (javac) version.
  3. access flags

Constant Pool

Alt text There are 14 kinds of constants, grouped into literals and symbolic references. Literals are strings, final constants, etc. Symbolic references are things like method names and field names; they point to a string entry, i.e., a literal.

Publish on:

Heap

    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)