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

- Anonymous September 11, 2012 | Flag Reply
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!

- Anonymous September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gnahzy September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- ksandeep.v2 September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- FBNerd February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- DarkPassenger March 01, 2013 | Flag
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

- evan September 11, 2012 | Flag Reply
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)

- AC Srinivas September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Safi December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

paulbutler.org/archives/data-structures-for-range-sum-queries-slides/

- Second Attempt November 15, 2012 | Flag Reply
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.

- Anonymous December 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 26, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More