Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)
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.

10 comments:

  1. max1=a[0];
    max2=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);

    ReplyDelete
  2. what if a[i] is equal to max1? The code would assign max2 equal to a[i]

    ReplyDelete
  3. 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.

    ReplyDelete
  4. int Arr[10] = { 1, 4,2,6,4,2,3,7,2,7};

    int 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];
    }

    ReplyDelete
    Replies
    1. Nice Solution
      this will work :)

      U just need to have an else block (which can be empty) to make it run

      Delete
  5. //initialize b[] with all 0's first
    //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.

    ReplyDelete
  6. largest = Arr[0];
    s_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];
    }

    ReplyDelete
  7. 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

    ReplyDelete
  8. int SecondMinElement(int arr[],int n) {
    int 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;
    }

    ReplyDelete
  9. int a[8]={10,5,6,7,8,9,6,8,1};
    int 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];
    }

    ReplyDelete