Good for whiteboarding

• Shortest Word Distance II
• Strobogrammatic Number II
• Factor Combinations
• Ternary Expression Parser
• Find Permutation
• Zigzag Iterator
• Construct Binary Tree from String

Original video

• Eval a polynomical A(x) at x0 : Horner’s rule
• Mutlply two polys:
  • Closed form at O(n^2) naively -> O(nlogn) possible
  • Equivalent to convolution of vectors A * reverse(B) - inner products of all possible shifts
• Poly representations:
  • Samples for n points with all distince xs.
    • Convert between this and coefficient form in O(nlogn)
    • Sampling n points takes O(n^2) in total
  • A sequence of n roots
• Eval A(x) for x in X: D&C by even/odd i
  • A(x) = A_even(x^2) + x * A_odd(x^2)
  • Derive the recursion and cost => draw the recursion tree and we see it is still n^2
  • Square a number on the unit circle on the complex plane
• FFT is the d&c algo for DFT (coefficent to sample form)
  • Fast poly multiplicatin: FFT(A) * FFA(B) and then do inverse FFT
• Similar techique

Good for whiteboarding

• Number of Sets of K Non-Overlapping Line Segments
• Repeated String Match
• Spiral Matrix III
• Find And Replace in String
• Online Election
• Previous Permutation With One Swap
• Minimum Number of Days to Make m Bouquets
• Vowel Spellchecker
• Number of Nodes in the Sub-Tree With the Same Label

Check If Word Is Valid After Substitutions

• First attempt TLE

Mini Parser

• Corner cases

Stamping The Sequence

• My optimization was wrong

Largest Merge Of Two Strings

• My optimization was wrong

Remove Zero Sum Consecutive Nodes from Linked List

Good for whiteboarding

• Maximum XOR of Two Numbers in an Array
• Map Sum Pairs
• Find the Longest Substring Containing Vowels in Even Counts
• Diagonal Traverse II
• Remove Sub-Folders from the Filesystem
• Course Schedule IV
• Number of Subsequences That Satisfy the Given Sum Condition
• Search Suggestions System
• Number of Good Leaf Nodes Pairs
• Maximum Score from Performing Multiplication Operations
• Correct a Binary Tree

Shopping Offers

• First attempt TLE

Maximum Number of Events That Can Be Attended

• My gut feeling was wrong

Shortest Unsorted Continuous Subarray

• First attempt WA

Path with Maximum Probability

• First attempt TLE

Good for whiteboarding

• Sequential Digits
• Stone Game II
• Maximum Subarray Sum with One Deletion
• 1202. Smallest String With Swaps
• Reverse Substrings Between Each Pair of Parentheses
• Greatest Sum Divisible by Three
• Count Number of Nice Subarrays
• Most Profit Assigning Work
• Minimum Cost Tree From Leaf Values
• Filling Bookcase Shelves
• Delete Columns to Make Sorted II
• 3Sum With Multiplicity

Can I Win

• My algo was wrong

Most Stones Removed with Same Row or Column

• How to prove it works?

