Amazon Interview Question for Web Developers


Country: India
Interview Type: Written Test




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

By saying maximize, I assume elements in array are projected as digits in a single number. Now we want to maximize that number by shuffling.

1. Starting from first digit, check next n digits. Record the position of biggest one. Here n=swapsAllowed.
2. Bubble the biggest digit to the top. Reduce n by no. of swaps. Reset n to -> n=n-(distance of biggest digit from top)
3. Move to second digit, repeat #1 with new value of n.
4. Repeat 3 until n or no. of digits are exhausted.

Time needed - O(n2). Space O(1)

If extra memory is not a problem, we can parse all digits and keep them in a decreasing order along with their indeces, in a sorted map. In that case, time will come down to O(nlogn) -[O(nlogn) for sorting, and O(n) for processing], and space will go up by O(n).

- Harsh May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

suppose all the number in first n digits are already max(if they are in decreasing order?)

- lpook May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice answer!

You can do O(n) time sorting in this problem, using counting sort or bucket sort.

(The last sentence you wrote may be correct, but be careful with the notation: little-o vs. big-O ...)

- ninhnnsoc May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

consider the test case 3, 8, 9
number of swaps allowed = 1
then
according to you answer would be 3, 9, 8
but answer should be 8, 3, 9

- Rohit Agarwal May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

@Rohit:
Starting from first digit, means starting from left. So, for 3,8,9 we start from 3. No. of swaps allowed is 1. So, we go to next digit and swap if it is bigger; if we swap, reduce the no. of swaps used. No. of swaps are exhausted so we stop and say this is final answer. This will change the number to 8,3,9 (the correct answer).

Consider another example -
4, 1, 9 - no. of swaps allowed - 1
First iteration will start from 4 and go till second digit (no. of swaps). Since, no change is required, we fix first position and repeat the same process from second. Since, our allowed swaps are not used, we can do next iteration

Second iteration will start from 1 and go till 9. Since, swap makes sense and we do that. No. changes ti 4, 9, 1.


@ipook : If no. are in decreasing order, can it be maximized ? Swaps will not be used and this algo will return the same no.

- Harsh May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

C++ implementation for Approach#1

#include <iostream>
#include<stdint.h>
#include<limits>
#include<cmath>


using namespace std;

int findMaxIndex(int* arr,int start, int end)
{
    int max_index = start;
    for(int curr = start; curr < end; curr++)  
    { 
        if(arr[curr] > arr[max_index])
        {
            max_index = curr;
        }
        
    }
       
    return max_index;
}

void printArray(int * arr, int length)
{
    cout<<endl;
    for(int i = 0; i<length; i++)
    {
        cout<<arr[i]<<" ";
    }
    
}

void maximizeArray(int * arr, int len, int swaps)
{
    
   
	int max_index = -1, max = -std::numeric_limits<int32_t>::max();;
	     
	for(int j = 0; (j < len ) && (swaps > 0) ; ++j)
	{
	    max_index = findMaxIndex(arr,j,j+swaps);
        
        if(j != max_index)
        {
            int temp = arr[j];
            arr[j] = arr[max_index];
            arr[max_index] = temp;
        
        }
    
        swaps = swaps - (abs(max_index - j));
                    
	}
	
}

int main()
{
    int arr[]={1,5,2,9,3,7,2,8,9,3};
    int length = sizeof(arr) / sizeof(int);
    cout<<endl<<"Before:";
    printArray(arr,length);
	
    maximizeArray(arr, length, 5);

    cout<<endl<<"After:";
    printArray(arr,length);
   
   
   return 0;
}

- phalgun May 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This my C# implementation for this approach, please let me know if you spot any bug with it, cheers:

