Given an unsorted array, extract the max and min value using the least number of comparison.

Question

Rafal · Accepted Answer

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

f(n)=f(n-1)+f(n-2)+...+f(1)+1 · Answer

f(1)=1
f(2)=f(1)+1=2
f(3)=f(2)+f(1)+1=4
...

toan · Answer

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

oded · Answer

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

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas