CODEWITHSUNDEEP
algorithmrange-query
SpiderRico
SpiderRico

Reputation: 2046

Algorithms for range query on streams of integers

I'm getting a stream of positive integers to my program. I've to store them as I receive them and be able to answer to range queries that come in between.

A simple solution that came to my mind is to store integers in a hashtable where keys are character representation of the integers(keys must be strings in my hashtable). Then, whenever a range query [a, b] comes, I can simply loop from a to b, check whether key exists and retrieve the value if it does. However, I'm not sure if this is a good approach.

What other alternative solutions exists for this problem?

Upvotes: 0

Views: 149

Answers (1)

Scott Hunter
Scott Hunter

Reputation: 49920

If you maintained an ordered list of the integers from the stream read so far, then a range query can be done by finding a (using binary search) and iterating from that point until you pass b, so that the time spent on the query will be proportional to the actual size of the result, regardless of how sparse the range is filled.

Upvotes: 0

Related Questions