Facebook Interview Question: Write a function that finds t... | Glassdoor

Interview Question

Software Engineer Intern Interview(Student Candidate) Palo Alto, CA

Write a function that finds the minimum and maximum values

  within an unsorted array using divide-and-conquer.
Answer

Interview Answer

6 Answers

3

The best I can do in Java:

int findMinimum(int[] a, int start, int end){
    if (end-start == 0){
      return a[end];
    } if (end-start == 1){
      if (a[end] = 2){
      int split = (start+end)/2;
      int leftLeast = findMinimum(a, start, split);
      int rightLeast = findMinimum(a, split+1, end);
      if (leftLeast

Anonymous on Mar 10, 2011
2

void GetMinMax(int[] array, out int minValue, out int maxValue)
{
    if (array == null || array.Length == 0)
        throw new ArgumentException("array null or empty.");
    MinMax minmax = GetMinMax(array, 0, array.Length - 1);
    minValue = minmax.Min;
    maxValue = minmax.Max;
}

MinMax GetMinMax(int[] array, int begin, int end)
{
    if (begin == end)
        return new MinMax { Min = array[begin], Max = array[begin] };
    else if (begin + 1 == end)
        return new MinMax { Min = Math.Min(array[begin], array[end]), Max = Math.Max(array[begin], array[end]) };
    else
    {
        int mid = begin + (end - begin) / 2;
        MinMax left = GetMinMax(array, begin, mid);
        MinMax right = GetMinMax(array, mid + 1, end);
        return new MinMax { Min = Math.Min(left.Min, right.Min), Max = Math.Max(left.Max, right.Max) };
    }
}

struct MinMax
{
    public int Min;
    public int Max;
}

jerryju on Mar 16, 2011
0

#include
#include

void devide_conque(int*, int, int, int*, int*);

int main(int argc, char** argv) {
    int min, max;
    int i = 0, array_size = (argc - 1);
    int* array = (int*) malloc(sizeof(int) * (argc - 1));
    for (; i rmax ? lmax : rmax;
    }
}

Anonymous on May 20, 2011
0

public static int[] minMax(int[] a) {
        int[] mm = new int[2];
        if (a.length > 0) {
            mm[0] = a[0];
            mm[1] = a[1];
        }
        mm = minMax(a,0,a.length-1);
        return mm;

    }

    public static int[] minMax(int[] a, int low, int high) {
       int[] temp = new int[2];
        if (low+1 < high) {
            int mid = (low+high)/2;
            int[] temp1 = minMax(a,low,mid);
            int[] temp2 = minMax(a,mid+1,high);

            temp[0] = Math.min(temp1[0],temp2[0]);
            temp[1] = Math.max(temp1[1],temp2[1]);
            return temp;

        } else if (low <= high) {
            if (a[low] < a[high]) {
                temp[0] = a[low];
                temp[1] = a[high];
            } else {
                temp[0] = a[high];
                temp[1] = a[low];
            }
        }

            return temp;

    }

Steve on Nov 1, 2011
0

def find_min_max(arr):
  return min_max(arr, 0, len(arr)-1, 1e308,-1e308)

def min_max(arr, i, j, mn, mx):
  if not arr or i > j:
    return mn, mx
  elif i == j:
    return min(mn, arr[i]), max(mx,arr[i])
  else:
    mid = ( i + j) / 2
    left = min_max(arr, i, mid-1, min(mn, arr[mid]), min(mn, arr[mid]))
    right = min_max(arr, mid+1, j, min(mn, arr[mid]), max(mx,arr[mid]))
    return min(left[0], right[0]), max(left[1], right[1])

ajs on Dec 2, 2011
0

first divide list in two, compare number from each list so we got 1list where the minimum is and second list where maximun is. Search for the min in the first list and the max in the second list.

$list[$n-1-$i]){
                $temp = $list[$i];
                $list[$i] = $list[$n-1-$i];
                $list[$n-1-$i] = $temp;
            }
        }

        $min = $list[0];
        for($i=1;$i$max)
                $max=$list[$i];
        }

        $result = array('min'=>$min, 'max'=>$max);
        return $result;
    }
?>

Oscar on Mar 23, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.