## Facebook Interview Question for 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.

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

FB wants chuck norris!!!

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

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

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

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.

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

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

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

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

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

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.

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?

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

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

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

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.