2
$\begingroup$

I've an hash (base 32 for what it's worth):

hash = 'ab352eghjhngd4'

And I've subscribers that want to listen to new hashes in a range.

   listener = { startAt: 'ab31', endAt: 'ab40', obj }  
   listener2 = { startAt: 'ab350', endAt: 'ab351', obj }

In this case listener1 should be notified of the new hash while listener2 shouldn't.

I'd like to find another algorithm than just iterating through all listeners to find if they fit.


I was thinking of holding an array for startAt

startAtOrderedArray = [
       { startAt: 'ab31', endAt: 'ab40', obj }, 
       { startAt: 'ab350', endAt: 'ab351', obj },
       { startAt: 'uc', endAt: 'uc2', obj }
    ]

Then using binary search I can forget the third item because it's above the hash which was ab352eghjhngd4.

Then I can do the same with endAt.

endAtOrderedArray = [
       { startAt: 'uc', endAt: 'uc2', obj },
       { startAt: 'ab31', endAt: 'ab40', obj }, 
       { startAt: 'ab350', endAt: 'ab351', obj },
    ]

So I end up with:

 before = [
           { startAt: 'ab31', endAt: 'ab40', obj }, 
           { startAt: 'ab350', endAt: 'ab351', obj },
        ]

 after = [
           { startAt: 'uc', endAt: 'uc2', obj },
           { startAt: 'ab31', endAt: 'ab40', obj }, 
        ]

So now if an item is in both array then it's interested in the hash.

The issue however is the complexity is still linear so I'm wondering how can I do better ?


I'd like the question to be as general as possible but for my specific use case it is likely that the first char of startAt and endAt are the same. So { startAt: 'ab', endAt: 'u23' } is not likely.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 13 '17 at 5:31
4
$\begingroup$

Use an interval tree. It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(\log n)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.