December 12, 2017

Solution to Genomic Range Query in Go

Recently I've been spending a lot more time focussed on learning the Go programming language. I've played with Go on and off for about 3 years but never gotten serious with it. I've decided 2018 is the year that will change!

I've been working through the lessons on Codility. I realised I haven't written a blog post in sooo long and thought the best way to start the momentum is a quick post with something I've been working on very recently. So here's my solution to Lesson 5 - Genomic Range Query in Go.

func Solution(S string, P []int, Q []int) []int {

    nucleos := []rune{'A', 'C', 'G', 'T'}
    sums := make(map[rune][]int)

    M := len(P)
    N := len(S)

    // Initialize prefix-sums

    for _, n := range nucleos {
        sums[n] = make([]int, N+1)
    }

    // Calculate prefix sums

    for i, r := range S {
        for j := range sums {
            sums[j][i+1] = sums[j][i]
        }
        sums[r][i+1]++
    }

    // Process queries

    for i := 0; i < M; i++ {
        p := P[i]
        q := Q[i]

        for j, n := range nucleos {
            if (sums[n][q+1] - sums[n][p]) > 0 {
                P[i] = j + 1
                break
            }
        }
    }

    return P
}

Hopefully by posting this, the inertia to write more posts will be too strong to resist 🤞

Comments powered by Disqus