The Problem

Classic interview setup: you walk in, sit down, and the interviewer says:

“Design a FastQueue class. It stores entries, where each entry has a long id and a String family.

You need three operations, all in O(1) time: add(entry), removeLast(), and removeLast(family).

Space complexity is O(N) for all operations.”

Let’s unpack that. You have a queue of entries, each tagged with a family group. At any point, you can eject the oldest entry within a given family, all in constant-time.

JUnit: Lay of the Land & Mutation testing

Alright, what do we know about unit tests?

1. A unit test verifies an individual unit of code works as expected,
2. It is small, fast and isolate a single functionality

They are generally named based on what the test verifies, e.g. testInvalidAccountIdThrowsException; they are independent from each other even though grouped in the same class as related tests.

We create them in the same package structure as the source code but under the src/test/java directory. With Maven, tests can be run using lifecycle phases like test, install, etc.

Tiptoeing Through the Asynch Door with the CompletionStage Interface JSE17

When it comes to holidays, I’m as spontaneous as they come. I enjoy not planning and picking the best option available just before or even while traveling.

So I needed a holiday… and a reason to explore Java’s async magic.

We’ll get to this Holiday Finder but first let’s get the theory out of the way, shall we?

Diving Right In

Considering two API calls A & B, API A is called first, and then API B. This is what synchronous code does: it waits before executing the next task and things run in order. However, could the thread blocked on the API response be doing some other work instead?

Quick Tour of Java Functional Interfaces

A functional interface is an interface with just one abstract method, such as Runnable, Comparator, Callable, etc. The main benefit of functional interfaces, with the introduction of lambdas in Java 8, is that they allow you to pass behavior (code) to a function the same way you’d pass data (objects) to a method. This means we can pass a lambda expression when a method is accepting a functional interface. Since there is only one function to override, it is possible to infer which function to implement when using a lambda expression.

The Huffman’s Algorithm

The Huffman’s algorithm was born in 1952 as a way to perform a lossless compression on data files. Its efficiency comes from the frequency analysis of characters present in the text to encode: shorter codes are used to encode more frequent characters while longer codes are used to encore less frequent ones.

It constitutes the foundation of modern text compression.

You can read more on variable-length encoding and tree representations under the Design tag on this blog.

Encoding for Web apps internationalisation

Some theory about Information Content & Entropy

Encoding is the process of converting data from one form into another using an unambiguous mapping. It can refer to transforming human-readable characters into a machine-readable format. The main question it raises is: how many bits do I need to encode ‘a’ (and the rest of the characters)?

The Information Content (Shannon information) quantifies the amount of “uncertainty” associated with a particular piece of information.

Pass-by-Value or Reference: the Great Debate

Background on Heap and Stack

The stack referred to when talking about memory is the same as the run-time call stack. It is composed of stack frames and stores things. It controls the function calls and program execution by storing in its frames the function parameters, the return address, local variables - among other things. The stack has a fixed-size so in some cases, for instance deep recursion, it can run out of memory. Remember this one time you forgot a stopping condition in your code and got a StackOverflowError or RecursionError: that’s the call stack telling you it’s full. Stack frames only exist during the execution of a function. This means everything stored in it becomes unavailable after the function has returned. This makes the allocation and de-allocation of memory automatic, which helps prevent memory leaks.

Structured logging in Java for distributed systems

Where do applications log end up anyway?

Applications typically write to standard output. Logs can either be handled by the app’s supervising process or be passed to the next supervision layer to be processed. For example Kubernetes collects logs written to stdout and stderr by containers and stores them in node-specific log files (usually /var/log/containers based on name). From there, they can be accessed by tools like kubectl logs.

The Problem

Classic interview setup: you walk in, sit down, and the interviewer says:

“Design a FastQueue class. It stores entries, where each entry has a long id and a String family.

You need three operations, all in O(1) time: add(entry), removeLast(), and removeLast(family).

Space complexity is O(N) for all operations.”

