I often find myself confused by "upstream" and "downstream", in the context of software development. They bother me so much that I avoid using them in my own writing and I have to pause whenever I see them. In this post, I'll show a simple rule that helps you remember the difference: downstream adds …

Read More

Modern CPUs operate significantly faster than memories. A 4.5 GHz x64 CPU operates 30 times faster than a 6000 MHz DDR5 memory of CAS Latency 36. Adding latencies incurred by the bus and memory coherency protocols, memory could be 100 times slower than registers. To mitigate the speed gap, CPU uses layers of caches, …

Read More

Given a non-decreasing array and a target value, we can find the target in logarithmic time using binary search. My first programming language is C++ and the C++ Standard Template Library (STL) provides two functions for this task. iterator lower_bound(first, last, value) returns the smallest index with a value larger …

Read More

Problem Given an integer array A, in one step, remove all elements A[i] where A[i-1] > A[i]. Return the number of steps performed until A becomes a non-decreasing array. See examples at LeetCode 2289. Solution The naive approach executes steps one by one. Store integers in a Linked List. At each step, find all …

Read More

Problem In a connected network consisting of N nodes, each node is connected to either one or two neighbors, forming a line topology. The task is to develop a program that runs on each node, calculating the total number of nodes in the network. Each node is aware of its neighboring nodes and can exchange messages with …

Read More

Problem An event consists of multiple properties, each defined as a key-value pair, where the key is a string and the value is of a primitive type such as numbers or strings. Importantly, each event must include a mandatory 'Name' property. Given a list of events, the task is to count the number of events based on …

Read More

ClickHouse is a popular OLAP database. It speaks SQL and earns the reputation of "fast and resource efficient". But the support of SQL comes with surprises if not careful. In this blog, I show that a simple query of nested WITH clauses in ClickHouse generates factorial number of subqueries. The simple query …

Read More

In distributed systems, because there are too many requests to be handled by a single server reliably, requests are handled by a cluster of servers. In order to get high availability, the technique of distributing requests to servers needs to satisfy the following three requirements. Even distribution. Each backend …

Read More

A function is monotonic if it preserves the order of its arguments, i.e., if $x \le y$, then $f(x) \le f(y) $. In this post, we look at a class of problems where the argument is an interval. By identifying monotonic functions, we can reduce number of intervals to enumerate by an order of magnitude, from $O(n^2)$ to …

Read More

Given an array of numbers $A$, for each number $A[i]$, find the largest subarray that contains $A[i]$ and $A[i]$ is the minimum of the subarray. For example, for $A=[2, 0, 3, 5, 1, 1, 0, 2 1]$, the largest subarray for $A[4]$ is $[3,5,1,1]$. Let's represent the subarray for $A[i]$ as the left boundary $l[i]$ and right …

Read More