# Solution to Genomic-Range-Query by codility

21 Jan

Question Name: GenomicRangeQuery

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

### 43 Replies to “Solution to Genomic-Range-Query by codility”

1. Alessandro says:

In this one I implemented a Segmented Tree, which was aaaa looooootttt more code than yours @o@.

• Sheng says:

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?

2. Alessandro says:

(by the way I Subscribed to your blog, cool posts for those interested in programming challenges!)

• Sheng says:

Thanks a lot! These questions should be also helpful to the internship/job seekers, like me~

3. Karol says:

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 ðŸ™‚

• Sheng says:

Thanks for sharing! I removed your previous mis-formatted comment to keep clean.

• Luciano Issoe says:

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

• Sheng says:

Great! Thanks!

4. Dustin says:

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

• Sheng says:

Thanks for sharing!

5. 20150525 says:

Why don’t set the initialize value of next_nucl to DNA_len instead of -1?

• Sheng says:

Yes, you can. It is more traditional and better to use DNA_len as the not-exist-item-index.

6. Damian says:

7. Martin says:

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?

• Sheng says:

The for loop itself is O(M). And inside the loop, the sorted statement is O(NlogN). Totally, it is O(M*N*logN).

8. Giovani says:

C# solution – similar approach

9. Adding a Java Solution 100/100, https://codility.com/demo/results/demoJFB5EV-EG8/

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.

10. Mathieu says:

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

11. Son Thai says:

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.

• Sheng says:

Yes, if they are short and the product is small, it works.

12. TD says:

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.

• Sheng says:

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).

13. Alex says:

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!

14. Tim Nguyen says:

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 ðŸ™‚

• Sheng says:

Hi Tim. Sorry, nothing but practice more ðŸ™‚

15. pyhu says:

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!

• Sheng says:

Thanks for C !

16. Vygis says:

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?

• Sheng says:

It’s O(N*M), not O(N+M). Because (‘A’ in S[i:j+1]) is O(N) in worst case.

• iolite says:

Hi, I got 100% with a similar solution, also with “detected time complexity O(N + M)”:

Sheng, can you comment on why mine might have passed the performance checks? Should it not pass in general?
Thanks ðŸ™‚

• Sheng says:

The “detected time complexity” is not always accurate. Because “”‘A’ in sub_S” is an O(N) operation, I would take your solution as O(N*M).

• Sheng says:

Please refer to “Guideline for Comments” (in the right column) to post code.

17. Chima Alaebo says:

Javascript code 100%

18. Small improvement to @karol solution.

19. MatB says:

I came up with this.

20. Vin says:

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

• Sheng says:

21. Another Javascript solution:

22. Fred says:

Clean VB:

23. 4nti7rust says:

Hello,

I am more a C++ dev, but I tried it in python, and it also gets the holy 100/100.

I don’t understand why you don’t loop through the letter, as this is a fixed size loop it does not account in time diff, right ?

Also I find my cost function very ugly now that I see what you did :p.

• Sheng says:

Yes, it’s more a design style, rather than a performance concern ðŸ™‚

24. Ana says:

I’ve solved this using prime numbers, but I’m failing at performance tests. I can’t see why. my time complexity is O(N+M)