Let’s unpack that. You have a queue of entries, each tagged with a family group. At any point, you can eject the oldest entry within a given family, all in constant-time.

JUnit: Lay of the Land & Mutation testing

Alright, what do we know about unit tests?

1. A unit test verifies an individual unit of code works as expected,
2. It is small, fast and isolate a single functionality

They are generally named based on what the test verifies, e.g. testInvalidAccountIdThrowsException; they are independent from each other even though grouped in the same class as related tests.

We create them in the same package structure as the source code but under the src/test/java directory. With Maven, tests can be run using lifecycle phases like test, install, etc.

Tiptoeing Through the Asynch Door with the CompletionStage Interface JSE17

When it comes to holidays, I’m as spontaneous as they come. I enjoy not planning and picking the best option available just before or even while traveling.

So I needed a holiday… and a reason to explore Java’s async magic.

We’ll get to this Holiday Finder but first let’s get the theory out of the way, shall we?

Diving Right In

Considering two API calls A & B, API A is called first, and then API B. This is what synchronous code does: it waits before executing the next task and things run in order. However, could the thread blocked on the API response be doing some other work instead?

Quick Tour of Java Functional Interfaces

A functional interface is an interface with just one abstract method, such as Runnable, Comparator, Callable, etc. The main benefit of functional interfaces, with the introduction of lambdas in Java 8, is that they allow you to pass behavior (code) to a function the same way you’d pass data (objects) to a method. This means we can pass a lambda expression when a method is accepting a functional interface. Since there is only one function to override, it is possible to infer which function to implement when using a lambda expression.

Encoding for Web apps internationalisation

Some theory about Information Content & Entropy

Encoding is the process of converting data from one form into another using an unambiguous mapping. It can refer to transforming human-readable characters into a machine-readable format. The main question it raises is: how many bits do I need to encode ‘a’ (and the rest of the characters)?

The Information Content (Shannon information) quantifies the amount of “uncertainty” associated with a particular piece of information.

Pass-by-Value or Reference: the Great Debate

Background on Heap and Stack

The stack referred to when talking about memory is the same as the run-time call stack. It is composed of stack frames and stores things. It controls the function calls and program execution by storing in its frames the function parameters, the return address, local variables - among other things. The stack has a fixed-size so in some cases, for instance deep recursion, it can run out of memory. Remember this one time you forgot a stopping condition in your code and got a StackOverflowError or RecursionError: that’s the call stack telling you it’s full. Stack frames only exist during the execution of a function. This means everything stored in it becomes unavailable after the function has returned. This makes the allocation and de-allocation of memory automatic, which helps prevent memory leaks.

Structured logging in Java for distributed systems

Where do applications log end up anyway?

Applications typically write to standard output. Logs can either be handled by the app’s supervising process or be passed to the next supervision layer to be processed. For example Kubernetes collects logs written to stdout and stderr by containers and stores them in node-specific log files (usually /var/log/containers based on name). From there, they can be accessed by tools like kubectl logs.

Discovery of Bron-Kerbosch in AoC24-23

For part 2 of this challenge, I am actually ashamed of showing here what I initially tried to program without knowing what a clique was, nor that an algorithm existed to find the maximal cliques in a graph… Maybe one day when I add a Premium Pass to this blog, a few privileged users could see the pépite.

Part 1 - the piece of 🍰

As The Historians wander around a secure area at Easter Bunny HQ, you come across posters for a LAN party scheduled for today! 
Maybe you can find it; you connect to a nearby datalink port and download a map of the local network (your puzzle input).

The network map provides a list of every connection between two computers. For example:
kh-tc
qp-kh
de-cg
ka-co
Each line of text in the network map represents a single connection; the line kh-tc represents a connection between the 
computer named kh and the computer named tc. Connections aren't directional; tc-kh would mean exactly the same thing.

LAN parties typically involve multiplayer games, so maybe you can locate it by finding groups of connected computers. 
Start by looking for sets of three computers where each computer in the set is connected to the other two computers.