public void Maximize(int[] arr, int swapsAllowed)
        {
            if (arr == null)
            {
                return;
            }

            int start = 0;
            int swapsLeft = swapsAllowed;
            int lastIndex = swapsLeft + start < arr.Length - 1 ? swapsLeft + start : arr.Length - 1;
            int maxIndex = start;

            while (swapsLeft > 0 &&
                   start < arr.Length)
            {
                for (int i = start + 1; i <= lastIndex; i++)
                {
                    if (arr[i] > arr[maxIndex])
                    {
                        maxIndex = i;
                    }
                }

                if (maxIndex > start)
                {
                    for (int i = maxIndex; i >= start + 1; i--)
                    {
                        Swap(ref arr[i], ref arr[i - 1]);
                    }
                }

                swapsLeft = swapsLeft - (maxIndex - start);
                start++;
                lastIndex = swapsLeft + start < arr.Length - 1 ? swapsLeft + start : arr.Length - 1;
                maxIndex = start;
            }
        }

        private void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

- Onat May 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

#include <stdio.h>

int findMax(int *a,int start, int end)
{
   int i =start;
   int index;
   int max =0;
   for(;i<=end;i++)
   {
	if(max < a[i])
        {
           max = a[i];
           index = i;
        }
   }
   return index;
}

void moveMaxElementToBeginning(int *a,int maxIndx,int start,int* swaps)
{
   int tmp;
   int i=0;
   if(maxIndx == start)  return;

   while(maxIndx != start)
   {
       tmp = a[maxIndx];
       a[maxIndx] = a[maxIndx -1];
       a[maxIndx-1] = tmp;
       maxIndx = maxIndx -1; 
       *swaps = *swaps -1;
   }
   printf("New array ");
   for(i=0;i<10;i++)
		printf("%d ",a[i]);
	printf("\n");
}


void swapToMax(int *a, int N, int nswaps)
{

int start =0;
int end = nswaps;
int maxIndx;
	while(nswaps > 0)
	{
   		maxIndx = findMax(a, start,end);
   		printf("found max %d indx %d\n",a[maxIndx],maxIndx);
   		moveMaxElementToBeginning(a,maxIndx,start,&nswaps);
   		printf("moved max to front %d \n",a[0]);
   		start = start + 1;
   
	}
}

int main(void) {
	// your code goes here
	int i=0;
	int a[]={2,5,1,9,3,7,2,8,9,3};
	
	printf("Original Array\n");
	for(i=0;i<10;i++)
		printf("%d ",a[i]);
	printf("\n");
	
	swapToMax(a,10,5);  // 5 swaps
	
	for(i=0;i<10;i++)
		printf("%d ",a[i]);
	printf("\n");
	
	return 0;
}

- northernlight May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

who down voted ??? it works perfectly...

- northernlight May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void maximize(int[] ar, int swapsAllowed){
		int numSwaps=swapsAllowed;
		for(int j=0;numSwaps!=0;j++){
			int i=maxNum(ar, j, ar.length);
			if(numSwaps<ar.length-j)
				i=numSwaps;
			for(; i>0;i--){
			swap(ar,i,i-1);
		}
		}
	}
	public static int maxNum(int ar[], int start, int end){
		int max=ar[start];
		int maxIndex = start;
		for (int i = start; i<=end;i++){
			if(max<ar[i]){
				max = ar[i];
				maxIndex = i;
			}
		}
		return maxIndex;
	}

- Rahul May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ proposal. I took into account the fact that swaps can only be performed on adjacent locations:

{
void swapMax(int * arr, int target_position, int current_position)
{
	int aux = 0;
	for(int i = current_position; i > target_position; i--)
	{
		aux = arr[i - 1];
		arr[i - 1] = arr[i];
		arr[i] = aux;
	}
}

void maximizeArray(int * arr, int length, int swaps)
{
	if(swaps == 0)
		return;
	
	for(int i = 0; i < length; i++)
	{
		int max_index = 0, max = -INT32_MAX;
		int limit = (swaps + i) > length ? length : swaps + i;
		for(int j = i; j <= limit; j++)
		{
			if(arr[j] > max)
			{
				max = arr[j];
				max_index = j;
			}
		}
		swaps -= (max_index - i);
		swapMax(arr, i, max_index);
		if(swaps == 0)
			break;
	}
}

int main()
{
	int arr[]={1,5,2,9,3,7,2,8,9,3};
	int length = sizeof(arr) / sizeof(int);
	maximizeArray(arr, length, 5);
	
	for(int i = 0; i < length; i++)
		cout << arr[i] << " ";
	cout << endl;
        //9 5 2 1 3 7 2 8 9 3 
	return 0;
}

}

