YouChen's Blog

In the previous article, we introduced Structural patterns. Structural patterns focus on how objects and modules are composed. This article focuses on Behavioral patterns. According to Refactoring.Guru, behavioral patterns focus on algorithms and responsibility assignment between objects. In other words, behavioral patterns help us answer this question: How should objects communicate, delegate work, and change behavior without making the code too tightly coupled? Why behavioral patterns mat...

In the previous article, we introduced Creational patterns. Creational patterns focus on object creation: where objects are created, which concrete implementation should be used, and how to avoid coupling callers to construction details. This article focuses on Structural patterns. According to Refactoring.Guru, structural patterns explain how to assemble objects and classes into larger structures while keeping those structures flexible and efficient. In other words, structural patterns help ...

In the previous summary, we introduced design patterns as reusable solution for repeated software design problems. Before using design patterns in our own system, we should first understand the common categories. Refactoring.Guru groups design patterns into three major types: Creational patterns: focus on how objects are created. Structural patterns: focus on how classes and objects are composed into larger structures. Behavioral pattern: focus on how objects communicate and share responsibi...

Synchronization is how concurrent programs coordinate independent work. In Rust, the type system prevents many unsafe data races, but an application still needs clear rules for shared state, message passing, task wakeups, and concurrency limits. In Tokio, synchronization usually means coordinating asynchronous tasks. A task may run on the same OS thread as another task, or it may move between worker threads. Because of that, Tokio provides async-aware primitives in tokio::sync [1]. They look ...

Wikipedia introduces software design patterns this way: A software design pattern describes a reusable solution to a commonly needed behavior in software. A design pattern is not a rigid structure to be copied directly into source code. Rather, it is a description of and a template for solving a particular type of problem that can be used in many different contexts. From this definition, the key point is that a design pattern helps solve problems that appear repeatedly in software engineeri...

230. Kth Smallest Element in a BSTProblem DescriptionGiven the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. IntuitionBinary TreeIn BST, all nodes in the left subtree are smaller than the root. So if the left subtree has L nodes, the root is the (L+1)th smallest. We can use this to decide whether to go left, return current, or go right.inorderIn BST, an inorder traversal visits nodes in sorted order, so th...

Lowest Common Ancestor of a Binary Search TreeProblem DescriptionGiven a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” IntuitionSince tree is BST, we know every left child is strictly less than root value, and eve...

Minimum Window SubstringProblem DescriptionGiven two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique. IntuitionWe need to find the shortest substring of s that contains all characters from t. Store the character frequencies of t in a hash map...

Product of Array Except SelfProblem DescriptionGiven an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in $O(n)$ time and without using the division operation. IntuitionSince product[i] should be the product of all numbers except nums[i], we could break it down into two parts left[i] and ...

Validate Binary Search TreeProblem DescriptionGiven the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node’s key. The right subtree of a node contains only nodes with keys strictly greater than the node’s key. Both the left and right subtrees must also be binary search trees. IntuitionBased on the BST definition, we could set min and max as the val...