sangupta/ps

Fastest Algorithm to find where the number lies

sundarv85 opened this issue · 2 comments

sundarv85 commented

I have the following content

1,10,Jose
12,28,Daniel
33,37,Vincent

When I get a number, say 15 I need to find where it lies and what is the name.

For e.g. 30 would not have a matching name.

Which algorithm would fit here and what would be the fastest way for this. Thoughts?

FedericoPonzi commented

Hi, this looks more an homework than something related to this repo. I think you should better ask for help in more appropriate places (/r/learnprogramming should be fine).

  • 👍1
sangupta commented

In case the ranges do not overlap (which I presume will not), you will need 3 arrays. Two integer-arrays int[] that contains the starting number and the ending number, and the third a String-array String[] that contains the name at the same index.

Now given a number you just need to lookup the number in the first array - which you can do via a divide-and-rule lookup (aka the binary search) and once you have an index where the integer on the left is smaller and the integer in the right is higher - you have a hit candidate.

Now at the same hit-index check the second int-array containing the ending number, and match that this is a valid hit. Once checked you have the name with you.

Space Complexity - O(n)
Time Complexity - O(log n)

Hope this helps. Feel free to reopen the issue in case you have more thoughts.

PS: The reason I assume ranges will not overlap is because in that case we will have multiple valid candidate results for a given number.

PS: I agree that this is more of a homework exercise, but still this one being a simple one - I went ahead and put my thoughts in here.