## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
7
of 7 vote

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.

Group 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).

Comment hidden because of low score. Click to expand.
1
of 1 vote

* keep the time within O(n^1/2).

Keeping the time within O(n^2) certainly would not be enough!

Comment hidden because of low score. Click to expand.
0

i think the solution is O(n^0.5) indeed. the author just makes a typo.

Comment hidden because of low score. Click to expand.
0

Yes, that was my own correction to my own solution. It was a typo.

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

if it queries sum[0...n], it requires O(n) time anyway. so I guess preprocessing is not counted for the O(n^0.5) time complexity.

Comment hidden because of low score. Click to expand.
0
of 2 vote

are you posting this because you are taking parallel computing course in U of M?

I am taking it too and this looks quite the same as the homework........so, i wish i could help, but i dont want to

Comment hidden because of low score. Click to expand.
0
of 0 vote

can be done using segment trees. See:
community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
O(preprocessing: n, query: n^1/2)

Comment hidden because of low score. Click to expand.
0

No. Although time complexity of segment tree is better (logn < n^1/2) it uses linear space (n^1/2 < n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Also segment tree is not the right answer for this problem because it uses O(n) space because of the leaf nodes.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.