TP Interview Question Software Engineer / Developers
I am not sure I understand. Just to read all points will take O(N). If we want to refelct all points between the minimal and maximal, it will take O(N) just to put "-" or '+' in front of all them.
The question is about a datastructure i suppose.
Once you are given the n points (assume you preprocess them somehow), you need to repeatedly be able to do 1,2,3. IN which case with O(nlogn) preprocessing, O(logn) for 1,2,3 is possible.
I guess, it won't serve the purpose.
I tried using maintaining cumulative total of the count for each quadrant at each position so that I can return the number of points in that particular quadrant in O(1) using cnt(j)-cnt(j-1)
But dunno how to go about reflection :(
Preprocessing (while reading the points)
(1) Construct a balanced binary search tree which keeps the points as it's value. i.e first compare with x coordinates, if they are equal then compare with the y coordinates. At each node also keep the count of points in each quadrant at that time including that point.
Running the query :
(1) Find the point (xi, yi) -> O(logn) . q1, q2, q3, q4.
(2) Find the point (xj, yj) -> O(logn) . q'1, q'2, q'3, q'4.
(3) Ans = ((q'1 - q1), (q'2 - q2), (q'3 - q3), (q'4 - q4)); -> O(1)
(4) Find the quadrant of point (xi, yi). Add one to that entry of the answer. i.e if quadrant is 1 then Ans += (1,0,0,0) -> O(1)
Hence in O(logn)
Preprocessing (while reading the points)
(1) Construct a balanced binary search tree which keeps the points as it's value. i.e first compare with x coordinates, if they are equal then compare with the y coordinates. At each node also keep the count of points (after applying the queries between 0, i.) in each quadrant at that time including that point.
Running the query :
(1) Find the point (xi, yi) -> O(logn) . q1, q2, q3, q4.
(2) Find the point (xj, yj) -> O(logn) . q'1, q'2, q'3, q'4.
(3) Ans = ((q'1 - q1), (q'2 - q2), (q'3 - q3), (q'4 - q4)); -> O(1)
(4) Find the quadrant of point (xi, yi). Add one to that entry of the answer. i.e if quadrant is 1 then Ans += (1,0,0,0) -> O(1)
Hence in O(logn)
I want to give you all hint about one data structure which is allready available
that is "segment tree with lazy propagation" this is the ultimate way to solve that problem
reason
we want to avoid two things to optimize code
avoid flipping of bits . flip bits when actually needed
avoid re-computation of results(counting no of points in quadrants)
Homework? What is TP? Full form?
- Anonymous August 28, 2011