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

See command history

When I want to find a command I used in the past, but I don’t remember I usually use vim to search for it:

1
vim ~/.bash_history

This is useful because you get the whole list of commands in your history and all the power of vim to search for the command you are looking for. A faster way to show the list of the commands is with the history command:

1
history

Content Security Policy is a browser feature that allows us to make our apps more secure by helping us prevent Cross Site Scripting(XSS) and content injection attacks. The way it does this is by giving us control over where resources will be loaded from and executed.

Even though CSP is supported by most browsers, you should always develop your apps thinking of the worst case scenario (The browser not supporting CSP). The golden security rule for web apps is: Filter input, escape output.

Enabling CSP requires us to configure our server to add a header to our document response. The most restrictive(and safest) value for this header would be:

1
Content-Security-Policy: default-src 'none';

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)

Angular’s ngRoute is useful when building single page apps with multiple views. It allows you to easily load a template into the screen and initialize the controller associated with it.

This is not only helpful to keep your code organized by having different controllers for different screens, but also gives your users a way to create bookmarks that associate a URL in the address bar with the current content of your app. This is a piece of functionality that has always been part of the web(links), so it is a good a idea to keep it there so users don’t run into unexpected behavior.

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:

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)

Since I started working on big companies I’ve been becoming a little interested in distributed systems. There are some distributed technologies I’ve been wanting to play with, but I don’t have a bunch of machines I can use to test how they work. To avoid having to buy multiple machines I decided to learn how to do it in a single machine using virtualization.

In this post I’m going to try to explain the basics of virtualization so we can build a few virtual machines that can talk to each other.

Types of virtualization

There are a few types of virtualization:

• Hardware emulation – This is generally very slow because the hardware is emulated with software.
• Full virtualization – Uses an hypervisor to share hardware with the host machine.
• Para-virtualization – Shares the process with the guest operating system.
• Operating System-level virtualization – Partitions a host into insulated guests. This is kind of chroot but with much stronger resource isolation.

Before your server can trust that a Google ID Token actually comes from a valid user, you need to validate it. Validation of an ID token requires two steps:

• Verify that the value of the aud field in the ID token is identical to your app’s client ID and that the iss is accounts.google.com
• Verify that the ID token is a JWT which is properly signed with an appropriate Google public key and has not expired

Anatomy of an ID Token

An ID Token consists of three sections separated by dots: header.body.signature. Here is an example taken from Google:

1
eyJhbGciOiJIUzI1NiJ9.eyJpc3MiOiIxNDIwNDk1MzA5NDM1MjE2ODU3MSIsImF1ZCI6Ikdvb2dsZSIsInR5cCI6Imdvb2dsZS9wYXltZW50cy9pbmFwcC9pdGVtL3YxIiwiaWF0IjoxMzg1MDc2MTM4LCJleHAiOjEzODUwODIxMzgsInJlcXVlc3QiOnsibmFtZSI6IlBpZWNlIG9mIENha2UiLCJkZXNjcmlwdGlvbiI6IkEgZGVsaWNpb3VzIHBpZWNlIG9mIHZpcnR1YWwgY2FrZSIsInByaWNlIjoiMTAuNTAiLCJjdXJyZW5jeUNvZGUiOiJVU0QiLCJzZWxsZXJEYXRhIjoiWW91ciBEYXRhIEhlcmUifX0.psOU3HlUMGjK_auKEkBhSLzi5n2ATUtaxn_XItGvdhA

I already wrote a post explaining how to sign-in to Google+ from an Android app. Now I want to be able to match all requests my app makes with the user associated with those requests.

Google uses the OpenID protocol and ID Tokens to make this possible. An ID Token consists of two JSON objects, base64 encoded, concatenated and cryptographically signed. This token can be attached to your requests so your server knows who is the user it should associate the request with. This token must be kept secret because anybody using it will be able to identify themselves as the user. To keep the token safe always use HTTPS and transfer it as an HTTP header.