Delivered instantly as a PDF via email. For Software Engineers & SDETs
150 programming interview questions and answers
5 proven approaches to crack algorithm questions
10 mistakes candidates make, and how to avoid them.
How to prepare for technical and behavioral questions without wasting your time!
"The BEST book for acing your interview. It helped me land my Microsoft job, and it was worth every penny!" - Ravi (Accepted at Microsoft, Amazon and Facebook)
30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!More Info
Saturday, April 24, 2010
Second largest elemen
Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
This does not work if array has the largest element as the first element e.g. 9,4,6,3,8,7 max1 and max2 both initialized to 9 no further processing happens both remain equal to 9.
Breaks for array a = { 9, 1, 2, 3 }; I think the ideal way is the quick-select, doing a O(n) compares. It works like quick sort, but breaking array into parts such that one of them is size k where k is the kth largest elem to be found
max1=a[0];
ReplyDeletemax2=a[0];
for(i=1;i<6;i++)
{
if(a[i]>max1)
{
max2=max1;
max1=a[i];
}
else if(((a[i]max2)
max2=a[i];
}
printf("MAx1=%d\t",max1);
printf("Max2=%d\t",max2);
what if a[i] is equal to max1? The code would assign max2 equal to a[i]
ReplyDeleteThis does not work if array has the largest element as the first element
ReplyDeletee.g. 9,4,6,3,8,7
max1 and max2 both initialized to 9
no further processing happens
both remain equal to 9.
int Arr[10] = { 1, 4,2,6,4,2,3,7,2,7};
ReplyDeleteint max1, max2;
max1 = max2= Arr[0];
for(int i = 1; i < 10; i++)
{
if(Arr[i] > max1)
{
max2 = max1;
max1 = Arr[i];
}
else if (Arr[i] < max1 && Arr[i] > max2)
max2 = Arr[i];
}
Nice Solution
Deletethis will work :)
U just need to have an else block (which can be empty) to make it run
//initialize b[] with all 0's first
ReplyDelete//let a[] be your i/p array..
for(i=0;i<=n;i++)
{
b[a[i]]=1;
}
for(j=0;j<=n+1;j++)
{ if(b[j]!=1)
printf("%d",b[j]);
}
Time: n.
largest = Arr[0];
ReplyDeletes_largset = Arr[1];
for(int i = 1; i < N ; i++)
{
if(Arr[i] > largest)
{
s_largest = largest;
largest = Arr[i];
}
else if (Arr[i] > s_largest)
s_largest = Arr[i];
}
Breaks for array a = { 9, 1, 2, 3 };
ReplyDeleteI think the ideal way is the quick-select, doing a O(n) compares.
It works like quick sort, but breaking array into parts such that one of them is size k where k is the kth largest elem to be found
int SecondMinElement(int arr[],int n) {
ReplyDeleteint max1 = 0, max2 = 0;
if(n > 1) {
max1 = arr[0], max2 = arr[1];
for(int i=2; i<n; i++) {
if(max1 < arr[i]) {
max2 = max1;
max1 = arr[i];
} else if (max2 < arr[i]) {
max2 = arr[i];
}
}
}
return max2;
}
int a[8]={10,5,6,7,8,9,6,8,1};
ReplyDeleteint max1, max2;
max1=max2=0;
int i;
for(i=0;i<8;i++)
{
if(a[i] > max1){
max2=max1;
max1=a[i];
}
else if(a[i] <= max1 && a[i] > max2)
max2=a[i];
}