CareerCup

void public int find2ndMax(String aString) {
	int max1 = 0;
	int max2 = 0;
	int strLen = aString.length();
	
	// error check string null/length
	
	for (i = 0; i < strLen; i++) {
		char someChar = aString.charAt(i);
		if (someChar > max1) {
			max2 = max1;
			max1 = someChar;
		} else if (someChar > max2) {
			max2 = someChar;
		}
	}

Kevin and Ankit's approach are correct. Have two variables keeping track of the Max and next-to-max.Traverser the whole array and by the time you reach the end you have the answer. Now if the interviewer says find the 5th Max (or someting like nth max) then this approach will suffer a lot and in that case I think the best answer would be to maintain a MaxHeap of the top n numbers and you are done...HTH

@ Sadineni.Venkat

Your code does not address the case where all numbers in Input array are equal.

Following is my java implementation.

int max=Integer.MIN_VALUE, secondMax=Integer.MIN_VALUE;
		for(int i: myArray)
		{
			if(i>max)
			{
				secondMax=max;
				max=i;
				
			}
			else if (i<max && i>secondMax)
			{
				secondMax=i;
			}
			
		}

. I gave the following code. Interviewer is stressing there are more ways to break this function. Please tell me the test cases I am missing below.

int Find_2nd_Max(int Arr[], int size)
{
if( size < 2 )
{
cout << "Array size should be at least 2. So returning some invalid value" << endl;
return -999;
}
else if( Arr == NULL)
{
cout << "The given array is NULL. Please pass a valid array. " << endl;
return -999;
}
else
{
int max1, max2;
if( Arr[0] > Arr[1] )
{
max1= Arr[0];
max2= Arr[1];
}
else
{
max1= Arr[1];
max2= Arr[0];

}
for(int i=2; i < size; i++ )
{
if( Arr[i] > max2 )
{
if( Arr[i] > max1 )
{
max2=max1;
max1= Arr[i];
}
else
{
max2 = Arr[i];
}
}
}
return max2;
}
}

/* Test Cases - Output
1. Size < 2 - Error message. return -999
2. Arr==NULL - Error message and return -999
3. Size=2
4. Size > 2, All the elements are equal
5. Size > 2, elements in ascending order
6. Size > 2, elements in descending order
*/

void Test_Find_2nd_Max()
{
int Arr[] = {1, 2, -3, 4, -7};
int size = 5;
int max2 = Find_2nd_Max(Arr, size);
cout << "The 2nd max is: " << max2 << endl;
}

int Max2nd(int* array, unsigned entries)
{
int max = array[0];
int max2 = array[1];
if(max2>max) swap(max,max2);
for(unsigned u = 2; u < entries; u++) {
if(array[u] >max) {
max2 = max;
max = array[u];
}
}
return max;
}

What if array is [1, -999] ?

The code will break in the case when the first and second is the max element and they are equal. For example {11,11, 7, 8, 9,10}. In this case max1 = 11 and max2 will also be 11 instead of being 10

// wrote a C# function
int Find2ndMax(int[] arr)
{
int length = arr.Length;
if (length < 2)
return Int32.MinValue;

int max = arr[0], max2 = arr[1];
if (arr[0] > arr[1])
{
max = arr[0];
max2 = arr[1];
}
else if (arr[1] > arr[0])
{
max = arr[1];
max2 = arr[0];
}
else
{
max = arr[0];
max2 = Int32.MinValue;
}

for (int i = 2; i < length; i++)
{
if (max2 < arr[i] && max < arr[i])
{
max2 = max;
max = arr[i];
}
else if (max2 < arr[i] && max > arr[i])
{
max2 = arr[i];
}
}
return max2;
}

A simple approach for this would be..assuming the array has more than 2 elements, implement bubble sort for 2 iterations...after that, the last element in the array would be the one with the max value and the one before that would be 2nd max...

tournament sort will work fine in dis case...O(lg N)..

int secondMax(int a[], int n){

int i, max, smax;
max=smax=-1;
for(i=0;i<n;i++){
if(a[i] > max){
smax = max;
max = a[i];
}
else if(a[i] > smax){
smax = a[i];
}
}
return smax;
}

The above code will work for all whole numbers in the array. For negative numbers, just change the
limits of max=smax=INT_MIN. Don't forget to include <limits.h>. Simple !

but both this solutions will fail for {11,7, 11, 8, 9,10} - instead of 10 it will answer 11. i would change it slightly -
if(a[i] > max){
smax = max;
max = a[i];
}
else if(a[i] = max){
// do nothing
}
else if(a[i] > smax){
smax = a[i];
}

Please comment:

If size less than 1 -> return -1
If duplicate numbers -> return -1

int findSecondMaxIndex(int arr[], int size)
{
	int max, max2;
	int index, index2;

	index2 = -1;

	boolean isMaxSet = false;

	for (int i=1; i<size; i++)
	{
		if (!isMaxSet)
		{
			if (arr[i-1] > arr[i])
			{
				max = arr[i-1];
				index = i-1;

				max2 = arr[i];
				index2 = i;
				isMaxSet = true;
			}
			else if (arr[i-1] < arr[i])
			{
				max2 = arr[i-1];
				index2 = i-1;

				max = arr[i];
				index = i;
				isMaxSet = true;
			}
		}
		//	New max
		else if (arr[i] > max)
		{
			max2 = max;
			index2 = index;

			max = arr[i];
			index = i;
		}
		//	New max2
		else if (arr[i] > max2)
		{
			max2 = arr[i];
			index2 = i;
		}
	}

	return index2;
}

TEST CASES:

10				-1
10 10				-1
10 10 10 10 5			4
10 5 6				2
1 1 -3 -2			2

use "quick select" Algorithm. It will be efficient in all case but it will modify the array.

int a[] = {4,4,5,1,3,8,3,2,44,20};
static int get_nth_max_element(int [] val,int n)
{
int temp[] = new int[n];

for(int i=0;i<n;i++)
temp[i] =0;
for(int i=0;i<val.length;i++)
if(val[i] > temp[0]) temp[0] = val[i];
for(int i=0;i<n;i++)
for(int j=1;j<val.length;j++)
{
if(val[j] > temp[i] && val[j] < temp[i-1])
temp[i] = val[j];
}
return temp[n-1];
}

{{

int secondmax(int A[], int n)
{
int max, max2, i;

if(n==0)
{
printf("Empty array");
exit(-1);
}
else if(n==1)
{
printf("We can't use size 1 array!");
exit(-1);
}
else if(n==2)
{
if(A[0]>A[1])
max2= A[1];
else
max2=A[0];
}
else
{
i=1;
while((A[0]==A[i]) && (i!=n))
{
i++;
}
if(i==n)
{
printf("All elements of the input array are equal..!\n");
}
else
{
if(A[0]>A[i])
{
max=A[0];
max2=A[i];
}
else
{
max=A[i];
max2=A[0];
}
}

i++;
while(i!=n)
{
if(A[i]> max)
{
max2=max;
max=A[i];

}
else if(A[i]<max && A[i]>max2)
max2=A[i];

i++;
}
}

return max2;

}

}}

How about this?

use quickselect to find kth largest element in O(logN)

use quickselect to find kth largest element in O(N)

build max heap and remove the top element...heapify again to get the 2nd max element
complexity O(log n)

A sample program in Java. Note that you need to handle empty- and single-element array cases here. Runs in O(n).

long getSecondMax(long[] arr) {
		long max = Long.MIN_VALUE;
		long secondMax = Long.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			long v = arr[i];
			if (v > max) {
				secondMax = max;
				max = v;
			} else if (v > secondMax && v < max) {
				secondMax = v;
			}
		}
		return secondMax;
	}

#include <iostream>
#include <climits>
using namespace std;

int findSecondLargest(int* arr, int n) {
	int first = INT_MIN;
	int second = INT_MIN;

	for(int i = 0; i < n; i++) {
		if(first < arr[i]) {
			second = first;
			first = arr[i];
		}
		else if(second < arr[i] && arr[i] != first) {
			second = arr[i];
		}
	}
	return second;
}

int main() {
	int arr[] = {3, 5, 9, 6, 4, 2, 11};
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << findSecondLargest(arr, n);
}

One of the best approaches to solving the above algorithm is with the help of a heap, you will have to implement a max heap using a priority queue.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findrepeatedelement(int arr[], int n, int k){
priority_queue<int> p;
for(int i = 0; i < n; i++)
p.push(arr[i]);
while(--k)
p.pop();
return p.top();
}
int main(){
int arr[] = {10, 5, 1, 30, 20};
cout<<findrepeatedelement(arr, 5, 3);
return 0;
}

int Max2nd(int* array, unsigned entries)
{
int max = array[0];
int max2 = array[1];
if(max2>max) swap(max,max2);
for(unsigned u = 0; u < entries; u++) {