## Amazon Interview Question for Software Engineer / Developers

Team: Kindle
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
11
of 13 vote

This is just sorting algo (descending order ).. the only modification we need to do is .. while comparing 2 integers , we have concat one with other and compare ....
ex: {9,10} --> then while comparing 9 and 10 .. we have concat these two...910 > 109 ... so 9 comes before 10
Ex: {9,900}--> 9900>9009 --> 9 comes before 900..
Ex {10,107} --> 10710 > 10107 --> 107 comes before 10....

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

convert the array into string and sort the string array and print it in reverse order

String [] nums = {"9", "7", "9", "20", "30"};
Arrays.sort(nums);
System.out.println(" op"+nums[4]+nums[3]+nums[2]+nums[1]+nums[0]);

output: 9973020

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

It's a great idea to concat one with the other then compare. However, the ordering relation should be transitive otherwise the whole sorting may fail. How do you prove if ab>ba, bc>cb, then ac>ca?

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

See my below solution. It works for all cases. It works by comparing the last digit( where two numbers differ) with the first digit of the smaller number.

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

In the above comment "smaller number" means "the number of digits" is less compared to the other number. If the number of digits is same, then it works by comparing the first digit they differ.

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

By intuition, we can say ab>ba, bc>cb, then ac>ca...
can any one give mathematical proof for this ?

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

I just found the proof. For ease of explanation, let's assume length(a) = 2, length(b) = 3 and length(c) = 4.

With ab > ba, we have aaabb > aabab > abaab > baaab > ... > bbaaa and therefore aaa > bb. Similarly, we have bbbb > ccc.

If ca > ac, then we have ccc > aaaaaa > bbbb > ccc. By contradiction, ac > ca.

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

Your statement ccc> aaaaaa is wrong for the below values.
For a=107, c=10
ac=10710 > ca=10107, but
ccc=101010 < aaaaaa=107107107107107107

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

My earlier statement is wrong.

ccc > aaaaaa is wrong for the following value of c and a
c= 107, a=10
ca=10710 > ac=10107, but
ccc=107107107 < aaaaaa=101010101010.

Could you explain how if ca> ac => ccc > aaaaaa.
It is not correct for the above values of a and c.

Another thing how aaaaaa> bbbb

If you take a=9, b=900
ab=9900 > ba, but
aaaaaa=999999< 900900900900

So I think both ccc>aaaaaa and aaaaaa>bbbb are wrong.
Could you clarify.

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

My example is not a complete proof because I fixed the length of a, b, and c. If you change the length, then you should change the number of repeats as well. In my example, length(aaaaaa) = length(bbbb) = length(ccc), and that's the invariant you need to keep when use different numbers.

In your example, length(107) = 3, length (10) = 2, so you repeat 107 2 times, and 10 3 times. cc = 107107 > 101010 = aaa.

A formal way is to compare aa....a (repeat length(b)*length(c) times) , bb...b (repeat length(a)*length(c) times), cc...c (repeat length(a)*length(b) times).

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

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

let x=len(a), y=len(b), z=len(c), x/y/z > 0
then we get
ab>ba ==> a*10^y + b > b*10^x + a ==> a*(10^y - 1) > b*(10^x - 1)
bc>cb ==> b*10^z + c > c*10^y + b ==> b*(10^z - 1) > c*(10^y - 1) ==> b > c*(10^y - 1)/(10^z - 1)

so,
a*(10^y - 1) > b*(10^x - 1) > c*(10^y - 1)*(10^x - 1)/(10^z - 1)
==> a > c*(10^x - 1)/(10^z - 1)
==> a*(10^z - 1) > c * (10^x - 1)
==> a*10^z +c > c*10^x +a

==> ac > ca

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

The proof is quite clear:
let x=len(a), y=len(b), z=len(c), x/y/z > 0
then we get
ab>ba <==> a*10^y + b > b*10^x + a <==> a/(10^x - 1) > b*(10^y - 1)

Value a/(10^x-1) is one to one mapping of a. So the ordering should be transitive.

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

Radix sort the elements in buckets of numerals and arrange/concatenate in descending order.

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

try the following two cases :

{5,10,999}

{5,10,444}

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

Here is the C++ code for this

