Facebook Interview Question: Given an unsorted array, extr... | Glassdoor

Interview Question

Software Engineer Intern Interview(Student Candidate) Stanford, CA

Given an unsorted array, extract the max and min value

using the least number of comparison.

1

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

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

well normal case n comparisons
Compare in pair and you have n-1 comparisons...

toan on Feb 5, 2013
15

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