Facebook

www.facebook.com
Employer Engaged

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

Interview Answer

4 Answers

0

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
11

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.