If the Chief Historian is here, and he's at the LAN party, it would be best to know that right away. You're pretty 
sure his computer's name starts with t, so consider only sets of three computers where at least one computer's name 
starts with t. That narrows the list down to 7 sets of three inter-connected computers:
co,de,ta
co,ka,ta
de,ka,ta
qp,td,wh
tb,vc,wq
tc,td,wh
td,wh,yn
Find all the sets of three inter-connected computers. How many contain at least one computer with a name that starts 
with t?

Initial Thoughts

Setting the “starts with t” requirement aside, the list of computers given is a list of edges connecting two computers (nodes).

Typeahead System

A little background

An autocomplete system, also called typeahead, is a feature often experienced by users while typing in a search bar (or your IDE for that matter). The software suggests the rest of a word or word sequence based on what the user has already typed.

These suggestions can be ranked depending on how often/popular a search is. Remember that gorgeous Versace dress J-Lo wore for the Grammy Awards back in 2000? Everyone googled it - in fact it became the most popular search query at the time and - fun fact - prompted Google engineers to develop the image search! The objective is to make user searches more efficient and reduce the amount of typing required, while keeping the suggestions relevant with current search trends.

The Huffman’s Algorithm

The Huffman’s algorithm was born in 1952 as a way to perform a lossless compression on data files. Its efficiency comes from the frequency analysis of characters present in the text to encode: shorter codes are used to encode more frequent characters while longer codes are used to encore less frequent ones.

It constitutes the foundation of modern text compression.

You can read more on variable-length encoding and tree representations under the Design tag on this blog.

LC23 - Merge k Sorted Lists

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

Smelling like merge sort in the air?

We know each list is already in sorted order. Does it remind us of the merge step from a classic merge-sort algorithm?

The Bucket Sort algorithm

LC75 - example of Sorting Colors

The problem statement is as below.

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color 
are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # bucket sort 
        value_range = 3 #red, white or blue
        counts = [0] * value_range

        for i, n in enumerate(nums):
            counts[n] += 1

        i = 0
        for value, freq in enumerate(counts):
            print(value, freq)  
            for _ in range(freq):
                nums[i] = value
                i += 1

Quick rundown

The bucket sort algorithm relies on the fact that values belong to a known range. In this example it is [0,2] ∈ Z. The input arrays have already been prepared, by encoding categorical values into numerical ones. The same thing could be said about a different numerical range where the start of range is re-indexed or shifted back to 0.

LC765 - Couples holding hands

Problem Statement

There are n couples sitting in 2n seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. 
The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), 
and so on with the last couple being (2n - 2, 2n - 1).

Return the minimum number of swaps so that every couple is sitting side by side. 
A swap consists of choosing any two people, then they stand up and switch seats.

Initial solution

The below solution provides an O(n) time complexity and memory. Relatively simply, checking for every pair of people, if the left-hand side person is not seated next to its beloved, then we swap the right person next to them.

Who said AoC25-11 should be complicated?

The Challenge

The ancient civilization on Pluto created stones that change every time you blink. Each stone follows specific transformation rules:
- A stone marked 0 becomes 1.
- A stone with an even number of digits splits into two stones, each half of the original number.
- Any other stone is replaced by a new one, with its number multiplied by 2024.
The stones remain in order, and their transformations continue with each blink. For example, the sequence [0, 1, 10, 99, 999] would change to [1, 2024, 1, 0, 9, 9, 2021976] after one blink.
Part 1: blink 25 times. Part 2: blink 75 times.

Full description available here.

Discovery of Bron-Kerbosch in AoC24-23

For part 2 of this challenge, I am actually ashamed of showing here what I initially tried to program without knowing what a clique was, nor that an algorithm existed to find the maximal cliques in a graph… Maybe one day when I add a Premium Pass to this blog, a few privileged users could see the pépite.

Part 1 - the piece of 🍰

As The Historians wander around a secure area at Easter Bunny HQ, you come across posters for a LAN party scheduled for today! 
Maybe you can find it; you connect to a nearby datalink port and download a map of the local network (your puzzle input).

