Luís Ramalho Entrepreneur & Developer

Codility's Genomic Range Query

Genomic Range Query is a problem from codility with the goal of finding the minimal nucleotide from a range of sequence DNA. Note that before attempting this problem, you should read the material on prefix sums.

In order to solve the problem I started by marking the position of each nucleotide in a 2D array. There are 4 nucleotides (A, C, G and T), so a[0][i] will mark the position i of nucleotide A as 1 if it appears in the string, otherwise a[0][i] will have the value of 0. The same for a[1][i] for nucleotide C, and so on.

int[][] a = new int[4][s.length()]; // A, C, G and T
for (int i = 0; i < s.length(); i++) {
    char ch = s.charAt(i);
    switch (ch) {
    case 'A':
        a[0][i]++;
        break;
    case 'C':
        a[1][i]++;
        break;
    case 'G':
        a[2][i]++;
        break;
    case 'T':
        a[3][i]++;
        break;
    default:
        break;
    }
}

Once we have the position of each nucleotide in the 2D array a, we can proceed to compute the prefix sum of each of the nucleotides:

int[][] prefixSum = new int[4][s.length() + 1];
for (int k = 1; k < s.length() + 1; k++) {
    for (int j = 0; j < 4; j++) {
        prefixSum[j][k] = prefixSum[j][k - 1] + a[j][k - 1];
    }
}

The final step is to return the value of the minimal impact factor of nucleotides contained in the given range. I did that by checking if the difference between the highest range prefix sum and the lowest returns a value above 0, if yes, then it means that a nucleotide of that impact factor must have occured, hence it's our answer and we can break out of the loop.

int[] m = new int[p.length];
for (int i = 0; i < p.length; i++) {
    int x = p[i];
    int y = q[i];
    for (int j = 0; j < 4; j++) {
        if (prefixSum[j][y + 1] - prefixSum[j][x] > 0) {
            m[i] = j + 1;
            break;
        }
    }
}

The full solution can be found here.

2014 so far

My previous post was a bit more than a year, thus I reckon it is time for an update on what I have been up to.

Sinemys

In September 2011 I co-founded with two other partners a web development company, and in late 2013 we decided it was time to close it.

The reasons are multiple, but the most important one was the lack of a clear mission statement. The company simply did too much.

We signed the final closing papers this month.

Porto.rb

Unfortunately with the departure of Sinemys, another project had to die.

I started a ruby meetup in Porto called Porto.rb which gathered a total of 50 great Rubyists. It is sad to see it go, and would be happy if someone takes over. Let me know.

GITM master’s program

Life goes on, and after some reflection I have decided that I would benefit from a better understanding of IT management. Thus, I applied to the Master's Degree Programme in Global IT Management offered by the University of Turku, to which I was admitted.

Classes will start in the end of August.

How to get the Facebook Access Token, the Extended Page Access Token that never expires

You will need:

  • [APPLICATION_ID]
  • [APPLICATION_SECRET] (https://developers.facebook.com/apps/[APPLICATION_ID])
https://www.facebook.com/dialog/oauth?client_id=[APPLICATION_ID]
&scope=manage_pages,publish_stream
&response_type=token
&redirect_uri=https://www.facebook.com/connect/login_success.html

When you see 'Success' then you have a URL like:

https://www.facebook.com/connect/login_success.html#access_token=[ACCESS_TOKEN]&expires_in=[SECONDS]

Grab the [ACCESS_TOKEN] then,

https://graph.facebook.com/oauth/access_token?client_id=[APPLICATION_ID]
&client_secret=[APPLICATION_SECRET]
&grant_type=fb_exchange_token
&fb_exchange_token=[ACCESS_TOKEN]

Finally, you will see your extended page access token that never expires

access_token=[EXTENDED_ACCESS_TOKEN]
https://graph.facebook.com/me/accounts?access_token=[EXTENDED_ACCESS_TOKEN]