Category Archives: Application Design

Introduction to networking in Google Cloud

Google uses the concept of Virtual Private Cloud (VPC) to refer to their capability for creating your own private network withing their infrastructure. There are a few terms that will allow us to create a network of our design:

  • Network – This is a virtual (because everything is virtual in the cloud) network that can span across the globe
  • Subnet – This is an IP range that can be used by machines in a single region
  • Firewall – Used to limit communication between machines in the same network

Network

A network (or VPC) is just a name used to group your network infrastructure. Subnets are defined inside a network and each host is part of one subnet.

Subnets

Subnets can be defined by region. You can choose any IP range defined as private as specified in RFC-1918 (basically anything inside these ranges: 10.0.0.0 – 10.255.255.255, 172.16.0.0 – 172.31.255.255 and 192.168.0.0 – 192.168.255.255).

Read more »

Distributed systems

In computer science a distributed system is a software system in which different parts of it communicate by passing messages through a network. The different parts could be running in the same machine or distributed across the globe; as long as they communicate through an unreliable channel (a network), we can classify them as distributed and consider the challenges that come with it.

With this definition in mind, we could think about many examples of distributed systems. A single monolithic application communicating with a database could be considered a distributed system if the application communicates through a network protocol.

Although in practice, local networks can be pretty reliable, they are still vulnerable. There are two condition that can cause a plethora of problems to a system: the network being down or the network being slow. These two conditions can put the system in a wide variety of states that may give results we don’t expect.

Before we look at how these problems can affect a distributed system, lets look at a distributed system whose failure mode is mostly understood and accepted to this date: a stateless system.

Read more »

Load testing a Rails app with Vegeta

I’m building a very simple app using Rails. While looking for guidance for preparing it for production, I found a lot of articles suggesting to put Nginx in front of it. After talking to some people they explained some reasons why this is suggested:

  • Ngingx can serve static assets – This appears to be the greatest and clearer advantage. You can configure Ngingx to directly serve static assets without having to hit Rails at all. This is very good because every request that comes to Rails will block all other request because Ruby is single threaded
  • Nginx can do caching for you – Nginx can cache some of the static assets, which would give them a performance boost
  • Nginx is multithreaded – Nginx can serve multiple static assets at the same time Rails is serving requests

These are definitely advantages (specially the first one), but having Nginx in front of my server also adds complexity to my deployment. To figure out if the added complexity worth it, I decided to run some load tests. Here I will explain how I did it and what were the results.

Read more »

OAuth2

Oauth2 is an authentication method where you allow clients to access resources in a server by authenticating in a different server. I am building a system where I will need this infrastructure so I will do my best to explain how to build and use an Oauth2 server.

The components

  • Resource owner: This is a person. Lets call him Adrian
  • Resource server: This is a server where Adrian’s information lives (along with other people’s information). The resource server needs to show Adrian only his information. We’ll call this app server
  • Client: This can be a browser or an app that Adrian uses to interact with the app server. This is the browser
  • Authorization server: This is our Oauth server. It validates user credentials and assigns tokens among other things. We’ll call this one oauth server

Read more »

UUIDs

UUID stands for Universally Unique ID. It is a 128-bit value that is usually represented by hexadecimal characters divided by dashes:

1
b54c9b1a-e19c-44e7-ab81-9528c195da02

They are called Universally Unique because in practice it is very hard to have collisions even if two(or more) independent systems generate these IDs independently. It is of course possible to have collisions, but the chances of it are low enough that it can be treated as impossible in most scenarios.

Read more »

Median of Integer Stream

The question

Given a stream of unsorted integers, find the median element in sorted order at any given time. So, we will be receiving a continuous stream of numbers in some random order and we don’t know the stream length in advance. Write a function that finds the median of the already received numbers efficiently at any time. We will be asked to find the median multiple times. Just to recall, median is the middle element in an odd length sorted array, and in the even case it’s the average of the middle elements.

Read more »

Kth Largest Element in Array

The question

Given an array of integers find the kth element in the sorted order (not the kth distinct element). So, if the array is [3, 1, 2, 1, 4] and k is 3 then the result is 2, because it’s the 3rd element in sorted order (but the 3rd distinct element is 3).

My solution

This doesn’t sound as a very hard problem but I couldn’t find a solution better than:

– Sort using quicksort
– Return the element at index k

The complexity of this solution is the complexity of quicksort O(nlogn).

Read more »

Convert Array

The question

Given an array [a1, a2, …, aN, b1, b2, …, bN, c1, c2, …, cN] convert it to [a1, b1, c1, a2, b2, c2, …, aN, bN, cN] in-place using constant extra space

My solution

At first this question felt a little confusing so lets clear a few things.
– There will only be a, b and c
– The size of the array is going to be N*3
– The problem needs to be solved without creating an extra array so the modifications need to be made in the same array

Read more »

Algorithm to check if a word is a palindrome

The question

Given a word, verify if it is a palindrome excluding spaces and punctuation.

The solution

This is the algorithm I came up to find out if a word is a palindrome:

– Place a pointer(left) on the first character
– Place a pointer(right) on the last character
– Check if the element at left is a character (not punctuation or space)
– If the element is not a character move the pointer one space to the right until you find a character
– Check if the element at right is a character
– If the element is not a character move the pointer one space to the left
– If left is greater than right return true
– Check if left and right elements are the same
– If they are not the same return false
– If they are the same move left one space to the right and right one space to the left
– Start over from step three

Read more »

Binary Search Tree Check

The question

Given a binary tree, check whether it’s a binary search tree or not.

My solution

I cheated a little in this question because I didn’t remember what a binary search tree is. After checking wikipedia I found the characteristic of a BST:

– The left subtree of a node contains only nodes with keys less than the node’s key.
– The right subtree of a node contains only nodes with keys greater than the node’s key.
– The left and right subtree each must also be a binary search tree.
– Each node can have up to two successor nodes.
– There must be no duplicate nodes.

Read more »