Microsoft Interview Question
Software Engineer in TestsTeam: Server and tools in microsoft erp
Country: United States
Interview Type: In-Person
#include<stdio.h>
int secondlargest(int arr[] , int len)
{
int num1,num2,temp,i;
int max1 = 0, max2 = 0;
num1 = arr[0];
num2 = arr[1];
if(num1 > num2)
{
max1 = num1;
max2 = num2;
}
else
{
max1 = num1;
max2 = num2;
}
for(i=2;i<len;i++)
{
temp = arr[i];
if(temp > max1 && temp > max2)
{
max2 = max1;
max1 = temp;
}
else if(temp < max1 && temp > max2)
{
max2 = temp;
}
}
printf("1st max = %d, 2nd max= %d\n", max1,max2);
return max2;
}
int main(void)
{
const unsigned int x[] = { 5, 3, 8, 6, 0, 7 };
printf("Array: ");
int i;
const int nx = sizeof x/sizeof(int);
for (i = 0; i < nx; i++)
printf("%d ", x[i]);
printf("\nSecond largest: %d\n", secondlargest(x, nx));
return 0;
}
/*
Find the second largest integer in an array of integers.
*/
#include <stdio.h>
int
secondlargest(const unsigned int *x, int nx)
{
/* Find the max, then go through the array one
more time to find the second largest.
*/
unsigned int max = x[0];
int i;
for (i = 1; i < nx; i++)
if (x[i] > max)
max = x[i];
/* Find an element other than the max to start
with. If none found, every element is the same.
*/
for (i = 0; i < nx; i++)
if (x[i] < max)
break;
unsigned int secondmax;
if (i == nx)
return -1;
else
secondmax = x[i];
/* Now compare to find the max but ignore max itself */
for (i++; i < nx; i++)
if (x[i] == max)
continue;
else if (x[i] > secondmax)
secondmax = x[i];
return secondmax;
}
int
main(void)
{
const unsigned int x[] = { 5, 3, 8, 6, 0, 7 };
printf("Array: ");
int i;
const int nx = sizeof x/sizeof(int);
for (i = 0; i < nx; i++)
printf("%d ", x[i]);
printf("\nSecond largest: %d\n", secondlargest(x, nx));
return 0;
}
int max1=a[0],max2=a[0];
for(int i=1;i<a.length;i++)
{//First Approach
/* if(a[i]>max1)
{
max2=max1;
max1=a[i];
}
else if(a[i]>max2)
{
max2=a[i];
}*/
//Second approach
if(a[i]>max2)
{
max2=a[i];
}
if(max2>max1)
{//swap max1 and max2
max2=max2^max1;
max1=max2^max1;
max2=max2^max1;
}
}
System.out.println("Largest number"+max1);
System.out.println("Second Largest Number"+max2);
This will not work when first element of the array is largest number. Because you are initializing max1 and max2 with a[0] which in this will be max number. Let's say array={115,10,6,80,15,9,12}, So max1=115 and max2=115 will be initialize in first step after that max2 will never be initialize with 80.
public class secondMax {
public static void main(String args[]) {
//int arr[] = {7,5,2,7,9,8};
//int arr[] = {8,5,2,7,7,9};
int arr[] = {9,5,2,7,7,8};
int max2 = 0;
int max=arr[0];
for(int i=1; i<arr.length; i++) {
if (arr[i] > max) {
max2 = max;
max = arr[i];
}
else if (arr[i] > max2) {
max2 = arr[i];
}
}
System.out.println("Max : " + max);
System.out.println("2nd Max : " + max2);
}
};
public class SecondLargestInIntArray {
public static void main(String[] args) {
int a[] = {9,1,9,2,8,4,1,9,0,0};
int mMax,mSecMax;
mMax = a[0];
mSecMax = 0;
for (int i=1;i<a.length;i++){
//if the current int in array is > mMax, set mMax to max value
//set mSecMAx to the previous value of mMax as that will the second largest so far
if(a[i]> mMax){
mSecMax = mMax;
mMax = a[i];
}//if the first element of the array is the largest,above if condition will never be enetered
//So,mSecMax will remain as 0 which is not the desired result.
//any value that is < mMax and > current mSecMax will be assigned to mSecMax
else if((a[i]> mSecMax) && (a[i] != mMax)){
mSecMax = a[i];
}
}
System.out.println("Second Largest value : " + mSecMax);
}
}
/**
*
* @param input the input array, which should contains more than 1 element
* @return the index in the array which is the second largest element. -1 means an error
*/
public static int findSecondLarge(int[] input){
int max=0,max2=1;
int temp;
if(input==null || input.length< 2){
return -1;
}
if(input[max]<input[max2]){
temp=max;
max=max2;
max2=temp;
}
for(int i=2;i<input.length;i++){
if(input[i]>input[max]){
max2=max;
max=i;
}else if(input[i]>input[max2]){
max2=i;
}
}
return max2;
}
private void getSecondHighestNumber(int [] arr) {
// TODO Auto-generated method stub
int []temp = new int[2];
temp[0] = arr[0];
temp[1]=arr[1];
for (int i = 2; i < arr.length; i++) {
if(arr[i]>temp[0] && arr[i]>temp[1])
{
int k = arr[i] - temp[0];
int l = arr[i] - temp[1];
System.out.println("l="+l+"=k="+k);
if(k>l)
temp[0] = arr[i];
if(k<l)
temp[1] = arr[i];
}else if(arr[i]>temp[0] && arr[i]<temp[1]){
temp[1] = arr[i];
}else if(arr[i]<temp[0] && arr[i]>temp[1]){
temp[0] = arr[i];
}
}
System.out.println("=========="+temp[0]+"======"+temp[1]);
}
This can be done by Tournament selection algorithm..
Compare 2 elements at a time. And get the maximum.
Now amongst the elements which were compared with maximum, find the largest element. That will be the second maximum element.
But i am not sure how to efficiently implement this algo
Any thoughts on this?
int returnSecondLargestFromArray(int a[],int size) {
int indx;
int max = a[0];
int secondMax = a[0];
if (size == 1)
return 0;
for (indx = 1 ; indx < size; indx++) {
if (a[indx] > max) {
secondMax = max;
max = a[indx];
} else if ((secondMax == max && a[indx] < secondMax) || a[indx] > secondMax) {
secondMax = a[indx];
}
}
return 0;
}
Just realized that I submitted an incomplete version, this one should work:
void returnSecondLargestFromArray(int a[],int size,int &max, int &secondMax) {
int indx;
if (size <= 1)
return;
max = a[0];
secondMax = a[0];
for (indx = 1 ; indx < size; indx++) {
if (a[indx] > max) {
secondMax = max;
max = a[indx];
} else if ((secondMax == max && a[indx] < secondMax) || a[indx] > secondMax) {
secondMax = a[indx];
}
}
return;
}
max1=a[0]
max2=0
for i=1 to n
if a[i] > max1
max2=max1
max1=a[i]
else if a[i] > max2 && a[i] != max1
max2=a[i]
return max2
Use randomize selection to find the 2nd largest element i.e. element at N-1 th position.
- Punit Jain April 22, 2012solution 2.
int max1, max2 = 0;
for i = 1 to N
if (A[i] > max2)
max2 = A[i]
if (max2 > max1)
swap (max1, max2)
return max2