After learning about k-means clustering, I thought I understood it until I tried implementing it myself. That’s when I realized just how many details I had missed and how incomplete my theoretical understanding really was.

Implementing the core algorithm alone didn’t capture my interest. I wanted to see the algorithm’s results in action. Although I’ve spent over a decade building backend systems, there’s something satisfying about visual feedback. This led me to image compression.

While k-means clustering can be used to reduce image sizes by averaging similar colors, I’m aware there are more efficient algorithms for this purpose. However, for educational reasons, it’s an excellent way to see k-means in action.

Above is a comparison of an original image (left) and its compressed version (right), which uses only 16 colors and the Greedy K-means++ initialization method for k-means.

In the sections that follow, I’ll dive deeper into other initialization methods, their implementation, and their comparative effectiveness. But first, let’s explore the fundamental components of the k-means clustering.

Zig is a general-purpose, statically typed, compiled system programming language designed by Andrew Kelley back in 2016. It aims to succeed C by being simpler and smaller, yet more functional, making it an appealing choice for system-level programming.

The Mandelbrot set, on the other hand, is a complex fractal shape. It consists of points in the complex plane that remain within certain limits under repeated application of a simple mathematical formula.

Let’s explore Zig by building a program that plots the Mandelbrot set, as shown in the figure above. The task involves parsing command-line arguments, iterating over image pixels, coloring pixels based on their inclusion in the Mandelbrot set, writing the results into a PNG file, and enhancing rendering performance by leveraging Zig’s concurrency capabilities.

In the rapidly evolving world of technology, Machine Learning (ML) is a revolutionary force driving innovation across industries. From enhancing customer experiences to automating tedious tasks, ML’s impact is undeniable. Below is a Machine Learning mind map that illustrates the primary ML building blocks. This mind map is followed by a concise overview of the core concepts and techniques in Machine Learning, aiming to demystify this complex field.

The Leaky Bucket Rate Limiting algorithm utilizes a FIFO (First In, First Out) queue with a fixed capacity to manage request rates, ensuring that requests are processed at a constant rate regardless of traffic spikes. It contrasts with the Token Bucket algorithm by not allowing for bursty traffic allowances based on token accumulation but instead focusing strictly on maintaining a constant output rate. When the queue is full, incoming requests are denied until space becomes available. This approach effectively moderates the flow of requests, preventing server overload by maintaining a steady rate of processing, akin to a bucket leaking water at a fixed rate to avoid overflow.

The above diagram shows an algorithm with a rate limit of one request per second and a bucket capacity for two requests. Initially, when request A arrives, it is added to an empty queue and processed. With space for one more, request B is also added, filling the bucket to capacity. Request C is rejected because the bucket is full and hasn’t leaked yet. After one second, a leak removes request A, making room for request D. By the time request E arrives, the bucket is empty due to the leaks for requests B and D, allowing E to be accepted.

The Token Bucket Rate Limiting algorithm implements rate limiting by maintaining a fixed-capacity bucket that holds tokens. Tokens are added at a consistent rate, and their count never exceeds the bucket’s capacity. To process a request, the algorithm checks for sufficient tokens in the bucket, deducting the necessary amount for each request. If insufficient tokens are available, the request is rejected.

The above diagram illustrates the algorithm with a rate limit set to one request per second and a bucket capacity of two tokens. When request A arrives, the token bucket is initialized with one token, enabling request A to proceed successfully. Request B is rejected due to a lack of tokens in the bucket at that moment. Since no requests are made between the first and second seconds, the bucket accumulates two tokens. Consequently, requests C and D are allowed, with each consuming a token. Request E is rejected as the bucket has been run out of tokens.

The Sliding Window Rate Limiting is similar to the Fixed Window Rate Limiting but differs in its approach to managing the time window. Unlike the fixed time window, which is static, the sliding window moves continuously along the request timeline. It monitors requests within the current window, rejecting additional requests once the window’s limit is reached. As the window slides forward on the timeline, older requests that fall outside the window are discarded, creating space for new requests.

In the figure above, the rate limit is one request per two seconds. Request A is processed successfully. When Request B arrives, the window moves right, using B’s current time as the end of the rolling window, but B is rejected because it falls within the same two-second window as A. Request C, arriving later, is also throttled for including A within its window. Request D, however, arrives outside A’s two-second window and is thus processed successfully.

The Fixed Window Rate Limiting algorithm divides time into fixed windows of a specified duration, with each window having a predetermined request limit. Requests are counted against this limit, and once the maximum number of requests for a window is reached, additional requests are rejected until the next window starts. The request count is reset at the beginning of each new window.

In the figure above, the rate limit is set to one request per two seconds. The initial timeframe starts when request A arrives, bringing the request count to 1. Request B is dropped because it causes the request count to reach 2 within the current two-second window. Shortly after two seconds, request C arrives. This marks the start of a new window and resets the request count, allowing Request C to be processed. Request D is subsequently dropped for the same reason as Request B.

Rate limiting is a critical technique in system design that controls the flow of data between systems, preventing resource monopolization, and maintaining system availability and security.

At its core, rate limiting sets a threshold on how often a user or system can perform a specific action within a set timeframe. Examples include limiting login attempts, API requests, or chat messages to prevent abuse and overloading.

Sometimes, you realize that a common library is being used in a single project but resides in its own Git repository. At other times, you may decide to merge a few Git repositories into one to reduce maintenance issues. There are many other similar scenarios that involve moving a portion of one Git repository into another. A common problem that unites all these cases is how to preserve the Git history for the moved files.

The problem can be described as follows: given two Git repositories, source and target, the task is to move content from source to target, either wholly or partially, while preserving the Git change history.

What’s wrong with this Java code?

public class App {

    private static Repo repo;

    App(Repo repo) {
        this.repo = repo;
    }

    String greet(int id) {
        return repo.getGreeting(id);
    }
}

class Repo {

    String getGreeting(int id) {
        throw new UnsupportedOperationException("not implemented yet");
    }
}