The network map provides a list of every connection between two computers. For example:
kh-tc
qp-kh
de-cg
ka-co
Each line of text in the network map represents a single connection; the line kh-tc represents a connection between the 
computer named kh and the computer named tc. Connections aren't directional; tc-kh would mean exactly the same thing.

LAN parties typically involve multiplayer games, so maybe you can locate it by finding groups of connected computers. 
Start by looking for sets of three computers where each computer in the set is connected to the other two computers.

If the Chief Historian is here, and he's at the LAN party, it would be best to know that right away. You're pretty 
sure his computer's name starts with t, so consider only sets of three computers where at least one computer's name 
starts with t. That narrows the list down to 7 sets of three inter-connected computers:
co,de,ta
co,ka,ta
de,ka,ta
qp,td,wh
tb,vc,wq
tc,td,wh
td,wh,yn
Find all the sets of three inter-connected computers. How many contain at least one computer with a name that starts 
with t?

Initial Thoughts

Setting the “starts with t” requirement aside, the list of computers given is a list of edges connecting two computers (nodes).

Your survival guide to feathered philosophies in software development

Rubber Duck Debugging

Alright, we’re starting easy and light for this one.

It was popularised by the Pragmatic Programmer written by Andrew Hunt and David Thomas (an alumnus of Imperial College London). The idea is rather simple: instead of spending hours trying to debug something obscure, explain the code line-by-line to an inanimate object - a rubber duck named Chucky maybe? - to help you work out what the problem is.

Typeahead System

A little background

An autocomplete system, also called typeahead, is a feature often experienced by users while typing in a search bar (or your IDE for that matter). The software suggests the rest of a word or word sequence based on what the user has already typed.

These suggestions can be ranked depending on how often/popular a search is. Remember that gorgeous Versace dress J-Lo wore for the Grammy Awards back in 2000? Everyone googled it - in fact it became the most popular search query at the time and - fun fact - prompted Google engineers to develop the image search! The objective is to make user searches more efficient and reduce the amount of typing required, while keeping the suggestions relevant with current search trends.

The Huffman’s Algorithm

The Huffman’s algorithm was born in 1952 as a way to perform a lossless compression on data files. Its efficiency comes from the frequency analysis of characters present in the text to encode: shorter codes are used to encode more frequent characters while longer codes are used to encore less frequent ones.

It constitutes the foundation of modern text compression.

You can read more on variable-length encoding and tree representations under the Design tag on this blog.

Pass-by-Value or Reference: the Great Debate

Background on Heap and Stack

The stack referred to when talking about memory is the same as the run-time call stack. It is composed of stack frames and stores things. It controls the function calls and program execution by storing in its frames the function parameters, the return address, local variables - among other things. The stack has a fixed-size so in some cases, for instance deep recursion, it can run out of memory. Remember this one time you forgot a stopping condition in your code and got a StackOverflowError or RecursionError: that’s the call stack telling you it’s full. Stack frames only exist during the execution of a function. This means everything stored in it becomes unavailable after the function has returned. This makes the allocation and de-allocation of memory automatic, which helps prevent memory leaks.

LC23 - Merge k Sorted Lists

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

Smelling like merge sort in the air?

We know each list is already in sorted order. Does it remind us of the merge step from a classic merge-sort algorithm?

The Bucket Sort algorithm

LC75 - example of Sorting Colors

The problem statement is as below.

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color 
are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # bucket sort 
        value_range = 3 #red, white or blue
        counts = [0] * value_range

        for i, n in enumerate(nums):
            counts[n] += 1

        i = 0
        for value, freq in enumerate(counts):
            print(value, freq)  
            for _ in range(freq):
                nums[i] = value
                i += 1

Quick rundown

The bucket sort algorithm relies on the fact that values belong to a known range. In this example it is [0,2] ∈ Z. The input arrays have already been prepared, by encoding categorical values into numerical ones. The same thing could be said about a different numerical range where the start of range is re-indexed or shifted back to 0.

LC765 - Couples holding hands