[Number of Closed Islands] (https://leetcode.com/submissions/detail/403350247/)

• My optimization was wrong

Good for whiteboarding

• Find Eventual Safe States
• Insert Interval
• Regions Cut By Slashes
• Convert to Base -2
• 935. Knight Dialer
• Guess Number Higher or Lower II
• Adding Two Negabinary Numbers
• 1296. Divide Array in Sets of K Consecutive Numbers

Minimum Area Rectangle

• First attempt got TLE
• Multiple solutions

Last Stone Weight II

• My gut feeling was wrong

1124. Longest Well-Performing Interval

• My algo was wrong

Good for whiteboarding

• Path In Zigzag Labelled Binary Tree
• Simplify Path
• Push Dominoes
• Unique Substrings in Wraparound String
• 1361. Validate Binary Tree Nodes

Champagne Tower

• My first attempt was wrong

Number of Subarrays with Bounded Maximum

• Corner case

988. Smallest String Starting From Leaf

• My optimization was wrong

Additive Number

• First attempt missed a corner case

Super Pow

• My gut feeling was wrong

Longest Word in Dictionary through Deleting

• Official insight is cleaner than mine
• First attempt missed a corner case

Good for whiteboarding

• Lexicographical Numbers
• 652. Find Duplicate Subtrees

Iterator for Combination

• My optimization was incorrect

Good for whiteboarding

• Find All Duplicates in an Array
• Random Flip Matrix
• Number of Atoms
• Minimize Max Distance to Gas Station
• Confusing Number II

The Maze III

• My optimization was wrong

Coin Path

• My optimization was wrong

Minimum Number of Days to Eat N Oranges

• Took me too long

Maximum Number of Non-Overlapping Substrings

• My optimization was wrong

Good for whiteboarding

• Find Right Interval
• Nth Digit

Student Attendance Record II

• Official insight cleaner than mine

Rectangle Area II

• Took me too long to figure out the decomposition

Trapping Rain Water II

• Unable to come up with the insight myself

Russian Doll Envelopes

• My algo was incorrect

Good for whiteboarding

• Increasing Subsequences

Minimum Moves to Equal Array Elements II

• Whiteboard version has bug

Good for whiteboarding

• Basic Calculator III
• Build Array Where You Can Find The Maximum Exactly K Comparisons
• Minimum Distance to Type a Word Using Two Fingers
• Longest Chunked Palindrome Decomposition
• 24 Game

Find the Kth Smallest Sum of a Matrix With Sorted Rows

• My gut feeling was wrong

String Compression II

• My algo was wrong

Find the Closest Palindrome

• Corner cases

Minimum Cost to Make at Least One Valid Path in a Grid

• Failed to see the insight

1096. Brace Expansion II

• Compare and contrast with Parsing A Boolean Expression

Minimum Number of Increments on Subarrays to Form a Target Array

• Took me too long

642. Design Search Autocomplete System

• 2 WAs

Numbers With Repeated Digits

• Took me too long

Maximum Length of Pair Chain

• How to prove we can do greedy

Circular Array Loop

• My gut feeling was wrong

Making File Names Unique

• My optimization was wrong

Monotone Increasing Digits

• Multiple solutions

Binary Subarrays With Sum

• Multiple solutions

Matchsticks to Square

• A lot trickier than it appears!

Good for whiteboarding

• 956. Tallest Billboard
• 600. Non-negative Integers without Consecutive Ones
• 920. Number of Music Playlists
• 995. Minimum Number of K Consecutive Bit Flips
• 664. Strange Printer
• Print Words Vertically
• Number of Ways of Cutting a Pizza
• Max Dot Product of Two Subsequences
• Arithmetic Slices II - Subsequence
• Paint House III

952. Largest Component Size by Common Factor

• First attempt missed 1 corner case
• Python is too slow for this problem

902. Numbers At Most N Given Digit Set

• First attempt missed 1 corner case
• Multiple solutions

Ways to Split Array Into Three Subarrays

• 2 WAs

Replace the Substring for Balanced String

• First attempt WA

Maximum Profit in Job Scheduling

• Took me too long

Good for whiteboarding

• 871. Minimum Number of Refueling Stops
  • Multiple ideas
• Sum of Mutated Array Closest to Target
• Get Equal Substrings Within Budget
• Video Stitching
• Smallest Integer Divisible by K
• Minimum Area Rectangle II
• 1238. Circular Permutation in Binary Representation
• Construct the Lexicographically Largest Valid Sequence
• Maximum Score From Removing Substrings
• 233. Number of Digit One
• Smallest Integer Divisible by K
• Minimum Area Rectangle II
• 1238. Circular Permutation in Binary Representation
• Minimum Number of Taps to Open to Water a Garden

RLE Iterator

• The official solution is cleaner than mine

Checked 10+ workflow engines. Here are my conclusions:

• It is not designed for high traffic (> 100 per sec) + short lived task case (< 10 sec). At most one requirement can be satisfied
• However, WE should support many executing tasks, e.g., 100k tasks managed by the workflow engine
• Evolution lineage

AWS Simple Workflow -> Uber Cadence -> Temporal
		    -> AWS Step Function

Concepts

• Workflow: similiar to the coordinator in saga. Its code is hosted on the workflow worker, which is your process
  • The communication between workflow worker and cadence service is encapsulated in a decision task (also called workflow task), e.g., when an external event happens to the workflow, a decision task will be created and dispatched to WW
• Activity: similar to the sub txn component in saga. Its code is hosted on the activity worker, which is your process and often the same process as the workflow worker
  • The communciation between activity worker and cadence service is encapsulated in the activity task, e.g., WW sends a ScheduleActivityTask to cadence, which will dispatch a corresponding activity task to the AW
• Execution history: persistent log to support exactly-once, all-or-nothing semantics. All task data will be persisted too to support replay during recovery

Architecture

• Front end: API gateway
• Matching service: task scheduling, dispatching, and task list
  • backed by task storage
• History service: workflow state, timer q, and transfer q
  • backed by event, workflow, visibility storage

Good for whiteboarding

• 629. K Inverse Pairs Array
• 878. Nth Magical Number
• 887. Super Egg Drop
• Sell Diminishing-Valued Colored Balls
• Patching Array
• Jump Game VI

780. Reaching Points

• Many corner cases

Minimum Domino Rotations For Equal Row

• My gut feeling was wrong

862. Shortest Subarray with Sum at Least K

• My DP appoarch didn’t work

927. Three Equal Parts

• Corner cases

906. Super Palindromes

• Corner cases

Decoded String at Index

• Official insight cleaner than mine

Dota2 Senate

• O(n) runtime

Perfect Rectangle

Minimum Score Triangulation of Polygon

• My gut feeling was wrong

Version 2.3

Data structure

public class KafkaConsumer<K, V> implements Consumer<K, V> {

   private final ConsumerCoordinator coordinator;
   private final SubscriptionState subscriptions;
}

public class SubscriptionState {

    /* the partitions that are currently assigned, note that the order of partition matters (see FetchBuilder for more details) */
    private final PartitionStates<TopicPartitionState> assignment;
    /* the list of topics the user has requested */
    private Set<String> subscription;


    private static class TopicPartitionState {

        private FetchState fetchState;
        private FetchPosition position; // last consumed position
}

public class PartitionStates<S> {

    private final LinkedHashMap<TopicPartition, S> map = new LinkedHashMap<>();
    private final Set<TopicPartition> partitionSetView = Collections.unmodifiableSet(map.keySet());

    public static class PartitionState<S> {
        private final TopicPartition topicPartition;
        private final S value;
}
}
}

Inside ConsumerCoordinator

In org.apache.kafka.clients.consumer.internals.ConsumerCoordinator - the local proxy for consumer coordinator.

    private RequestFuture<Void> sendOffsetCommitRequest(final Map<TopicPartition, OffsetAndMetadata> offsets) {
        Node coordinator = checkAndGetCoordinator();

        // create the offset commit request
        Map<String, OffsetCommitRequestData.OffsetCommitRequestTopic> requestTopicDataMap = new HashMap<>();
        for (Map.Entry<TopicPartition, OffsetAndMetadata> entry : offsets.entrySet()) {
            TopicPartition topicPartition = entry.getKey();
            OffsetAndMetadata offsetAndMetadata = entry.getValue();
            OffsetCommitRequestData.OffsetCommitRequestTopic topic = requestTopicDataMap
                    .getOrDefault(topicPartition.topic(),
                            new OffsetCommitRequestData.OffsetCommitRequestTopic()
                                    .setName(topicPartition.topic())
                    );

            topic.partitions().add(new OffsetCommitRequestData.OffsetCommitRequestPartition()
                    .setPartitionIndex(topicPartition.partition())
                    .setCommittedOffset(offsetAndMetadata.offset())
                    .setCommittedLeaderEpoch(offsetAndMetadata.leaderEpoch().orElse(RecordBatch.NO_PARTITION_LEADER_EPOCH))
                    .setCommittedMetadata(offsetAndMetadata.metadata())
            );
            requestTopicDataMap.put(topicPartition.topic(), topic);
        }

        final Generation generation = generation();
            // if the generation is null, we are not part of an active group (and we expect to be).
            // the only thing we can do is fail the commit and let the user rejoin the group in poll()
            if (generation == null) {
                log.info("Failing OffsetCommit request since the consumer is not part of an active group");
                return RequestFuture.failure(new CommitFailedException());
            }

        OffsetCommitRequest.Builder builder = new OffsetCommitRequest.Builder(
                new OffsetCommitRequestData()
                        .setGroupId(this.groupId)
                        .setGenerationId(generation.generationId)
                        .setMemberId(generation.memberId)
                        .setGroupInstanceId(groupInstanceId.orElse(null))
                        .setTopics(new ArrayList<>(requestTopicDataMap.values()))
        );

        log.trace("Sending OffsetCommit request with {} to coordinator {}", offsets, coordinator);

        return client.send(coordinator, builder)
                .compose(new OffsetCommitResponseHandler(offsets));
    }

Losing data on rebooting primary in clustered mode

• If we reboot the primary, both primary and its read replica/slave’s data will be wiped
  • Reboot takes about 2 mins from start to primary health check passed again. Auto failover will not be triggered in this process
  • Note that if we deploy redis on EC2 directly, we can turn on AOF, so that on server reboot, all data upto the last fsync will be in memory. However, EC redis disabled AOF in cross-AZ mode and cannot be turned on! This suggests a risk of cache avalanche and stakeholders need to eval the risk/reward ratio
• If we reboot the read/replica, the primary data remains intact
• Promoting the replica to master will keep the data in the new master and old master intact

Scenario and goals

• Major refactoring of centralization of multiple payment history tables into one To act as OLTP and small OLAP bedrock for front line services
• 2k writes per sec. 1k reads with p99 < 2 sec
• Gain confidence for the critial path migration later on

Timeline

• June - PoC with load testing
• July - Dev starts
• Aug - Load testing with problems. DR drills
• Sep - Turn on incremental traffic switch
• Oct - 100% traffic switch

Major decision dilemmas/Known unknowns and how I solved them

• DB selection
  • PoCed vitess, tidb, cockroach db
  • Vitess has hugh operational problem even during PoC
  • Cockroach is feasible, but we are mysql based so favored tdib
• Hosting solution: EKS + operator or EC2 + Ansible
  • Ansible proved too much effort
  • Because we can do incremental traffic switch, it is OK we take risks with k8s operator, since it is the direction of the future
• Data transfer approach: direct between DBs or done by kafka
  • Kafka approach means we don’t need coordination logic
  • But our kafka pipeline implmentation uses the single row actions, which reduced speed by a large margin
  • Personal preference is between DBs, but the implmentation team prefers the kafka approach. In the end I approved the team’s decision
    • I have no way to prove the kafka approach won’t perform as well.
    • I didn’t force a PoC, because that would be implementing coordination logic regardless, which we all know it is not trivial
    • I trusted the team, which I didn’t work too much with in prior
    • In retro, I should have forced a PoC on the team’s preferred approach even against the timeline.

How did we migrate

• Based on big query, we know in effect data becomes immutable after 3 months. So we migration data up to T - 3 months first, and take a backup of that. This means our kafka pipeline needs to run at most 3 months data (in effect, a little over one month) every time we need to re-run
• A recon job that calcuates checksum between old and new architecture based on domain logics
• A new service powered by the tidb running in parallel with the old one. Openresty in from of the both to do traffic swtich

Setbacks/Unknown unknowns run into

• By late July, find that kafka pipeline performance is much lower than expected - only 2k writes per sec
• By late August, find that we had to scope down the project - one low traffic /big effort component is dropped
• Schema changed twice AFTER staging migration is completed. Each time it addes an extra week of delay
• First week in production, the cluster disappeared from all monitors for 10 minutes

(TODO: add how we solve such problems)