``````#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int compareNumString( string num1, string num2 )
{
string joined_num1 = num1+num2;
string joined_num2 = num2+num1;
return joined_num1.compare(joined_num2) > 0 ? 1: 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<string> array;
//output should be 6054854654
array.push_back("54");
array.push_back("546");
array.push_back("548");
array.push_back("60");

// output should be 777776
/*array.push_back("7");
array.push_back("776");
array.push_back("7");
array.push_back("7");*/

//output should be 998764543431
/*array.push_back("1");
array.push_back("34");
array.push_back("3");
array.push_back("98");
array.push_back("9");
array.push_back("76");
array.push_back("45");
array.push_back("4");
*/

std::sort( array.begin(), array.end(), compareNumString );

for(int i=0; i < array.size() ; i++ )
cout<<array[i];

return 0;
}``````

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

do radix sort and append the digit..

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

Here we have to sort the numbers according to the digit positions...If conflict occurs between any 2 numbers sort according to the next digit.
Let me explain with an example:

Array: [9, 18, 3, 28, 173]
Step 1: Sort according to 1st digit : [9,3,28,(18,173)]
step 2: here 18, 173 have same 1st digit. So sort according to next digit. : [9, 3, 28, 18, 173]

So output: 932818173...

P.S: We can use 'Divide by 10' technique to get first digit each time.

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

According to your algorithm, what would happen in this case?
{9, 900} .
If you tell that you have to sort the small digits first, what would be the answer for {10,107}

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

Well in that case we have to compare the resulting numbers and take the largest...

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

This approach is a bit bad, but How about, generate all the n digit (n is size of array) permutation of given array and then picking up the largest number among them arr[1,2]

2 digit permutations are [1,2] [2,1] ....21 is the largest..you need to use some extra space to store the permutation output ...and then sort that.....This can be optimized however

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

If needed i can put code for this

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *xptr, const void *yptr)
{
char *sbuffer=(char *)malloc(sizeof(char)*20),*tmp;
char *lbuffer=(char *)malloc(sizeof(char)*20);
int x=*(int *)xptr;
int y=*(int *)yptr;
int cnt=0,swapped=0;
itoa(x,sbuffer,10);
itoa(y,lbuffer,10);
if(strlen(sbuffer)>strlen(lbuffer))
{
tmp=sbuffer;
sbuffer=lbuffer;
lbuffer=tmp;
swapped=1;
}
while(*sbuffer==*lbuffer&&*sbuffer!='\0')
{
sbuffer++;
lbuffer++;
cnt++;
}
if(*sbuffer=='\0')
if((*lbuffer-'0')>(*(sbuffer-cnt)-'0'))
return(swapped?-1:1);
else
return(swapped?1:-1);
else
return(swapped?(*sbuffer-*lbuffer):-(*sbuffer-*lbuffer));
}

int main()
{
int values[]= {9, 18, 3, 28, 173};
int i;
//int values[]={9,900};
//int values[]={10,107};
//int values[]={3,71,2};
//int values[]={7,76,7,7};
int size=sizeof(values)/sizeof(values[0]);
qsort (values, size, sizeof(int), compare);
for(i=0; i<size; i++)
printf ("%d ",values[i]);
getchar();
}

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

It fails with {987, 9879, 987987}. Your program outputs 987 9879 987987 while the optimal solution is 9879 987 987987.

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

Thank you for pointing out the mistake.
if((*lbuffer-'0')>(*(sbuffer-cnt)-'0')) with
if((*lbuffer-'0')>=(*(sbuffer-cnt)-'0'))

i.e change > sign with >=. It works after this change.

Actually the optimal solution for {987, 9879, 987987} is
9879 987987 987.

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

``````How about simply sorting even and odd positions separately.
Here is the code.
#define ASC 	1
#define DEC 	2

void sort(int *a, int len, int skip, int order)
{
int i,j;

for(i=0; i<len; i+=skip) {
for(j=i+skip; j<len;j+=skip) {
if((order == ASC && a[i] > a[j]) ||
(order == DEC && a[i] < a[j]))
swap(a, i, j);
}
}
}

int main()
{
int a[] = {7,1,4,2,18,34,16,12,19,56,3,20, 5};
int len = sizeof(a)/sizeof(int);
sort(a, len, 2, ASC);
sort(a+1, len-1, 2, DEC);

return 0;
}``````

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

Sorry, posted in wrong question.

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

lexographic sorting will do.
Example: 10, 7, 9, 20, 30

compare 10 and 7 : 7 is greater than 1. NUMBER: 710
compare 710 and 9 : 9 is greater than 7. NUMBER: 9710
compare 9710 and 20 : 2 < 9 go forward check 2 < 7 go forward 2 > 1 Number: 972010.
compare 972010 and 30 : 3 < 9 go forward 3 < 7 go forward 3 > 2 Number: 97302010.

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

