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

Every Go program has a runtime. The runtime implements garbage collection, concurrency, stack management, and other critical features. We can configure the runtime by setting variables. In this post, we will look at GOMAXPROCS, a variable that configures concurrency. You may get free performance boost by setting …

Read More

We plan to load test our product before public Beta, with two goals in mind. Find out bottlenecks: figure out road maps of performance improvement and prepare for oncalls. Understand how much workload we can support with fixed resources. This shapes the pricing strategy and determines number of Beta partners to …

Read More

Given two sorted arrays of integers, $A$ and $B$, find the $K$-th smallest integer from A and B in $O(\min(\log{N}, \log{M}))$ time. $N$ and $M$ are the size of $A$ and $B$ respectively. Without loss of generality, we can assume A and B are of the same length N. Because both A and B are sorted, we can merge A and B …

Read More

I implemented a job scheduler at work recently. Each job has a unique ID and an expiration time. The job ID is immutable while the expiration time may change. The job scheduler schedules the job of the earliest expiration time. Go comes with heap.Interface and map. My first implementation uses a hashmap and a slice …

Read More