Work in HR? Unlock Free Profile

# FacebookSoftware Engineer Intern Interview Question (student candidate)

I interviewed in Stanford, CA and was asked:
"Given an unsorted array, extract the max and min value using the least number of comparison."

Part of a Software Engineer Intern Interview Review - one of 1,070 Facebook Interview Reviews

0
of 25
f(1)=1
f(2)=f(1)+1=2
f(3)=f(2)+f(1)+1=4
...
- f(n)=f(n-1)+f(n-2)+...+f(1)+1 on Nov 24, 2012
0
of 8
var min, max, arr = [3,4,2,7,1,9];
for(i in arr){ //n-iterations
min = Math.min( arr[i], arr[i+1], min ); //2 comparisons
max = Math.max( arr[i], arr[i+1], max ); //2 comparisons
}

//4n => n
- oded on Jan 3, 2013
0
of 2
well normal case n comparisons
Compare in pair and you have n-1 comparisons...
- toan on Feb 5, 2013
8
of 8
Minimum number of comparisons is 3n/2. The strategy is to go through the elements in pairs, and compare the smaller one to the minimum, and the bigger one to the maximum. This is 3 comparisons, done n/2 times in total, for 3n/2 running time. Working code in python:

import random
import sys

r = [random.randint(1,100) for i in range(31)]
print r

mini = r[0]
maxi = r[0]

start = 0
if len(r) % 2 != 0:
start = 1

for i in range(start,len(r)-1,2):
n1 = r[i]
n2 = r[i+1]

# Exactly 3 comparisons each time
if(n1 < n2):
mini = min(n1,mini)
maxi = max(n2,maxi)
else:
mini = min(n2,mini)
maxi = max(n1,maxi)

print mini
print maxi
- Rafal on Feb 26, 2013