Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
* keep the time within O(n^1/2).
Keeping the time within O(n^2) certainly would not be enough!
What is the general rule? The pre-processing time is accounted for in the algorithm's complexity ? Or it is treated as a one-time overhead ?
It depends. If you want an algorithm to be used only one time then of course you need to add it to its run-time complexity. But if you, like in this question, are allowed to pre-process the data, then you will have two run-times, the one for preprocessing and the one for answering queries...
can be done using segment trees. See:
community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
O(preprocessing: n, query: n^1/2)
This is RMQA problem. This can be done by dividing the array in to n^1/2 parts. i.e, if array has 9 elements {3, 9, 5, 2, -1, 4, 10, 0, 3} Then partition the array in to 3 parts and store min for each part in an array M. so M[0] will have 3 , M[1] will have -1 and M[2] will have 0. If the range is 2 to 6 then we need to get min of a[2], M[1], a[6]. so this is O(n^1/2) space and O(n^1/2) time complexity.
I'm assuming you have O(n) time and O(n^1/2) extra space to pre-process the input, and you're then allowed O(n^1/2) time to answer each of any number of queries that could then be sent your way.
- Anonymous September 11, 2012Group the input by chunks of O(n^1/2), and store the sum of each (chunk 0: sum of arr[0] through arr[sqrt(n)-1]; chunk 1: sum of arr[sqrt(n)] through arr[2*sqrt(n)-1]; etc.). That's your preprocessing step.
Now, each query is the sum of some number (maybe 0) of complete chunks of size O(n^1/2) plus possibly parts of the two chunks on each end of the range. There are at most O(n^1/2) complete chunks to sum that are part of the range. Now consider the two chunks that are partially covered by the range. Each of these 2 chunks has at most O(n^1/2) numbers, so we can just add the individual numbers to the total and still keep the time within O(n^2).
This analysis assumes that adds are O(1).