Solution to Genomic-Range-Query by codility

21 Jan


Question Name: GenomicRangeQuery

This is a typical case that uses more space for less time.

37 Replies to “Solution to Genomic-Range-Query by codility

    • Segmented Tree is a more powerful and more universal solution for this kind of questions. The major reason, that I did not use it here, is: I did not master it. If you are willing, could you please share your code here, as another solution?

  1. Here is my solution. Python, result 100/100. A bit different approach than yours, closer to Lesson 3 topic (Prefix Sums).

    Sorry for bad tag usage in my previous post attempt 🙂

    • Great code!! Just making it a little more verbose without a dictionary for expressiveness :

  2. Solution in Golang without going to a map to convert nucleotide to number.

  3. Trying to understand the time complexity problem here. This is apparently O(N*M) instead of the required O(N+M). Can someone explain why?

  4. C# solution – similar approach

  5. Adding a Java Solution 100/100,

    I know the ImpactFactorHolder class might be too much, but It was a little bit tricky for me on what was happening, my initial attempts I used a two dimensions arrays, but somehow I wasn’t able to deal with some of the test cases and adding that extra class helped me a little bit to understand and solve the problem.

  6. I took the liberty of Implementing the original solution in a more pythonic way, using dictionaries, removing the “-1” trick, using reversed(), enumerate() and zip() instead of looping with an index

  7. I had an idea but could not implement it due to practical number range limits. Small numbers may work.
    Instead of impact 1,2,3,4; encode them as primes 2,3,5,7.
    Instead of prefix-summing impacts, prefix multiplying the primes (equivalent to summing logs of primes).
    Instead of subtracting prefix sums, use division.
    For each segment, the division result is tested for divisibility of 2, then 3, then 5, then 7. If divisible, decode back to the minimum impact 1,2,3,4 correspondingly.

  8. Hi,
    I am trying out Codility exercises to help me learn coding as I am preparing for interviews. Many thanks to Sheng, and other contributors, for the enormous help he is providing to people like me who is trying to learn on our own.
    For this problem, I cooked up this solution in Python but I am not sure if it matches all the time and space restrictions of the problem. Any help would be appreciated a lot. Thanks in advance.

    • Hi, thanks for visiting my blog! Unfortunately your solution does not match the time restrictions of the problem. Let the N be the length of the DNA S, and M be the length of queries (P and Q), the statement “min(set(SS[P[i]:(Q[i]+1)]))” is O(N), and it is inside one loop of O(M). Therefore, the total complexity is O(M*N).

  9. Here’s a 100% score solution I did straight from codility in java. It’s definitely a hack’n’slash patch job to deal with some of the test cases, but I honestly didn’t understand some of the logic that others were employing.(Especially Luciano Issoe’s InRange variables in his last FOR loop. A quick explanation would be great =D)

    Anyhow, hope this can help!

  10. Hi Sheng,

    This is a really great solution. How did you come up with this approach? Like is there any tricks or tips to know how I should approach the solution for this problem? I gave up after 3hrs solving since my approaches were wrong. I just want to know how you figured this problem out. Like ways to think and steps to approach the solution.

    Thanks 🙂

  11. Hello, here’s something I came up with in C, since there aren’t many C solutions I thought it could help. Seems kinda long and probably could use some optimisation.
    Feel free to comment!

  12. I scored 87% with this solution. The detected time complexity is O(N + M) but I get “Timeout Error” on the last check. Could you tell me why by any chance?

  13. Javascript code 100%

  14. Small improvement to @karol solution.

  15. I came up with this.

  16. Another solution in python , got 100/100 on codility, many thanks to all the contributors especially Sheng

  17. Another Javascript solution:

Leave a Reply

Your email address will not be published. Required fields are marked *