- NL May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Without sorting -- max O(n^2)... min O(n);

public static void maximize(int[] ar, int swapsAllowed){
		int numSwaps=swapsAllowed;
		
		for(int j=0;j<ar.length-1 && numSwaps!=0; j++){
			int i=maxNum(ar, j, ar.length-1);
			if(numSwaps<ar.length-j)
				i=numSwaps;
			for(; i>j;i--){
			swap(ar,i,i-1);
			numSwaps--;
		}
		}
	}
public static int maxNum(int ar[], int start, int end){
		int max=ar[start];
		int maxIndex = start;
		for (int i = start; i<=end;i++){
			if(max<ar[i]){
				max = ar[i];
				maxIndex = i;
			}
		}
		return maxIndex;
	}

- traitorJack May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test {
    public static void main (String[] args){
    	int a[] = {3,8,9};
    	Test t = new Test();
    	int b[] = t.swapWithLimit(a, 2);
        for (int i : b){
        	System.out.print (i +", ");
        }
    }
    
    
    //{3,8,9}, 1
    public int[] swapWithLimit (int[] array, int limit){
        int limitLeft = limit;
        for (int j = 0; (j < array.length) && (limitLeft > 0); j++){
            int maxIndx = j;                                                    
            for (int i = j + 1; i < array.length; i++){            
                if ( (array[maxIndx] < array[i]) && ((i - j) <= limit)){
                    maxIndx = i;                                                
                }
            }
            
            if (maxIndx != j){
                int temp = array[j];
                array[j] = array[maxIndx];
                array[maxIndx] = temp;
                
                limitLeft = limit - maxIndx;
                
            }
        }
        return array;
        
    }
}

- Math.random() May 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] maximize(int[] arr, int swapsAll,int startIndex)
{
int maxIndex = 0;
int maxi = 0;
for (int i = startIndex; i < min(arr.Length - startIndex, swapsAll) + startIndex + 1; i++)
{
if (arr[i] > maxi)
{
maxi = arr[i];
maxIndex = i;
}

}

int count = swapsAll;
while (count > 0 && maxIndex > startIndex)
{
swap(ref arr[maxIndex], ref arr[maxIndex - 1]);
Console.WriteLine(arr[maxIndex].ToString()+","+ arr[maxIndex - 1].ToString());
count--;
maxIndex--;
}
if (count >= 0 && startIndex+1<arr.Length)
arr = maximize(arr, count,startIndex+1);
return arr;
}

- RS117 May 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Optimal Solution :
Assuming the array elements are in single digit and space is not a constraint.
1. Construct the Binary Tree for the given array.
2. Traverse the Tree in Reverse In-order algorithm. i.e. Right -> Root -> Left

Now you will get the maximum number which can be formed from the given array.

- Anonymous June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// This is the best way for finding biggest number
public class Swap 
{
	public static void main(String[] args) 
	{
		int a[]={2,5,1,9,3,7,2,0,9,30};
		int l=a.length;
		int k=l;
		for (int i=0;i<l-1 ;i++ )
		{
			for (int j=0;j<k-1 ;j++ )
			{
				if (a[j]<a[j+1])
				{
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
			}
			k--;
		}
		System.out.println("biggest number "+a[0]);
	}
}

- surya vattikuti February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Solution:

public static int[] maximize(int[] a, int swaps) {
        int l = a.length;
        for (int j = 0; swaps != 0; j++) {
            int i = max(a, j, l);
            int t = a[j];
            a[j] = a[i];
            a[i] = t;
            swaps--;

        }
        return a;
    }

