Category Archives: Computer science

Sorting algorithms

This is a refresher of sorting algorithms since I recently realized that I don’t remember how a lot of the most common sorting algorithms work. I’m only going to focus on arrays on this article since it is the most common structure for these kind of problems.

Bubble sort

This is the first algorithm we learn at school. It is not very efficient(O(n ^ 2) in most of the cases) but it is pretty easy to implement.

  • Grab the first two elements(0 and 1) in an array and compare them
  • If the element in the left is higher than the elements in the right then swap them
  • Grab the next two elements(1 and 2) and do the same
  • Repeat until the greatest element is in the far right
  • Do the same starting from the first two elements(0 and 1) but ending before reaching the last element(which is already sorted)
  • At the end the array will be sorted

Read more »

Stack and heap memory in C++

Since I’ve been working in C++, I’ve noticed the necessity to get familiar with concepts about computer architecture and how the operating system works. One thing that has been bothering me for a few weeks is hearing people talk about the heap and stack memory, while I don’t really know what those things mean.

I decided to write this post to try to explain to myself what is the difference between stack memory and heap memory and hopefully understand why people keep talking about them.

The names

Stack and Heap are both names of data structures. This can lead to some confusion, because although the stack is called like that because it works similar to a stack (I’ll explain more about this), the heap is not related at all to the heap data structure. The exact origin of the heap word in this context is unknown to me, but from a little research it seems like it’s use is based on the English language definition for that word:

1
An untidy collection of things piled up haphazardly

Which actually describes pretty well what a heap of memory is.

Read more »

Raft for reaching consensus

In a past post I wrote about distributed systems, but I intentionally omitted the subject of leaderless replication since I consider it a topic that deserves a little more focus.

In this post I’m going to explore how a leaderless system works and explain a little about how the Raft algorithm helps us achieve consensus.

Leaderless replication

As the name suggests, there are no leaders (or masters) in a leaderless setup. In this configuration all instances can receive reads and writes. If you read my previous post, you might be thinking that this sounds like master-master replication, but it is actually very different.

I mentioned two main problems in a master-master setup: Replication lag when you write to one master and then read from the other, and conflicts when you modify the same record in both masters and they try to sync. Leaderless replication doesn’t have these problems (it has others that I’ll explore soon). On top of not having those problems, a leaderless system can stay up even when instances are down (like the master-master configuration).

Read more »

The Rabin-Karp algorithm

I was doing a little studying on algorithms when I stumbled into what looked to me as a pretty simple question: “Find the first occurrence of a string inside another string”. This can be simply achieved with two nested loops and a worst case scenario performance of O(nm) or O(n^2) if m’s size is relative to n.

Here is an implementation that uses two loops:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function findString(s1, s2) {
  // We only need to loop until s2 doesn't fit anymore
  var loopLimit = s1.length - s2.length;
  for (var i = 0; i < = loopLimit; i++) {
    for (var j = 0; j < s2.length; j++) {
      // As soon as we find a mismatch we abort the loop
      if (s1[i + j] !== s2[j]) {
        break;
      }
    }

    // If j reached the size of s2, it means all letters
    // in s2 matched. We have succeeded!
    if (j === s2.length) {
      return true;
    }
  }

  return false;
}

findString('aaaaaaaaaa', 'aaaab'); // false
findString('aaaaaaaaab', 'aaaab'); // true
findString('aaaaaaaaab', 'ab'); // true

Read more »

House painting problem

The question

There are a row of houses, each house can be painted with one of three colors red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?

Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.

Read more »

Add one to a number without using plus or minus sign

I got asked this question in a code interview and I wanted to make sure my answer was good. Without the pressure of being in an interview I see the problem more clearly and the problem seems pretty easy now.

Lets look at the basics of adding in binary:

1
2
3
4
 0         1       1
+0        +0      +1
---       ---     ---
 0         1      10

Read more »

Maximum length palindromic subsequence

Given a sequence of characters, find the longest palindromic sub-sequence. A sub-sequence is any sequence that can be formed by removing 0 or more characters from the given sequence. For example, the possible sub-sequences for ABC are:

1
2
3
4
5
6
7
8
9
10
ABC
BC
C
B
AC
C
A
AB
B
A

Read more »

The Fibonacci sequence

The Fibonacci sequence is a sequence of numbers starting with 0 and 1 and then adding the sum of the two last numbers at the end of the sequence:

1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The mathematical representation of the Fibonacci sequence is:

1
F(n) = F(n-1) + F(n-2)

Read more »

Unique paths

A robot is located at the top-left corner of a m x n grid (marked ā€˜Sā€™ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ā€˜Fā€™ in the diagram below). How many possible unique paths are there?

1
2
3
4
5
6
7
+---+---+---+---+---+---+---+
| S |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
|   |   |   |   |   |   | F |
+---+---+---+---+---+---+---+

The first idea that came to my mind after seeing this problem was to find all the combinations for two movements down and six movements to the right(>>>>>>vv). I couldn’t remember of the top of my head the formula but after a little playing with pen and paper it came back to me. The formula is:

Read more »

Binary search

I was just going through the basics and I wanted to verify that I still knew how to do a binary search. If I remember correctly these are the steps:

– Set a left pointer at the beginning of the sorted array
– Set a right pointer at the end of the sorted array
– Calculate the middle between those two pointers(If there is no exact middle, truncate the number) and set the a middle pointer there
– Check if the middle is the number you are looking for. If it is return
– If the element at middle is greater than the element you are looking for set the left pointer to middle + 1
– If the element at middle is lower than the element you are looking for set the right pointer to middle – 1
– Repeat until the number is found or left is greater than right (not found)

Read more »