Computing Ranges in Constant Time | Hacker News Reader

Computing Ranges in Constant Time

deniskyashif.com

35 pointsgbrown_5 comments

Conclusion: You need pre-processing and another data structure (sparse table) anyway....

On the other hand, if you have a particular problem, there is always someone that have solved in a very clever way to make it optimized for the given situation.

But, Please, folks in HN, don't take questions/answers like this and ask them on interviews....

They are very specific, and the solutions are basically using tricks (i.e. enough esoteric data-structure and algo), to solve those limited amount answers.

I am not so sure about this technique being specific. I'd say sparse tables are quite well known and presented to students at one of Algorithms and Data Structures courses at most universities. Another generally known solution applicable here would be segment trees with Theta(n) preprocessing and Theta(log n) query.

Also the problem of querying range sums, as the author himself notes, has actually much simpler solution in form of a prefix sum array, which is exactly what the name suggests and can be computed in one iteration, queries being constant time.

Obviously self-taught developers might be unfamiliar with these concepts and one might make a point of these questions screening for computer science background, but I personally believe that being aware of fundamental algorithm design techniques is important for programmers working on non-trivial problems. Some people say that you can always google these things, but can you really? It's like saying that you don't have to learn integration and just continue on with calculus, always being able to just look up needed formulas as you go.

The value of these fundamental algorithms is much more than just knowing how to write them when the need arises. They teach you general principles of algorithm design, present with many patters you can apply in problem solving and create a solid foundation for being able to deal with non-trivial problems. Knowing how segment trees or sparse tables work opens you up to whole new domains of useful applications building on them. There are reasons why these are generally taught at undergraduate level.

Comp Science major here, I still think these type of questions are not relevant years down the road, unless you explicitly are working with them. (eg. most database systems, log storage, and such will have to deal with such optimizations).

If you do, then it is fair to ask. But I have seen interviewers asking questions like these even for folks that would not need them . (aka, mobile development, of front end JS)

It is like asking a motorcycle racer/driver on whats the fastest way to swap four wheels in a F1 race.... Makes sense of the formula 1 driver, but not for the 500c motorcycle driver.

Unfortunately our industry is filled with lots of self-congratulating types that use interviews to inflate their own sense of self worth.

So this method works for max and sum. What else? Is it any sort-of "associative function" - ie, f st. f(x, f(y,z)) = f(f(x,y), z)?

Are there other useful functions satisfying these conditions?

The one that works for sum works for all associative functions. One can do a bit better using the same amount of space, but with query time O(α(n)), where α is the inverse Ackermann function. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.1...

Reply on news.ycombinator.com