## Adobe Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

max and second maxinum can be found in just O(n).
here is the code.

#include<iostream>
using namespace std;
int main()
{
vector<int> v;
int array[]={0,4,1,8,2,3,7,5,6};
int max1=0,max2=0;
for(int i=0;i<9;++i)
{
if(max1<array[i])
max1=array[i];
if(max2<array[i]&&array[i]<max1)
max2=array[i];
}
cout<<max1<<" "<<max2<<"\n";
system("pause");
return 0;
}

Comment hidden because of low score. Click to expand.
0

when you change max1 you need to check if the previous value of max1 should substitute the current value of max2

Comment hidden because of low score. Click to expand.
1
of 1 vote

sorry for vector<int> v. it's not needed

Comment hidden because of low score. Click to expand.
1
of 1 vote

simple code for the second largest value.

``````#include "stdio.h"
#include<conio.h>
using namespace std;
int main()
{
int a[10] = { 11, 2, 9, 13, 33, 25, 17, 1, 90, 3 } ;
int fmax = 0; int smax = 0;
for(int i=0; i<10;i++)
{
if(a[i]>fmax)
{
smax=fmax;
fmax=a[i];
}
else if (smax<a[i])
smax = a[i];
}
printf("%d, %d", fmax, smax);
getch();
return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

The question asks about finding second maximum in minimum number of comparisons. It doesn't asks about minimum complexity, which is ofcourse O(n). Minimum number of comparisons for second max. element are N - 2 + logN .
stackoverflow.com/questions/9889679/find-second-largest-number-in-array-at-most-nlog2n2-comparisons

Comment hidden because of low score. Click to expand.
0

hey it is a very neat and concise solution can you explain the logic.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can sort using some O(nlogn) algorithm like heapsort by making a maxheap and find the max number .

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting is not required if we have to find just the maximum or minimum number. Here's how we can achieve that:
1. Have two var - max, min - initialized to the first element.
2. Compare each subsequent element with max and min.

if (a[i]>max)
max=a[i];
else if (a[i]<min)
min=a[i];

Comment hidden because of low score. Click to expand.
0

@Algo,
Your approach is correct, but how will you find the second largest number?
Using your approach, one can find maximum number in (n-1) comparisons.

Comment hidden because of low score. Click to expand.
0

Make heap of two elements. with this u can achieve in o(n). also we can use two variables for two elements.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Max: n-1.
Max + second Max: n + logn -1.

Comment hidden because of low score. Click to expand.
0

Algorithm?

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

Take two variables max, secondMax and iterate the array initializing both to the first element. if an item is greater than max then update secondMax to max to new max value. If the item is greater than secondMax, update secondMax to that value. When all items are enumerated, secondMax shall contain secondMax value.

Comment hidden because of low score. Click to expand.
0

what if the first element is the maximum..
like 5,3,4,2,1
now sec_max and max will contain ly d same value

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

the whole problem of finding largest and second largest element can be found out by (n+logn) steps.
Here is the procedure:

First make all the elements of the array as leaf nodes. consider pair of elements and make the larger one as the parent and continue further until u get a single element which is largest.

Now that we got the largest element in (n/2) + (n/4) + . . . + 1 = (n - 1) steps
and also we have build a binary tree...

Now the second largest element should be somewhere compared with the largest element as it would become the parent with every other element except with the largest.

Thus by following the comparisions of the largest element along the branch we can find the second largest element in (log n) steps...

Please correct me if I am wrong.

Comment hidden because of low score. Click to expand.
0

(n/2) + (n/4) + . . . + 1 = (n - 1) ???
we are traversing all the element cost o(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

the whole problem of finding largest and second largest element can be found out by (n+logn) steps.
Here is the procedure:

First make all the elements of the array as leaf nodes. consider pair of elements and make the larger one as the parent and continue further until u get a single element which is largest.

Now that we got the largest element in (n/2) + (n/4) + . . . + 1 = (n - 1) steps
and also we have build a binary tree...

Now the second largest element should be somewhere compared with the largest element as it would become the parent with every other element except with the largest.

Thus by following the comparisions of the largest element along the branch we can find the second largest element in (log n) steps...

Please correct me if I am wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you code it?

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey38946" class="run-this">#include<iostream.h>

int main()
{
int a[10],i,j,max,sec; // creates as many ints as necessary
for (i = 0; i <10; i++)
{
cin >> a[i];
// until the array is full
}
max=sec=a[0];

for (int j =1; j <10; j++) // loop to print the stars for each array

{
if(a[j]>max)
{sec=max;
max=a[j];
}
else if(a[j]>sec)
sec=a[j]; // value

}

cout<<sec<<endl;
getch();
return 0;

}

</pre><pre title="CodeMonkey38946" input="yes">
</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry for vector<int> v. it's not needed

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tournament tree -> if both max, and 2nd max are required -> O(n + logn)
nth largest element -> quickSelect -> O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Make a Mx-heap from the given array
2) O(1) to get the Max number.
3) Second largest element is one of the child of root node of heap.
4) Only one comparison is needed to find the second largest number

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
using namespace std;
int main() {
int n,i;
cout << "Enter the size of array: ";
cin  >> n;

int a[n];
cout<<"\nEnter the elements in array: \n";
for(i=0;i<n;i++) cin>>a[i];

int f=0;
int s=1;

if(a[s]>a[f]){
int temp=f;
f=s;
s=temp;
}

for(i=1;i<n;++i) {

if( (a[i]>a[f]) && (a[i] > a[s]) ) {
s=f;
f=i;
}
if(a[i]<a[f] && a[i]>a[s] )
s=i;
}
cout<<"\nSecond highest: "<<a[s]<<endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*max and second maxinum can be found in just O(n).*/

#include<iostream>
using namespace std;
int main()
{
int n,i;
cout << "Enter the size of array: ";
cin  >> n;
int a[n];
cout<<"\nEnter the elements in array: \n";

for(i=0;i<n;i++) cin>>a[i];
int f=0;
int s=1;
if(a[s]>a[f])
{
int temp=f;
f=s;
s=temp;
}
for(i=1;i<n;++i)
{
if( (a[i]>a[f]) && (a[i] > a[s]) )
{
s=f;
f=i;
}
if(a[i]<a[f] && a[i]>a[s] )
s=i;
}
cout<<"\nSecond highest: "<<a[s]<<endl;
cout<<"\nFirst Highest : "<<a[f]<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

easiest and correct Algo.. good one Anand

Comment hidden because of low score. Click to expand.
0
of 0 vote

Finding max min and sec_max in O(n) time

#include <iostream>
#include <stdlib.h>
#define SIZE 50
using namespace std;

int main()
{
int max, min, sec_max,n;
int arr[SIZE];
int i;
cout<<"Enter no. of element\n";
cin>>n;
for(i = 0; i < n; i++)
cin>>arr[i];
if(n > 1)
{
sec_max = arr[0]>arr[1]?arr[1]:arr[0];
}
max = min = arr[0];
for(i = 1;i < n; i++)
{
if(arr[i] > max)
{
sec_max = max;
max = arr[i];
}
if(arr[i] < min)
min = arr[i];
}
cout<<max<<" "<<sec_max<<" "<<min;
getchar();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't comment to @nihaldps so writing a new post.

fmax --maximum element in the array.
smax --second maximum element in the array.

Your solution fails for all negative elements in the array. So always initialise fmax and smax with a[0].

Suppose,a[0] is the greatest element in the array then,the number of comparisions that your code does is 2(n-1).Since from index=1 to n-1 every element will be compared to fmax and then to smax also.

This question can have a better solution.

We can find the fmax in n-1 comparisions.
For finding the second maximum element, we are sure that at any point of time second maximum element should have been compared with maximum element.So if somehow we can keep information that which all elements have been compared with maximum elements. We can find maximum of those which would be the second maximum element.

Prepare a decision tree as follows,
Compare a0 with a1, a2 with a3, a4 with a5......and so on.
then keep on going with winners among those.
We come to know that number of elements which get compared with maximum element is log(n) ------height of decision tree.
So now we can compute max from these in log(n)-1 comparisions.

So total no. of comparisions= n-1+log(n)-1=n+logn-2

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use the divide and conquer method (Tournament Method) to find the maximum and second maximum in O(n) time

Comment hidden because of low score. Click to expand.
0

@Luv, i think Tournament tree takes (3xN/2)-1 comparisons.

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do both in jus N-1 steps:
int large=0,sec_large=0;
for(i=0;i<N;i++)
if(arr[i]>large)
{ small=large;
large=arr[i];
}
else if(arr[i]<large&& arr[i]>sec_large)
sec_large=arr[i];

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ThirdLargestNumber {
public static void main(String[] args) {
int arr[] = { 200, 200, 100, 100, 300,600 };
int first = 0, second = 0, third = 0, temp = 0, temp1 = 0;
for (int i = 0; i <= 5 /*
* Length of array-1. You can use here length
* property of java array instead of hard coded
* value
*/; i++) {

if (arr[i] == first) {
continue;
}
if (arr[i] > first) {
temp = first;
temp1 = second;
first = arr[i];
second = temp;
if (temp1 > third) {
third = temp1;
}
} else {
if ((arr[i] == second) || (arr[i]) == first) {
continue;
}
if ((arr[i] > second) && (arr[i]) < first) {
temp1 = second;
second = arr[i];
if (temp1 > third) {
third = temp1;
}
} else {
if (arr[i] > third) {
third = arr[i];
}
}
}
}
System.out.println("Third largest number: " + third);
System.out.println("Second largest number: " + second);
System.out.println("Largest number: " + first);
}

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.