consider 91, 9

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

suppose u have some numbers in an array ,then u have to find greatest no.then there must me some no start with either 0-9 .u have to separate those no in different bucket on the basis of starting no.then within each bucket sort the number.sorting is done on the basis of digit,if 2 no is dere then sort it in this manner.example:- suppose i have 2 no in a bucket,(4,48).these 2 goes in 1 bucket.then on the basis of digit sort this(48,4).then ur work is done.

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

Step 1:- filter base no digits like (single,double...)
Step 2:- sort all single, then all double......
step 3:- merge
step 4:- output

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

``````E.g. {1, 34, 3, 98, 9, 76, 45, 4}
1. Sort on most significant digit of each number first. After this step all numbers starting with 9 will be followed by all numbers starting with 8 and so on. For above example: {9, 98, 76, 45, 4, 3, 34, 1}. There will be 9 groups and a group of zeros if present.
2. Sort the numbers within each group with the following special comparison function compare(a,b):
2a. Normal integer comparison with a,b have same number of digits.
2b. If a and b do not have equal number of digits, add the digit corresponding to the group as many times as needed to make the two have equal number of digits.
3. The final answer is the concatenation of the sorted numbers in steps 1 and 2.``````

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

1. Sort array in descending order
2. build the string by appending each digit
3. cast to int

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

Assumption: number is an integral 64 bits.

Insertion sort in descending order. With long int of 64 bits, the max positive value possible is 9223372036854775807, which is 19 digits. Insertion sort may do element copies. For example, if all the elements are sorted in descending order except the first element, then insertion sort needs to shift N-1 elements. In contrast, using quicksort, the number of copy operations is logn.

``````public static void sort(final List<Integer> digits) {
for (int i = 1; i < digits.size(); i++) {
int storeIndex = i;
int valueToInsert = digits.get(i);

while ((storeIndex > 0) &&
(valueToInsert > digits.get(storeIndex - 1))) {
digits.set(storeIndex, digits.get(storeIndex - 1));
storeIndex--;
}

digits.set(storeIndex, valueToInsert);
}
}``````

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

``````scala> val a = Array(9,6,8,1).sortWith((x,y) => x.toString > y.toString).mkString.toInt
a: Int = 9861``````

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

Correction:

val a = Array(7, 76, 7, 7).sortWith((x,y) => x.toString+y.toString > y.toString+x.toString).mkString.toInt
a: Int = 77776

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

How about a bucket sort and ordering from reverse???

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

This is the correct solution : www {dot} geeksforgeeks {dot} org {slash} given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number

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

Sort the array in descending order -
T(N) = O(NlgN) and S(N) = O(1)

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

No that will not work.

Consider : {9, 10}

Max number should be 910, but if you sort in descending order it will be 109.

It should be sorted on a lexicographical order.

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

so, instead of comparing the actual numbers in a sorting routine the code should compare the numbers converted to strings, like

``Array.Sort(input, (n1, n2) =>{return string.Compare(n1.ToString(), n2.ToString())} );``

?

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

``````public int compare(Integer x, Integer y) {
return - ( Integer.toString(x).compareTo( Integer.toString(y) ) );
}

Integer[] arr = {10, 11};
Arrays.sort( arr, IntegerLexicalDescComparator.INST );``````

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

``````public static void findMaxNumber(Integer[] input){
Arrays.sort(input, new Comparator<Integer>(){

@Override
public int compare(Integer o1, Integer o2) {
StringBuffer buf = new StringBuffer();
buf.append(o1);
buf.append(o2);
String s1 = buf.toString();
String s2 = buf.reverse().toString();
return s2.compareTo(s1);
}
});

StringBuffer buf2 = new StringBuffer();
for(int n : input){
buf2.append(n);
}

System.out.println(buf2.toString());
}``````

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

Ignore the above code. It does not always work.

As for example : {7, 76, 7, 7} gives 77677 when 77776 should be the answer

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

do permutation of number and keep track of maximum number.

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

Convert the array into String so that we have all the array as the String of digits and then we can do a sort on the String in descending order to get the largest number.

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

That may not work....
Bcz relative positions of the individual strings may be changed...

Eg. array [3, 71, 2]
Idle Output: 7132

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

Nope, his idea is correct, it'll indeed give correct output.

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

But again you'll have to write your own comparator for comparing string. else [9,900] will give you 9009. that means we're back to the same problem of solving integers.

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.