## 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).

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

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

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

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

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

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

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

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

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;
}``````

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

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;
}``````

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) {
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;
}``````

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

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

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;
}``````

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;
}``````

}

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;
}``````

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;

}
}``````

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

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.

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]);
}
}``````

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;
}``````

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

swap constraint: exchange only adjacent element.

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

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;
}``````

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;
}``````

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)``````

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 :)

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)

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

``````package array;
import java.util.*;

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]);
}
}
}``````

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

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)

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

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

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.