Amazon Interview Question Software Engineer in Tests
Country: United States
Interview Type: Phone Interview
And what if we need to return n-th max value (i.e. return the smallest one) in this case it would be definitely not O(n).
Selection search will work, but with square time complexity.
Good one. +1 for you Subhajit. It is just that in order to find nth maximum number, you need to find M-(n-1)st order statistic in quick-select algorithm. Here M is the total number of elements in the array. That should address J's concern as well.
Yes we can do as @Dumbo has said, or may be just reverse the sign in the partition function and get the nth Maximum.
#include <stdio.h>
void swap(int a[], int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int partition(int a[], int left, int right)
{
int pivot = (left+right)/2;
int element = a[pivot];
int copy = right;
swap(a, pivot, right);
right--;
while(left < right){
while(a[left] > element)
left++;
while(a[right] < element)
right--;
if(left < right)
swap(a, left, right);
}
swap(a, left, copy);
return left;
}
int q_s(int a[], int left, int right, int k)
{
if(left < right) {
int pivot = partition(a, left, right);
if(pivot == k) {
printf("found it\n");
return a[pivot];
}
if(pivot < k)
q_s(a, pivot+1, right, k);
else
q_s(a, left, pivot-1, k);
}
}
int main()
{
int i;
int a[] = {2, -4, 5, 6, 0, 7, -1, 10, 9};
int k = 2; //if you want to find out 1 largest then give 0
printf("%d\n", q_s(a, 0, sizeof(a)/sizeof(a[0]) -1, k));
}
@aka
Good one. one upvote from me. Did you test for all scenarios? I suspect there is a bug lurking though....I suppose that the following modification should be made
if(pivot < k)
q_s(a, pivot+1, right, k-pivot);
else
...
private static int partition(int[] arr, int left, int right, int pivotIndex) {
int pivot = arr[pivotIndex];
//Move pivot to the end
arr[pivotIndex] = arr[right];
arr[right] = pivot;
int newIndex = left;
for(int i = left; i < right; i++) {
if(arr[i] >= pivot) {
//swap arr[i] with arr[newIndex]
int temp = arr[newIndex];
arr[newIndex] = arr[i];
arr[i] = temp;
newIndex++;
}
}
//Move pivot to its position
int temp = arr[right];
arr[right] = arr[newIndex];
arr[newIndex] = temp;
return newIndex;
}
private static int select(int[] arr, int left, int right, int n) {
if(left == right) return arr[left];
int pivotIndex = left + (right - left)/2;
int newPivotIndex = partition(arr, left, right, pivotIndex);
int newPivotDistance = newPivotIndex - left + 1;
if(newPivotDistance == n) return arr[newPivotIndex];
else if(newPivotDistance > n) return select(arr, left, newPivotIndex -1, n);
else return select(arr, newPivotIndex + 1, right, n - newPivotDistance);
}
Using a min-heap of size n as ashot has mentioned already. I am merely providing Java code to illustrate the idea.
static int nthMax(int[] arr, int n) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
for(int i : arr) {
heap.add(i);
if(heap.size() > n)
heap.poll();
}
return heap.poll();
}
quick-select algorithm can do this in O(n) time and O(1) space. Why is the heap solution better than @subahjit's solution?
Because the quick-select algorithm is harder to implement correctly? I think if the candidate can code the heap solution up, then that might be good enough already for a phone interview. The interviewer might press for the quick-select algorithm, at which point you can then offer a verbal explanation.
But of course that's just me. Other people can code something like this fluently.
If there is a reasonable cap to the values (e.g. they are all integers in the range of 0-1000000) you can use a bit vector, toggling the appropriate bit for each value you see, and then simply traverse the bit vector to find the nth toggled bit. That'll work in O(N).
Else, the heap approach already mentioned for O(N * log(K)).
Here is my java solution. It is essentially the quick select algorithm used to find the kth largest number in an unsorted array. The algorithm assumes all elements in the array are unique (no duplicates). I also added the code to show the kth smallest element (commented out). I recommend not committing the code itself to memory, but rather working the algorithm out on paper until you understand the way the algorithm works.
public class findkthelement {
public static int selectKthLargest(int[] arr, int k) {
//ensure k is valid
if (k < 1 || k > arr.length){
return -1;
}
return findKthLargest(arr, 0, arr.length-1, k);
}
public static int findKthLargest(int[] nums, int start, int end, int k){
int pivot = start;
int left = start;
int right = end;
while (left <= right){
while (left <= right && nums[left] <= nums[pivot])
++left;
while (left<= right && nums[right]>= nums[pivot])
--right;
if (left < right){
swap(nums, left, right);
}
}
swap(nums, pivot, right);
/* code to find the kth largest element */
if (k == nums.length - right)
return nums[right];
else if (k > nums.length -right)
return findKthLargest(nums, start, right-1, k);
else
return findKthLargest(nums, right+1, end, k);
/****** code to find the kth smallest element --
* put here to show the slight difference between returning kth smallest
* and kth largest
if (k == right+1)
return nums[right];
else if (k > right+1)
return findKthLargest(nums, right+1, end, k);
else
return findKthLargest(nums, start, right-1, k);
*/
}
private static void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public static void main(String[] args) {
int[] array = {2, -4, 5, 6, 0, 7, -1, 10, 9};
int k = 6;
System.out.print("{"+ array[0]);
for (int i = 1; i < array.length;++i)
System.out.print(", " + array[i]);
System.out.println("}");
System.out.println(k+"th largest element: " + selectKthLargest(array, k));
System.out.print("{"+ array[0]);
for (int i = 1; i < array.length;++i)
System.out.print(", " + array[i]);
System.out.println("}");
}
}
var input = [2, -4, 5, 6, 0, 7, -1, 10, 9];
var maximums = [];
var nth = 3;
for (var index = 0; index < input.length; index++) {
if (maximums.length > 0) {
for (var maxIndex = 0; maxIndex < maximums.length && maxIndex < nth; maxIndex++) {
if (maximums[maxIndex] < input[index]) {
maximums.splice(maxIndex, 0, input[index]);
maximums.length = nth;
break;
}
}
} else {
maximums.push(input[index]);
}
}
var result = maximums[nth];
#include<stdio.h>
#include<conio.h>
int ele;
int returnNthMax(int *p,int k)
{
return p[ele-k];
}
int main()
{
int *p;
int i,j=0,k=0,temp=0,max=0;
printf("\nHow many elements ?? ");
scanf("%d",&ele);
printf("\nEnter elements : ");
p=(int *)malloc(sizeof(int)*ele);
for(i=0;i<ele;i++)
{
scanf("%d",&p[i]);
}
for(i=0;i<ele;i++)
{
for(j=0;j<ele-(i+1);j++)
{
if(p[j] > p[j+1])
{
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}
printf("\nwhich maximum you want ? ");
scanf("%d",&k);
max=returnNthMax(p,k);
printf("\nkth max is : %d",max);
getch();
return 0;
}
This solution is same as @braap 's solution. It finds the kth largest number by using divide and conquer technique. This technique is similar to partition technique of quick sort. But we shall follow the partition where the kth largest element is. Hence the time complexity is O(k log n).
@braap I have just coded it a bit different way
public class KthMax {
public static void main(String args[]) {
// int arr[] = { -2, 1, 5, 3, -10, 20, 4 };
int arr[] = { -10, -2, 1, 3, 4, 5, 20 };
for (int i = 1; i <= arr.length; i++)
System.out.println(kthMax(arr, 0, arr.length - 1, i));
}
public static int kthMax(int arr[], int st, int end, int k) {
// base cases for recursion
if (st >= end)
return arr[st];
// recursion
int pivot = arr[end];
int i = st, j = end;
int temp;
while (i < j) {
// move right until we find something greater than pivot
while (arr[i] < pivot)
i++;
// move left until we find something less than or equal to pivot
while (arr[j] > pivot)
j--;
if (i < j) {
// swap
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
} else if (i == j)
j--;
}
if (k > end - j)
return kthMax(arr, st, j, k - (end - j));
else
return kthMax(arr, i, end, k);
}
}
applying a simple bubble sort seems to be more simpler. Here is the code in C#
static void Main(string[] args)
{
FindNthLargestNumber();
}
static void FindNthLargestNumber()
{
var nthLargestNumber = int.Parse(Console.ReadLine());
var array1 = new int[] {2, -4, 5, 6, 0, 7, -1, 10, 9};
BubbleSort(array1);
Console.WriteLine("Nth number is {0}", array1[(array1.Length-1) -( nthLargestNumber - 1)]);
}
private static void BubbleSort(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
for (var j = i+1; j < arr.Length; j++)
{
if (arr[i] > arr[j])
{
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
static int returnNthMax(int[] arr, int nTh)
{
int lastmax = int.MaxValue;
if(arr.Length < nTh)
return -1;
for (int j = nTh - 1; j >= 0; j--)
{
int localMax = int.MinValue;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > localMax && arr[i] < lastmax)
{
localMax = arr[i];
}
}
lastmax = localMax;
}
return lastmax;
}
use randomized selection algorithm.
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
void swap(int*,int*);
int partition(int*,int,int);
int rselect(int*,int,int,int);
int main()
{
int n,i;
ifstream fin("input9.txt");
fin>>n;
int *a=new int[n];
for(int i=0;i<n;i++)
fin>>*(a+i);
cout<<"Enter the order statistic you want to find\n";
cin>>i;
int stat=rselect(a,0,n-1,i-1);
cout<<"The "<<i<<"th order statistic is = "<<stat<<endl;
return 0;
}
void swap(int* a,int* b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int partition(int* a,int p,int r)
{
int j=p+1;
for(int k=p+1;k<=r;k++)
{
if(*(a+k)>*(a+p))
swap(a+k,a+j++);
}
swap(a+j-1,a+p);
return j-1;
}
int rselect(int* a,int p,int r,int i)
{
if(p>=r)
return *(a+r);
else
{
int m=partition(a,p,r);
if(m-p==i)
return *(a+m);
else if(m-p>i)
return rselect(a,p,m-1,i);
return rselect(a,m+1,r,i-m+p-1);
}
}
The Random Select algorithm can lead to the worst-case O(n^2) complexity if the pivot element happens to be the largest in many iteration, but in average it is O(n). In contrast, Median of Medians guarantees the worst-case complexity of o(n).
We can still do better by constructing a RB-Tree to achieve O(lg n) complexity. The pseudo code is as follows:
struct RBTree *Select_ith_Max(struct RBTree *b, int i)
{
if(b==NULL)
return NULL;
range=b->leftChild->size+1; //it gives the number of elements that precede b in an inorder-traversal of the RBTree
if(r==i)
return b;
if(r>i)
return RBTree *Select_ith_Max(b->leftChild,i);
return RBTree *Select_ith_Max(b->rightChild,i-r);
}
The value i passed to this function upon its invocation should be (n-(i-1)) -or simply n-i if array representation is used - for function to return the ith max value, where n is total number of elements in the tree.
public class MaxNumber {
public static void main (String[]args){
System.out.println("Enter the array length: ");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Integer> marks = new ArrayList<Integer>();
System.out.println("Enter the element of the array: ");
for (int i=0; i<n; i++){
marks.add(sc.nextInt());
}
Collections.sort(marks);
System.out.print("Original contents of al: ");
Iterator itr = marks.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
System.out.println();
System.out.println("Enter the number: ");
int num = sc.nextInt();
for (int i =marks.size()-1; i>num; i--){
System.out.println(marks.get(i));
}
}
public class MaxNumber {
public static void main (String[]args){
System.out.println("Enter the array length: ");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Integer> marks = new ArrayList<Integer>();
System.out.println("Enter the element of the array: ");
for (int i=0; i<n; i++){
marks.add(sc.nextInt());
}
Collections.sort(marks);
System.out.print("Original contents of al: ");
Iterator itr = marks.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
System.out.println();
System.out.println("Enter the number: ");
int num = sc.nextInt();
for (int i =marks.size()-1; i>num; i--){
System.out.println(marks.get(i));
}
}
public class NthMaxArray {
public static void findNthMax(int arr[], int n) {
List<Integer> list = Ints.asList(arr);
Collections.sort(list);
int len = arr.length;
System.out.println(list);
System.out.println(list.get(len - n));
}
public static void main(String[] args) {
int[] arr = { 2, -4, 5, 6, 0, 7, -1, 10, 9 };
int n = 3;
findNthMax(arr, n);
}
}
{{
public class NthMaxArray {
public static void findNthMax(int arr[], int n) {
List<Integer> list = Ints.asList(arr);
Collections.sort(list);
int len = arr.length;
System.out.println(list);
System.out.println(list.get(len - n));
}
public static void main(String[] args) {
int[] arr = { 2, -4, 5, 6, 0, 7, -1, 10, 9 };
int n = 3;
findNthMax(arr, n);
}
}
}}
Selection search should do.
- subahjit June 28, 2013Complexity: O(n) where n is the number of elements in the array.