Joao Junior

I was verifying the performance of an endpoint in an API using framegraph when I noticed that checking if an object is in a set or a hash data structure was consuming a lot of time. This post explains the problem and the solution to it.

First of all, checking if an object is in a Set or HashMap is O(1) when we don’t consider collisions. Even in the presence of collisions, it should be much less than O(n), where n is the number of items in the set. Otherwise, we are operating as a linked list.

First things first, this is a classic book by Tom DeMarco and Timothy Lister that everyone working in the software industry must read.

The third edition divides this book into 6 parts with 39 chapters and 249 pages. It is an easy book to read and follow. However, it is necessary to stop constantly to reflect on the facts and ideas presented. Also, the reading would be like a map of the industry if you had a lot of experience in the software development industry. By this, I would like to say that many, maybe all, of the ideas presented in the book are implemented in all software-based companies I have seen.

When we study transactions in relational databases, one of the first things we learn are the guarantees that a transaction must provide. ACID(Atomicity, Consistency, Isolation, Durability) are the properties that we desire. Here, I will discuss the Isolation level in more detail and show that atomicity alone is not enough when handling concurrency.

One classic example of the importance of atomicity is moving money between accounts. So, imagine that we have two accounts and we would like to transfer the total amount from one account to another one. In a relational database, what we need to do is three steps:

The Quicksort algorithm was created by Tony Hoare in 1961 and it is a very powerful algorithm to sort an array in memory until today. Here, I will describe the Quicksort algorithm, show an implementation in Python, and analyze the time complexity of this algorithm in the worst and best scenarios.

The idea behind the Quicksort is so simple: to sort an array \(V\) of \(n\) elements, it is easier to sort smaller sub-arrays of \(V\). We can think of this approach as divide-and-conquer, where we break a problem into smaller sub-problems and combine their solutions to form the solution to the original problem.