    public static int max(int a[], int start, int end) {
        int maxNum = a[start];
        int maxIndex = start;
        for (int i = start; i < end; i++) {
            if (maxNum < a[i]) {
                maxNum = a[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

- Urja March 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

swap constraint: exchange only adjacent element.

- funktional September 26, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;

int max_ind(vector<int> &a, int l, int r){
int maxi = l;
for(int i=l;i<=r;i++){
if(a[maxi]<a[i])
maxi = i;
}
return maxi;
}

void max_number(vector<int> &v, int swaps){
for(int j=0;(j<v.size()) && (swaps >0);j++){
int max_index = max_ind(v, j, j+swaps);
int k = max_index;
if(j != max_index){
while(max_index > j){
swap(v[max_index], v[max_index-1]);
max_index--;
}
}
swaps -= abs(k - j);
// cout<<"zxzcz "<<swaps<<endl;
}
}

int main(){
int n,swaps;
cin>>n;
vector<int>v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
cin>>swaps;
max_number(v, swaps);
for(int i=0;i<n;i++)
cout<<v[i]<<" ";
cout<<endl;
}

- Rohit Meena February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;

int max_ind(vector<int> &a, int l, int r){
    int maxi = l;
    for(int i=l;i<=r;i++){
        if(a[maxi]<a[i])
            maxi = i;
    }
    return maxi;
}

void max_number(vector<int> &v, int swaps){
    for(int j=0;(j<v.size()) && (swaps >0);j++){
        int max_index = max_ind(v, j, j+swaps);
        int k = max_index;
        if(j != max_index){
            while(max_index > j){
                swap(v[max_index], v[max_index-1]);
                max_index--;
            }
        }
        swaps -= abs(k - j);
       // cout<<"zxzcz "<<swaps<<endl;
    }
}

int main(){
    int n,swaps;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    cin>>swaps;
    max_number(v, swaps);
    for(int i=0;i<n;i++)
        cout<<v[i]<<" ";
    cout<<endl;
}

- Rohit Meena February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;

int max_ind(vector<int> &a, int l, int r){
    int maxi = l;
    for(int i=l;i<=r;i++){
        if(a[maxi]<a[i])
            maxi = i;
    }
    return maxi;
}

void max_number(vector<int> &v, int swaps){
    for(int j=0;(j<v.size()) && (swaps >0);j++){
        int max_index = max_ind(v, j, j+swaps);
        int k = max_index;
        if(j != max_index){
            while(max_index > j){
                swap(v[max_index], v[max_index-1]);
                max_index--;
            }
        }
        swaps -= abs(k - j);
       // cout<<"zxzcz "<<swaps<<endl;
    }
}

int main(){
    int n,swaps;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    cin>>swaps;
    max_number(v, swaps);
    for(int i=0;i<n;i++)
        cout<<v[i]<<" ";
    cout<<endl;
}

- rohitm924 February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution

import math
def maxi_el(L, s, e):
   maxi = s
   for i in range(s, e+1):
      if(L[maxi] < L[i]):
         maxi = i
   return maxi

def new_array(L, swaps):
   for i in range(0, len(L)):
      if(swaps <= 0):
         break
      max_index = maxi_el(L, i, i+swaps)
      z = max_index
      if(i != max_index):
         while(max_index > i):
            temp = L[max_index]
            L[max_index] = L[max_index-1]
            L[max_index-1] = temp
            max_index = max_index-1
      swaps = swaps - abs(i - z)

n = input("Enter size of array \n")
n = int(n)
L = list()
print ("Enter element in array")
for i in range(0, n):
   x = input()
   x = int(x)
   L.append(x)
print ("Enter number of swaps")
x = input()
x = int(x)
new_array(L, x)

for i in L:
   print (i)

- rohitm924 February 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution:-

Maintain hash to linkedlist mapping for each digit (1-9)
In the linkedlist for each digint append each position(default ascending order) of its appearance in original array given.

Now,
for each 1..n
starting from 9 to 1 find the max element available and possible in (<=) k moves and place it
reduce k by number of moves required in previous step.

Though complexity is O(9 * n), 9 is a constant :)

- sreekanth March 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can make the Cell Structure with syntax.

Struct Cell {
	int index;
	int value;
}

Make the array of the structures and sort them (according to values)using the comparator function. Do a final iteration on the sorted array and calculate the swaps by subtracting the index in the array and the index in the structure.

Complexity : O(nlogn)

- rishi_neo May 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package array;
import java.util.*;


public class maxNumKAdjSwap {
	
	
	public static int findMax(int ar[],int start, int end){
		
		int max = start;
		for(int i= start+1; i<end; i++){
			if(ar[max]<ar[i]){
				max = i;
			}
		}
		return max;
	}
	
	public static void swapMax(int ar[], int start, int end){
		
		int temp = -1;
		for(int i = end; i>start; i--){
			 temp = ar[i];
			 ar[i] = ar[i-1];
			 ar[i-1] = temp;
		}	
	}

	public static void findMaximumNum(int ar[], int k, int n){
		
		int start = 0;
		int end = n;
		while(k>0 && start<end){
			int max = findMax(ar,start,end);
			if(max!=start && k>=max-start){
				k -= max- start; 
				swapMax(ar,start,max);
				end = start + 1 + k ;
			}
			start++;
		}
	} 
	
		public static void main(String argsr[]){
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
			int k = sc.nextInt();
			int ar[] = new int[n];
			for(int i=0; i<n; i++){
				ar[i] = sc.nextInt();
			}
			findMaximumNum(ar,k,n);
			for(int i=0; i<n; i++){
				System.out.printf("%d ",ar[i]);
			}
		}
}

- Ayushi April 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I suppose there are two scenarios to look at
1. n(number of swaps)>=(number of swaps required to bring biggest element in front of subarray under consideration)
2. n(number of swaps)<(number of swaps required to bring biggest element on top of subarray under consideration)

for case 1, find biggest ele, bubble it up till it reaches front, fix the pos(i), update n(number of swaps left), repeat process for subarray A[i+1]...A[length-1].
for case 2, start after fixed pos in case 1, keep swapping A[i] with A[i+1] if A[i]<A[i+1], update n, repeat until n becomes 0.
in case one, we will start from biggest element and bubble up, till it comes to the top then decrement n by n-(number of swaps used). Find next big element from next element.. keep repeating.
in case 2, we will start from top and find the pair which follows A[i]<A[i+1] and swap

- JK31 July 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class FindMaxNumberAfterSwaps{

	private static void findGreatestNumber(int a[],int noOfSwaps){
		int max =0;
		int indexOfMax = 0;
		
		for(int i=0;noOfSwaps!=0 && i < a.length - 1 ;i++){
			max =a[i];
			indexOfMax=i;
			for(int j=i+1;j<a.length;j++){
				if(max<a[j]){
					max = a[j];
					indexOfMax = j;
				}
			}
			
			for(int k = indexOfMax ;  noOfSwaps != 0 && k != 0; ){
				if(a[k] > a[k-1]){
					a[k]=a[k]^a[k-1];
					a[k-1]=a[k]^a[k-1];
					a[k]=a[k]^a[k-1];
					noOfSwaps--;
					k--;
				}	
				else
					break;
			}
		}

	}
	public static void main(String args[]){
		int a1[]={2,5,1,9,3,7,2,8,9,3};
		int a2[]={2,1,1,1,1,1};
		int a[]={5,4,3,2,1,0};
		int noOfSwaps = 2;
		
		System.out.print("Old Array: ");
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]+" ");
		System.out.println();		
		findGreatestNumber(a,noOfSwaps);	
		System.out.print("New Array: ");	
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]+" ");
		System.out.println();					
			
		
	}
}

Time : O(n^2)
Space : O(1)

- dhirajb1989 May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for(int k = indexOfMax ; noOfSwaps != 0 && k != 0; )
should be for(int k = indexOfMax ; noOfSwaps > 0 && k > i; )

- weizhishu007 May 12, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More