Facebook Interview Question
Web:
www.facebook.com
|
HQ:
Menlo Park, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
348 Interview Reviews |
Back to all Facebook Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Facebook:
Nov 7, 2011
Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons).
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (9)
Dec 4, 2011
Very good try! But, the approach does not work. For example, consider this example:
1,9,2,5,4,6,3,7,8,10
1,9,2,5,4,6,3,7,8,10
Helpful Answer?
Yes |
No
Inappropriate?
2 of 3 people found this helpful
Dec 4, 2011
The solution seems to be wrong but gave an insight to me.
Lets assume that we are scanning the array and we are at element "i". We have min and max number so far.
Instead of comparing numbers one one by one, we process them two by two:)
If we process one by one, we make 2 comparison for each element and 4 comparison for two elements.
I sugeest that, first compare "i"th element with "i+1"th element. (1 comparison).
If "i"th element is less than "i+1"th, we compare "i"th element with "min" (1 comparison) and "i+1"th element with max (1 comparison), totally 3 comparison. Otherwise, "i"th is compared with max and "i+1"th is compared with min, again 3 comparison. If we make 3 comparison for each 2 number, we make 3n/2 comparison for the array.
Lets assume that we are scanning the array and we are at element "i". We have min and max number so far.
Instead of comparing numbers one one by one, we process them two by two:)
If we process one by one, we make 2 comparison for each element and 4 comparison for two elements.
I sugeest that, first compare "i"th element with "i+1"th element. (1 comparison).
If "i"th element is less than "i+1"th, we compare "i"th element with "min" (1 comparison) and "i+1"th element with max (1 comparison), totally 3 comparison. Otherwise, "i"th is compared with max and "i+1"th is compared with min, again 3 comparison. If we make 3 comparison for each 2 number, we make 3n/2 comparison for the array.
Helpful Answer?
Yes |
No
Inappropriate?
9 of 10 people found this helpful
Dec 9, 2011
Do it in a tournament style
For example: 0,4,2,11,16,9,23,2
Divide these numbers into 2 arrays min, max
where min array contains min of ({0,4}{2,11},{16,9},{23,2}). So just by 4 comparisons we will have
min: 0,2,9,2
max:4,11,16,23
No do it again for min and max arrays.
So the total number of comparisons will be 4+2+2+1+1=10.
It's much better than 3/2n in this case it's 5/4n
For example: 0,4,2,11,16,9,23,2
Divide these numbers into 2 arrays min, max
where min array contains min of ({0,4}{2,11},{16,9},{23,2}). So just by 4 comparisons we will have
min: 0,2,9,2
max:4,11,16,23
No do it again for min and max arrays.
So the total number of comparisons will be 4+2+2+1+1=10.
It's much better than 3/2n in this case it's 5/4n
Helpful Answer?
Yes |
No
Inappropriate?
2 of 2 people found this helpful
Dec 10, 2011
this special case gives 5n/4 when n is 8. When n is large, number of comparisons approach 3n/2
Helpful Answer?
Yes |
No
Inappropriate?
0 of 4 people found this helpful
Feb 10, 2012
Construct a min and max heap - time to construct heap is o(logn), so the heaps will take o(logn) each - still o(log n) and then o(1) to get the min and max.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 1 people found this helpful
Apr 3, 2012
Time to construct a heap is O(NLg(N)) not O(Lg N) .. the max_heapify method takes O(Lg N) but there is N calls to it.
But still this is the best solution till now.
But still this is the best solution till now.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 1 people found this helpful
Apr 21, 2012
take 2 elements of an array
say a[0],a[1]
now temp=a[0]<a[1]?a[0]:a[1]; //1st comparison
min=temp<min?temp:min; //2nd comparison
max=temp>max?temp:max; //3rd comparison
hence you can traverse the entire array in n/2 steps making 3 comparisons per pair,
a total of 3n/2 comparisons; at the end you have min and max both
void minmax(vint &a)
{
int n=a.size();
if(n==0) return;
int min=a[0],max=a[0];
int f,s,t;
for(int i=0;i<n;++i)
{
f=a[i];
if(i+1<n) i+=1;
s=a[i];
t=f<s?f:s;
if(t<min) min=t;
if(f+s-t>max) max=f+s-t;
}
cout<<"min: "<<min<<endl;
cout<<"max: "<<max<<endl;
}
say a[0],a[1]
now temp=a[0]<a[1]?a[0]:a[1]; //1st comparison
min=temp<min?temp:min; //2nd comparison
max=temp>max?temp:max; //3rd comparison
hence you can traverse the entire array in n/2 steps making 3 comparisons per pair,
a total of 3n/2 comparisons; at the end you have min and max both
void minmax(vint &a)
{
int n=a.size();
if(n==0) return;
int min=a[0],max=a[0];
int f,s,t;
for(int i=0;i<n;++i)
{
f=a[i];
if(i+1<n) i+=1;
s=a[i];
t=f<s?f:s;
if(t<min) min=t;
if(f+s-t>max) max=f+s-t;
}
cout<<"min: "<<min<<endl;
cout<<"max: "<<max<<endl;
}
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
May 16, 2012
Based on the light's idea of pair comparisons, but bug fixed. Compiled and tested.
public MinMax find(int[] data) {
int i = 0;
MinMax minMax = new MinMax(data[0], data[0]);
while(i < data.length) {
if(i + 1 < data.length) {
if(data[i] < data[i+1]) {
if(data[i] < minMax.min) {
minMax.min = data[i];
}
if(data[i + 1] > minMax.max) {
minMax.max = data[i + 1];
}
} else {
if(data[i] > minMax.max) {
minMax.max = data[i];
}
if(data[i + 1] < minMax.min) {
minMax.min = data[i + 1];
}
}
i += 2;
} else {
minMax.min = data[i] < minMax.min ? data[i] : minMax.min;
minMax.max = data[i] > minMax.max ? data[i] : minMax.max;
i++;
}
}
return minMax;
}
public MinMax find(int[] data) {
int i = 0;
MinMax minMax = new MinMax(data[0], data[0]);
while(i < data.length) {
if(i + 1 < data.length) {
if(data[i] < data[i+1]) {
if(data[i] < minMax.min) {
minMax.min = data[i];
}
if(data[i + 1] > minMax.max) {
minMax.max = data[i + 1];
}
} else {
if(data[i] > minMax.max) {
minMax.max = data[i];
}
if(data[i + 1] < minMax.min) {
minMax.min = data[i + 1];
}
}
i += 2;
} else {
minMax.min = data[i] < minMax.min ? data[i] : minMax.min;
minMax.max = data[i] > minMax.max ? data[i] : minMax.max;
i++;
}
}
return minMax;
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Facebook Interview
2 of 3 people found this helpful
by Redeye:
// For convenience we assume array has even no. of elements.
Compare 1st element with nth element, if 1st element > nth element swap them
Do 1st pass, total n/2 comparisons (n/2 instructions used in swapping assuming only 1 instruction per swap)
Traverse first half in usual way of comaprisons -> n/2 comparisons Highest is your max element
Traverse second half in usual way of comaprisons -> n/2 comparisons lowest is your min element.
Total comparisons = n/2 + n/2 + n/2 = 3n/2