## Interview Question

• 0

Country: United States

Comment hidden because of low score. Click to expand.
4
of 4 vote

Perform pair-wise comparison on the initial n ints. This costs n/2 ops.
Collect the winners in the winner set and losers in the loser set. Each set has n/2 items.
Find the max of winner requires n/2 ops.
Find the min of loser requires n/2 ops.
Overall, it requires 3/2 n + c ops.
Special care is needed for tied result in the original pair-wise comparison: when a pair is tied, grab the next number and do compare.
If there is a left-over after all pair-wise comparison, put it in both the winner and loser brackets.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

This is, indeed, the correct answer

Comment hidden because of low score. Click to expand.
0

Above solution requires additional O(n) space to store winner and loser.
Below implementation does not require any additional space.

``````public static void findMaxMin(int[] a){
if(a==null || a.length<1)
return;
int max,min;
max=min=a[0];
for (int i = 0; i < a.length; i=i+2) {
if(a[i]>a[i+1]){
if(max<a[i])
max=a[i];
if(min>a[i+1])
min=a[i+1];
}
else{
if(max<a[i+1])
max=a[i+1];
if(min>a[i])
min=a[i];
}
}
System.out.println("Max : "+max+"\nMin : "+min);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution takes 3n/2+c time and does not require any additional space.

``````public static void findMaxMin(int[] a){
if(a==null || a.length<1)
return;
int max,min;
max=min=a[0];
for (int i = 0; i < a.length; i=i+2) {
if(a[i]>a[i+1]){
if(max<a[i])
max=a[i];
if(min>a[i+1])
min=a[i+1];
}
else{
if(max<a[i+1])
max=a[i+1];
if(min>a[i])
min=a[i];
}
}
System.out.println("Max : "+max+"\nMin : "+min);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do you mean <2N comparisons? If so, I would propose a counting sort based algorithm....o(n) but extra space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You mean in n times?

``````public class MinMaxArray {

public static void main(String[] args) {
int array[] = {10, 4, 5, 2, 15, 6, 1, 9};

int min = array[0];
int max = array[0];
for(int i : array) {
if(i < min)
min = i;
if(i > max)
max = i;
}

System.out.println("Min = " + min + ", Max = " + max);
}

}``````

Comment hidden because of low score. Click to expand.
0

This is 2n operations/comparisons

Comment hidden because of low score. Click to expand.
-2

{
void findMinAndMax(int *a, int n){
sort(a, a+n);
cout<<"Max = "<<a[n-1];
cout<<"Min = "<<a[0];

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void findSmallestAndLargest(String test){
int high , low;
int[] numbers = new int[test.length()];
for(int i= 0; i < test.length(); i++){
numbers[i] = Integer.parseInt("" + test.charAt(i));
System.out.println(numbers[i]);
}

high = numbers[0];
low = numbers[0];
int counter = 0;
for(int i=1; i< numbers.length; i++){
if(numbers[i] > high){
high = numbers[i];
counter++;
}else if(numbers[i] < low){
low = numbers[i];
counter++;
}

}

System.out.println("Low " +  low +  " Hight " + high +
" counter  " + counter  + " Length of input " +  numbers.length  );
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Divide and conquer:
1. for n numbers, partition them into two groups of size n/2 and n/2
2. find the max and min from each group
3. perform one more comparison to get the max of two group,
4. one more comparison to get the min of two group

Here's the complexity analysis:
1. Let T(n) be the complexity to get max and min for size n
2. T(n) = 2 T(n/2) + 2 (or T(n)+2 = 2 (T(n/2) + 2)
3. T(2) = 1, you only need one comparison to get max and min for group of 2
4. T(n) + 2 = n/2 * (T(1)+2) = 3n/2 => T(n) = 3n/2 + c
5. step 4 is rough because n may not be a power of 2 but you can use it to bound

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void minmax(int arr[SIZE])
{
int min = arr[0];
int max = arr[0];
for(int i=0;i<SIZE;i++)
{
if(arr[i] < min)
min = arr[i];
else
max = arr[i];
}
cout << "min " << min << "  max" << max << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void findmixmax(int[] a)
{
int min = a[0];
int max = a[0];
for (int i = 1;i<a.length;i++)
{
if(a[i] < min)
{
min = a[i];
continue;
}
if(a[i] > max)
max = a[i];
}
cout<<"min"<<min<<endl;
cout<<"max"<<max<<endl;
}

Above code will do max of 3n/2 comparisons because of continue statement when a[i]<min. it will not check for max.

No of comparisions: 3n/2 max in worst case
Space complexity: O(1)

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinAndMax
{
public static int[] minAndMax( int[] arr )
{
int min, max;
int[] minAndMax = new int[2];
min = max = arr[0];
for( int element : arr )
{

if( element < min )
{
min = element;
}
if( element > max )
{
max = element;
}
}
minAndMax[0] = max;
minAndMax[1] = min;
return minAndMax;
}

public static void main( String[] args )
{
int[] arr = { 3, 4, 1, 2, 5, 7, 6 };

System.out.println( "Max of an Array = " + minAndMax( arr )[0] );
System.out.println( "Min of an Array = " + minAndMax( arr )[1] );
}
}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Comparison based sorting algorithms has a lower bound of nlogn which is clearly not 3n/2 + c ops.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.