Interview Question
Country: United States
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);
}
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);
}
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);
}
}
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 );
}
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
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)
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] );
}
}
Perform pair-wise comparison on the initial n ints. This costs n/2 ops.
- t4k9 January 14, 2015Collect 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.