Amazon Interview Question
Web DevelopersCountry: India
Interview Type: Written Test
suppose all the number in first n digits are already max(if they are in decreasing order?)
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 ...)
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:
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.
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;
}
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;
}
#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;
}
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;
}
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;
}
}
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;
}
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;
}
}
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;
}
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.
// 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]);
}
}
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;
}
#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;
}
#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;
}
#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;
}
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)
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 :)
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)
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]);
}
}
}
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
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)
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.
- Harsh May 11, 20141. 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).