Facebook Interview Question Software Engineer / Developers




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

I think "less than linear time" is not correct term in this case.

I think they mean that such a raising function like log(x) or sqt(n) doesn't require to make calculations for each element in the array. You should simply find the largest element in the array and only then calculate the function.

- Anonymous on May 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

FB wants chuck norris!!!

- baghel on May 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Damn right, but even he couldn't do this in sub-linear time! His solution would probably be guessing and killing anyone who complains :P

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

IS it possible to find even in linear time.
The best I can think of maintaining a min heap of size K, where K= log(n) or sqrt(n)
Even in this case complexity is O(n*log(K))

- XYZ on May 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can always use median-of-median approach to get K-th smallest (or largest) in O(n) time. The same technique also gives worst case O(n logn) complexity for deterministic heap sort.

- lol on May 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

correction in my above post: it would be "deterministic quick sort".

- lol on May 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also i think you would like to maintain a MAX-head of k smallest numbers rather than max heap. For MAX-Heap replacement of a smaller number from current max in K-set is going to be O(logk), in case of min heap it will be O(n).

- viiids on November 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lol is correct. You can use quickselect (which is O(n)) to find the sqrt(n)^th or the log(n)^th element and do a partition around it in O(n) time. Now, outputting the K largest elements in sorted order is a different question, but we can do it in O(n+K*log(K)) time by sorting those elements after partitioning the array as above. As long as K=o(N/log(n)), this is linear time as well.

- Anonymous on June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think it is feasible because without traversing the integers(i.e, in linear time) how can you resort to a judgement regarding the top values?

- Anonymous on May 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is possible only when...
1. Array is sorted.
We can find out the intervals like top(sqrt(26)) and top(sqrt(36)) is 6 and so on.
keep jumping in the array 2 elements at a time or more according to your assumption... compare with apex values of interval...

- Sanjay on May 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use Binary search kind of logic to figure out top(sqrt(n)) or top(log(n)).. It will take log(n) time.

- Punit on September 11, 2011 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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