Facebook

  www.facebook.com
Work in HR? Unlock Free Profile

Facebook Software 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."
Add Tags [?]
Answer

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

Answers & Comments

0
of 25
votes
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
votes
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
votes
well normal case n comparisons
Compare in pair and you have n-1 comparisons...
- toan on Feb 5, 2013
8
of 8
votes
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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.