Problem Statement

There are n couples sitting in 2n seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. 
The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), 
and so on with the last couple being (2n - 2, 2n - 1).

Return the minimum number of swaps so that every couple is sitting side by side. 
A swap consists of choosing any two people, then they stand up and switch seats.

Initial solution

The below solution provides an O(n) time complexity and memory. Relatively simply, checking for every pair of people, if the left-hand side person is not seated next to its beloved, then we swap the right person next to them.

Who said AoC25-11 should be complicated?

The Challenge

The ancient civilization on Pluto created stones that change every time you blink. Each stone follows specific transformation rules:
- A stone marked 0 becomes 1.
- A stone with an even number of digits splits into two stones, each half of the original number.
- Any other stone is replaced by a new one, with its number multiplied by 2024.
The stones remain in order, and their transformations continue with each blink. For example, the sequence [0, 1, 10, 99, 999] would change to [1, 2024, 1, 0, 9, 9, 2021976] after one blink.
Part 1: blink 25 times. Part 2: blink 75 times.

Full description available here.

Your survival guide to feathered philosophies in software development

Rubber Duck Debugging

Alright, we’re starting easy and light for this one.

It was popularised by the Pragmatic Programmer written by Andrew Hunt and David Thomas (an alumnus of Imperial College London). The idea is rather simple: instead of spending hours trying to debug something obscure, explain the code line-by-line to an inanimate object - a rubber duck named Chucky maybe? - to help you work out what the problem is.

Domain Name System: traffic distribution on a budget

It’s not magic

What happens when you type leane.dev in your browser?

As a regular reader of this blog, I am allowing myself to take your everyday example.

You want to access the server hosting this blog, but how do you reach it? On the Internet, routing is done by finding the path to a given Internet Protocol - IP. Thing is: you don’t know my IP, not directly. It’s easier to remember the hostname: leane.dev. Yet, the browser manages to display the blog to you.

Typeahead System

A little background

An autocomplete system, also called typeahead, is a feature often experienced by users while typing in a search bar (or your IDE for that matter). The software suggests the rest of a word or word sequence based on what the user has already typed.

These suggestions can be ranked depending on how often/popular a search is. Remember that gorgeous Versace dress J-Lo wore for the Grammy Awards back in 2000? Everyone googled it - in fact it became the most popular search query at the time and - fun fact - prompted Google engineers to develop the image search! The objective is to make user searches more efficient and reduce the amount of typing required, while keeping the suggestions relevant with current search trends.

Encoding for Web apps internationalisation

Some theory about Information Content & Entropy

Encoding is the process of converting data from one form into another using an unambiguous mapping. It can refer to transforming human-readable characters into a machine-readable format. The main question it raises is: how many bits do I need to encode ‘a’ (and the rest of the characters)?

The Information Content (Shannon information) quantifies the amount of “uncertainty” associated with a particular piece of information.

Domain Name System: traffic distribution on a budget

It’s not magic

What happens when you type leane.dev in your browser?

As a regular reader of this blog, I am allowing myself to take your everyday example.

You want to access the server hosting this blog, but how do you reach it? On the Internet, routing is done by finding the path to a given Internet Protocol - IP. Thing is: you don’t know my IP, not directly. It’s easier to remember the hostname: leane.dev. Yet, the browser manages to display the blog to you.

Kubernetes cert-manager for LetsEncrypt certificates

Digital Certificates raison d’être and usage

Certificates are exchanged as part of the TLS handshake. This allows the client to ensure the entity it is trying to establish a connection with is authentically the genuine server.

Note: see other posts under this tag for a few words on TLS handshakes and mentions of the attacks it protects against.

A certificate contains: the issuer details, its expiration date, the entity’s public key for asymmetric encryption and a signature (encrypted server’s public key).

The fast alternative to TCP+TLS

What is QUIC?

The Quick UDP Internet Connection (QUIC) protocol is an encrypted connection protocol operating on the Layer 4 - Transport Layer of the OSI model.

