## Adobe Interview Question for Software Engineer / Developers

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

Use Randomized-Select to find nth max element in O(N) time where N=number of elements

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

@Sriram Correct. Also, Median of Medians algorithm has worst case linear time where Randomized-Select is not...

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

The algorithm is based on slight modification to quick sort & is of time complexity log(n).

1. select an element r randomly from the array.
2. partition the array into 2 halves, left & right such that left have elements less than or equal to the selected element r and right has elements of higher value than r.
3. now count the number of elements in left.
4. if n = size(left) return element r.
5. else if n < size (left) repeat the process on left array and ignore the right array elements.
6 else if n > size (left), ignore left array & randomly selected element r and repeat the process on right array to fine the element of order [n - size(left) - 1]. (-1 for randomly selected element).

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

nice approach !!

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

how can this be O(logn)? partitioning and arranging the elements so that left is less than r and right is greater than r, would on an average be of O(n). so the total complexity would be O(n.logn)

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

I think the solution is really nice and the complexity is O(n).
Please point out if you find any mistakes.

Since the number to choosen is random number about which we have to partition the array.On an average we can assume that,choosing this random number leads to two arrays with half no. of elements every time.
And for worst case we can assume that we only found the nth element when we had only a single element in the array.
Suppose that there are k elements initially,

Initially,
k elements -----to partition we need k comparisions which leads to 2 arrays of k/2 elements.

k+k/2 (k/2 comparisions in the array of k/2 elements)
k+k/2+k/4 (k/4 comparisions for array of k/4 elements)

k+k/2+k/4+k/8+........k/2(power i) ,where k=2(power i) since we assumed that we found nth element when we had only single element in array
k(1+1/2+1/4+1/8+.....1/2(power i))
k(1-1/2(power i)/(1-1/2)
2k(2(power i)-1)/2(power i)
2k(2(power i)-1)/k
2(k-1)
O(k)

generally O(n),where n is size of problem

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

it's time complexity is O(n^2) in worst case

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

i think ur code is wrong

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

awesome thought....but any one pls explain time complexity of this program in detail.

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

using quicksort for finding nth largest value.
Here is a working c code

#include "stdio.h"
#include<conio.h>
using namespace std;
int quicksort ( int *, int, int, int ) ;
int split ( int*, int, int ) ;

int main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
int nth = 5; //finding 5th largest value
int num =  quicksort ( arr, 0, 9, nth-1 ) ;
printf ( "%d\t", num ) ;
getch();
return 0;
}

int quicksort ( int a[ ], int lower, int upper, int nth)
{
int i ;
if ( upper > lower && i !=nth )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1, nth ) ;
quicksort ( a, i + 1, upper,nth ) ;
}
return a[nth];
}
int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;
p = lower + 1 ;
q = upper ;
i = a[lower] ;
while ( q >= p )
{
while ( a[p] < i )
p++ ;
while ( a[q] > i )
q-- ;
if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}
t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;
return q ;
}

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

The solution that comes instantly to the mind is sort the array and then traverse the sorted array ignoring repetion of elements in the array while counting.

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

Not the most optimal solution as sorting would require nlog(n) time. The optimal solution is in log(n) time.

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

Impossible to solve in logn time if array is nt sorted.

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

int FindNthMaximum(int arr[],size_t size,int n)
{
if(arr == NULL || size == 0 || n < 1 ||  n > size) return -1;
int max = 0,tmp=0;
int *a = new int[size];
memcpy(a,arr,size*sizeof(int));
for(int i = 0;i<n;++i)
{
max = i;
for(int j=i+1;j<size;++j)
{
if(a[j] > a[max] ) max = j;
}
if(i + 1 == n)
{
tmp = a[max];
delete []a;
a = NULL;
return tmp;
}
tmp = a[i];
a[i] = a[max];
a[max] = tmp;
}
return 0;

}

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

Use heap to get nth element.. If array has m elements and we have to get nth largest.. then it will cost [m + n log m]. it will be better than sorting array approach [m log m] because n < m.

If we create min-heap of only n elements, then it will cost [n + m log n]

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

use selection sort and just make the enclosing loop n times is ok! and bubble sort in the same way…

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

@dheeraj123
Thanks

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

This is code for quickselect ( similar technique used by quicksort )

void swap( int *input, int a, int b)
{
int temp;
temp = input[a];
input[a] = input[b];
input[b] = temp;
}

int GetPivot(int *input, int beg, int end )
{
int pivot;
int middle = (beg + end)/2;
if ( input[beg] <= input[end] && input[beg] >= input[middle] )
pivot = beg;
else if (input[end] <= input[beg] && input[beg] >= input[middle])
pivot = end;
else
pivot = middle;
swap(input, pivot, end ); /* put pivot at end */
return　input[end];
}
int QuickSelect ( int *input, int beg, int end, int k )
{
// 1 choose the pivot by median of 3
int pivot = GetPivot( input, beg, end );
swap(input, pivot, end ); /* put pivot at end */

// 2 move elements
int i = beg;
int j = end – 1;
while( 1 )
{
while( input[i] <= pivot )
i++;   // move right until meet some one > pivot
while( input[j] >= pivot)
j--; // move left until meet some one < pivot
if ( i < j )
swap(input, i, j );
else
break;
}
swap(input, i, end ); // put pivot back

// 3 select recursively
if ( end – i > k - 1 )
return ( input, i + 1, end, k );  // the kth is in the second half
else if ( end – i == k – 1)
return input[i];	   // the kth is the one
else
return (input, beg, i – 1, k -1 –(end – i ) ); // the kth is in  the first half
}

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

Can you please tell me whether your implementation contains the randomised quick sort algorithm...?

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

findNthMax(a[],n)
{
if(a.length<n)
{
throw new Exception("No Sufficient Data");
}else
{
Queue q;
for(int i =0; i<a.length;i++)
{
if(a[i] >= q.peek(q.front))
{
if(q.isEmpty() || q.size() ! = n)
{
q.insert(a[i]);
}else{
q.delete();
q.insert(a[i]);
}
}
}
SOP("nth largest element:::" + q.delete());
}

}

Its O(n)

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

package arrays;

/**
* Returns the kth largest element in the array of elements
* Uses partitioning (order statistics) technique to arrive
* at kth element.
*
* Usage: Kth largest element returned will be the element at index
* k-1;
*
*/
public class KthLargest {

public static void main(String[] args) {
int a[] = { 1, 6, 2, 9, 13, 5, 3, 8 };
int k = 7;
int index = findKth(a,0, a.length -1, k);
System.out.println(k+ "th largest element: "+ a[index]);

}

private static int findKth(int[] a, int low, int high, int k) {

int partitionIndex = partition(a,low,high);
if( k == partitionIndex - low) {
return partitionIndex;
} else if(k < partitionIndex){
return findKth(a, low, partitionIndex-1, k);
} else if(k> partitionIndex) {
return findKth(a, partitionIndex+1, high, k-(partitionIndex+1));
}
return partitionIndex;
}

private static int partition(int[] a, int low, int high) {
if(low<high){
int pIndex = Math.abs((low + high) / 2);
int pivot = a[pIndex];
swap(a, pIndex, high);

int i = low;
int j = high - 1;
while (i <= j) {
while (i < high && a[i] <= pivot) {
i++;
}
while (j >= low && a[j] >= pivot) {
j--;
}
if (i < j) {
swap(a, i, j);
i++;
j--;
}
}
swap(a, i, high);
return i;
} else {
return low;
}
}

private static void swap(int[] a, int i, int pIndex) {
int t = a[i];
a[i] = a[pIndex];
a[pIndex] = t;

}

}

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.