## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
You are given N points.
Preprocess them such that given any rectangle, we can find the number points that lie inside the rectangle in O(log N) time. Note that we need just the number of points not which points lie inside. Can we do the pre-processing in O(N^2) time? What do we do in that pre-processing? I could come up with O(N^4) pre-processing. Anything better?
PP Monday, July 21, 2008
First solve the simple case where the points have integer coordinates between 1 and n. To prepare, compute the number of points in each rectangle with a corner at (1,1) and an opposite corner at a grid point (of which there are n^2). This can be done by computing running sums first horizontally and then vertically.
Now to answer a query for the rectangle ((a,b),(c,d)) where a < c and b < d, return count((1,1),(c,d)) - count((1,1),(a-1,d)) - count((1,1),(c,b-1)) + count((1,1),(a-1,b-1)). The reduction to this case is straightforward.
d Monday, July 21, 2008 |

Powered by FogBugz