Developed at Google around 2012, it has only been adopted as a standard by IETF in 2021.

The current and widely used solution of HTTPS using TLS is built is on top of the TCP protocol. The TCP handshake and the TLS handshake need to be completed to establish a path to communicate between a server and a client. As a result, multiple rounds trips to initiate a connection and negotiate the encryption parameters are required - two at the very least, depending on the TLS version used.

A brief overview of HSTS protocol or why I chose the .dev domain

Quick intro

What happens when you’re back from a family weekend in a cabin in the woods with no internet?

I’d probably check my dog’s instagram account first. On the browser: instagram.com and … my browser is making a call to http://instagram.com

Exactly! I haven’t explicitly used https, so where does this leave me? Exposed to all sorts of man-in-the-middle attacks that wikipedia can list for us in a scary way - session hijacking, protocol downgrade attack, etc.

Automated Vulnerability Scanning for Dependencies & Packages

Do we need to explain why?

🔥💥💣🚨⚡☠️🧨

That’s what I thought.

Configure your pipeline with Snyk

There is a plethora of tools available out there for security scans and/or vulnerable dependencies - Dependabot, Trivy, sonarQube/Lint, Anchore, etc. Most of which can be integrated into your IDE or CI/CD.

For this use case, Snyk has been selected. Snyk is able to scan code, open-source dependencies, container images, and infrastructure as code configurations to helps developers prioritize and fix security vulnerabilities. The free version comes with a max limit scans per month.

Kubernetes cert-manager for LetsEncrypt certificates

Digital Certificates raison d’être and usage

Certificates are exchanged as part of the TLS handshake. This allows the client to ensure the entity it is trying to establish a connection with is authentically the genuine server.

Note: see other posts under this tag for a few words on TLS handshakes and mentions of the attacks it protects against.

A certificate contains: the issuer details, its expiration date, the entity’s public key for asymmetric encryption and a signature (encrypted server’s public key).

Automated Vulnerability Scanning for Dependencies & Packages

Do we need to explain why?

🔥💥💣🚨⚡☠️🧨

That’s what I thought.

Configure your pipeline with Snyk

There is a plethora of tools available out there for security scans and/or vulnerable dependencies - Dependabot, Trivy, sonarQube/Lint, Anchore, etc. Most of which can be integrated into your IDE or CI/CD.

For this use case, Snyk has been selected. Snyk is able to scan code, open-source dependencies, container images, and infrastructure as code configurations to helps developers prioritize and fix security vulnerabilities. The free version comes with a max limit scans per month.

Kubernetes cert-manager for LetsEncrypt certificates

Digital Certificates raison d’être and usage

Certificates are exchanged as part of the TLS handshake. This allows the client to ensure the entity it is trying to establish a connection with is authentically the genuine server.

Note: see other posts under this tag for a few words on TLS handshakes and mentions of the attacks it protects against.

A certificate contains: the issuer details, its expiration date, the entity’s public key for asymmetric encryption and a signature (encrypted server’s public key).

The fast alternative to TCP+TLS

What is QUIC?

The Quick UDP Internet Connection (QUIC) protocol is an encrypted connection protocol operating on the Layer 4 - Transport Layer of the OSI model.

Developed at Google around 2012, it has only been adopted as a standard by IETF in 2021.

The current and widely used solution of HTTPS using TLS is built is on top of the TCP protocol. The TCP handshake and the TLS handshake need to be completed to establish a path to communicate between a server and a client. As a result, multiple rounds trips to initiate a connection and negotiate the encryption parameters are required - two at the very least, depending on the TLS version used.

A brief overview of HSTS protocol or why I chose the .dev domain

Quick intro

What happens when you’re back from a family weekend in a cabin in the woods with no internet?

I’d probably check my dog’s instagram account first. On the browser: instagram.com and … my browser is making a call to http://instagram.com

Exactly! I haven’t explicitly used https, so where does this leave me? Exposed to all sorts of man-in-the-middle attacks that wikipedia can list for us in a scary way - session hijacking, protocol downgrade attack, etc.