# Category Archives: Computer science

## IPv6

IPv6 has been an Internet Standard since July 2017. Although I had heard of it since far back, I never had to know much about it until now. In this post I’m going to explain what are some of the differences between IPv4 (The previous and most widely used standard) and IPv6.

Probably the most commonly known reason behind IPv6 is that we were going to run out of IPv4 addresses soon. An IPv4 address looks like this: 192.168.100.255. In binary it would look something like this: 11000000.10101000.1100100.11111111. That is 32 bits (2^32) which equals 4,294,967,296 values.

IPv6 addresses look a little different. They are represented by 8 groups of 4 hexadecimal digits separated by a colon. For example: 1234:5678:9abc:def1:f00d:1560:0d7a:c055. This is 2^128 different combinations which is a little more than 3*10^38. This is a very high number we’re probably not going to exhaust any time soon.

Because addresses can get very long, a few conventions have been made to make them shorter to write on paper. One of them is that leading zeros in a group can be omitted. For example:

 12 1234:0abc:9abc:00f1:f00d:1560:0035:0001 1234:abc:9abc:f1:f00d:1560:35:1

The two addresses above are the same.

## 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

## 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.

## 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.

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).

## 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:

 123456789101112131415161718192021222324 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

## 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.

## 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:

 1234 0         1       1 +0        +0      +1 ---       ---     ---  0         1      10

## 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:

 12345678910 ABC BC C B AC C A AB B A

## 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)

## 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?

 1234567 +---+---+---+---+---+---+---+ | 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: