Amazon Interview Question Software Engineer / Developers
Country: India
how can u sort strings?????i mean to say how can u compare "10" and "9" and get the result "9" before "10"? :(
if its possible, then ya your logic is correct..:)
pls help
how can u sort strings?????i mean to say how can u compare "10" and "9" and get the result "9" before "10"? :(
if its possible, then ya your logic is correct..:)
pls help
how can u sort strings?????i mean to say how can u compare "10" and "9" and get the result "9" before "10"? :(
if its possible, then ya your logic is correct..:)
pls help
how can u sort strings?????i mean to say how can u compare "10" and "9" and get the result "9" before "10"? :(
if its possible, then ya your logic is correct..:)
pls help
In fact, it could not be solved using "strcmp".
For example, {"51", "517"} , {"51","514"}. For the value of strcmp, both shows "51" is less than "517" or "514" while the result should be different.
{"51", "517"} -> "517"+"51"
{"51","514"} -> "51" +"514"
So, we should create own "strcmp" function which comparing each characters in string and length of strings.
1) compare the length of two string.
2.1) if the length is same -> just use strcmp
2.2) if A's length is less -> strncmp( A, B, A_len )
if the result is 0 -> compare the B[0:B_Len-A_Len], B[A_Len:B_Len]
2.3) if B's length is less -> strncmp( A, B, B_len )
... and so on.
It would be better to compare the concatenation of two strings.
AA -> A+B
BB -> B+A
return strcmp( AA, BB );
you can sort strings by sorting them based on their pointers.... if you have *a = "hello" and *b="world",
*a is < *b because *a = 'h' and *b = 'w'.
Also, I dont think you need to convert them into string.
just extract the first digit of the number while sorting. After all, if you use itoa to convert digit to string, it is going to use the same procedure.
Implementation of offered algorithm using custom comparator.
It sorts number strings in required order.
package com.askmesoft.careercup;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class FacebookTask1 extends Common {
public static void main(String[] args) {
Queue<String> s = new LinkedList<String>();
String[] items = { "1", "222", "3", "23", "45", "46", "453", "451" };
System.out.println(makeBiggestNum(items));
}
public static String makeBiggestNum(String[] items) {
List<String> listItems = Arrays.asList(items);
Collections.sort(listItems, new NumStringComporator());
StringBuffer result = new StringBuffer();
for (String item : listItems) {
result.append(item);
}
return result.toString();
}
public static class NumStringComporator implements Comparator<String> {
private int diff(char c1, char c2) {
return (c1 > c2) ? 1 : -1;
}
@Override
public int compare(String str1, String str2) {
char c2 = 'a';
for (int i = 0; i < str1.length(); i++) {
char c1 = str1.charAt(i);
if (i >= str2.length()) {
// 583xxxxx vs 58
return diff(str2.charAt(0), c1);
}
c2 = str2.charAt(i);
if (c1 != c2) {
return c2 - c1;
}
}
if (str1.length() == str2.length()) {
return 0;
} else {
// str2 length > str1 length
return diff(str1.charAt(0), c2);
}
}
}
}
The "strcmp" function below may serve the purpose
int strcmp(char *str1,char *str2)
{
if(!*str1 && *str2)
return 1;
if(!*str2 && *str1)
return -1;
if(!*str1 && !*str2)
return 0;
if(*str1==*str2)
return strcmp(++str1,++str2);
else if(*str1>*str2)
return 1;
else
return -1;
}
My Java version leverages the PriorityQueue and the natural ordering of Strings:
String largest(int[] arr) {
PriorityQueue<String> heap = new PriorityQueue<String>();
for(int i : arr) {
heap.add("" + i);
}
String longest = "";
while(!heap.isEmpty()) {
longest = heap.poll() + longest;
}
return longest;
}
Actually we can use any nlogn sorting algorithm. There is a small modification required : while comparing two numbers, if any of them is multiple digit then use its most significant digit.Sort in Decreasing order and print the whole number....
That won't work. what if your list contains 91 and 92...
lets say our list is 5, 23, 6, 91, 101, 92
Find max number = 101 and number of digits in max number = 3
clone this array into some other array and make sure all numbers of digit 3 ..so the clone array will have
500, 230, 600, 910, 101, 920
Now just sort the array in decreasing order and then you will get the indices. using these indices, form a number from first array
We can also use modified version of radix sort and this problem can be solved in O(kn) where k is the max number of digits.
Sorting would require minimum O(nlgn) time. Problem can be easily solved in O(n) time. Below is the java code:
public class Main {
private static String lrgstNm;
public static void main(String[] args) {
int[] inpArrs = new int[]{2,3,5,78};
lrgstNm=new Integer(inpArrs[0]).toString();
for(int i=1;i<inpArrs.length;i++)
findSubSolForN(inpArrs[i], i);
System.out.println(lrgstNm);
}
private static void findSubSolForN(int inpEle, int n){
Integer inpInt = new Integer(inpEle);
if(Integer.parseInt(inpInt+lrgstNm)>=Integer.parseInt(lrgstNm+inpInt)){
lrgstNm=inpInt+lrgstNm;
}
else
lrgstNm+=inpInt;
}
}
I like the first solution. It is correct. Converting to string will give us the lexical order we need, while sorting.
For eg.
"54" > "504"
is true. And that's what we want.
In nlogn sorting , two elements are compared in constant time. Comparing two long enough strings is not a constant time operation. So nlogn sorting algorithm will appear more costly in string case.
String sort does not work try this
510,5,51 -string sort -> 510,51,5 so -> 510515
but it should 551510
Okay. In that case we write our own lex sorter, which behaves very much like std lex sorts except when comparing if a string doesn't have any more chars left and all have been equal to another so far, we output the first string as larger. So, "5" > "5x" would be true for any x value.
Would not that solve our problem ?
@knap: No, that won't solve your problem. For instance, if you have 5 and 56, you want 56 to be bigger that 5. However, id x is less that 5 then, your idea works. What we need is the following algorithm for comparison. When comparing two strings lexicography, make the lengths of the two strings equal by appending that last character of the shorter string. For instance, if you want to compare 5 and 531, compare 555 and 531. This will result in "5" being considered bigger that "531" which is what we want. On the other hand, if you are comparing, 5478 and 54, compare 5478 with 5444 which will tell you to consider 5478 to be bigger than 54. The key is to just repeat the last character of the shorter string to make them equal length and do a vanilla lexicographic comparison.
The think, we have to sort with the highest number place present in the numbers,
Eg: 5 -> highest number place is units digit = 5
78 -> highest number place is tens digit = 7
112 -> highest number place is hundreds digit = 1
Sorted sequence is 7,5,1 => 785112, will be max number can be formed.
special cases has to be dealt, like what we have duplicates.
think of below some senario also.. you need modification..
1. 5,51
2. 55,52
3. 55,557
4. 5571,5579
if most significant digit ae equal.. go for 2nd most significant digit.. and sord accourding to them.....
Or bring every element on the same scale... suppose 5 ans 51..
convert 5 to 50 abd keep track of it like we have multiplied it by 10..
sort it desc... revert the changes ...print the number..
Assume you have the following array:
Integer[] inputArray = {2,3,5,78,234}
Just write a comparator like the following and sort the above array with this comparator.... after that print out the array in the reverse order..
public class MyComparator implements Comparator<Integer>{
@Override
public int compare(Integer arg0, Integer arg1) {
String int1 = Integer.toString(arg0);
String int2 = Integer.toString(arg1);
if(Integer.parseInt(Character.toString(int1.charAt(0))) > Integer.parseInt(Character.toString(int2.charAt(0))))
return 1;
else if(Integer.parseInt(Character.toString(int1.charAt(0))) < Integer.parseInt(Character.toString(int2.charAt(0))))
return -1;
if(int1.length() < int2.length())
return 1;
else if(int1.length() > int2.length())
return -1;
if(arg0 > arg1 )
return 1;
else if(arg0 < arg1)
return -1;
return 0;
}
}
I have verified the logic as much as I could ... please respond if it fails in some case
this is the correct comparator:
public static class MyComparator implements Comparator<Integer>{
@Override
public int compare(Integer arg0, Integer arg1) {
String int1 = Integer.toString(arg0);
String int2 = Integer.toString(arg1);
if(Integer.parseInt(Character.toString(int1.charAt(0))) > Integer.parseInt(Character.toString(int2.charAt(0))))
return 1;
else if(Integer.parseInt(Character.toString(int1.charAt(0))) < Integer.parseInt(Character.toString(int2.charAt(0))))
return -1;
int i=0;
try{
for(i=0;i<Math.max(int1.length(), int2.length());i++){
if(int1.charAt(i) == int2.charAt(i))
continue;
if(int1.charAt(i) > int2.charAt(i))
return 1;
else
return 0;
}
}catch(Exception e){
if(int1.length() < int2.length()){
if(Integer.parseInt(Character.toString(int2.charAt(i))) > Integer.parseInt(Character.toString(int2.charAt(i-1))))
return -1;
else
return 1;
}else{
if(Integer.parseInt(Character.toString(int1.charAt(i))) > Integer.parseInt(Character.toString(int1.charAt(i-1))))
return 1;
else
return -1;
}
}
if(int1.length() < int2.length())
return 1;
else if(int1.length() > int2.length())
return -1;
if(arg0 > arg1 )
return 1;
else if(arg0 < arg1)
return -1;
return 0;
}
}
Compare numbers as strings digit by digit using the following scheme:
1. if len(x) < len(y) and all letters in x are greater than or equal to y, then x comes before y
2. if len(x) = len(y) use above as well
So if you have 9 and 91 then 9 comes before 91.
Similarly if you have 8 and 101 then 8 comes before 101
Mostly this requires comparing left to right until you hit different digits or one of the strings terminate, so in this respect it is similar to radix sort.
Finally just concatenate ordered digits to get the maximum possible number !
let us compare two numbers in the following way:
X=a1a2a3..ak
Y=b1b2b3... bp
Say k<p. without loss of genarality
for i = 1 to k
if( ai >bi) declare x > y;
if( ai <bi) declare y > x;
if( ai==bi) continue;
U r out of the loop remember
for i= k to p
if(ak>bi) declare x>y
if(ak<bi) declare x<y
use this to compare the numbers in the given array and use any standard sorting algorithm. Sort in decreasing order , That's your number.
Young's solutions is perfect. And that's what is expected
Here is the C# Code
class AmazonCompare
{
public AmazonCompare() { }
int Compare(int a, int b)
{
string s1 = a.ToString();
string s2 = b.ToString();
string s3 = s1 + s2;
string s4 = s2 + s1;
return (s3.CompareTo(s4));
}
public void ExampleForAmazonCompare()
{
int a = 51;
int b = 515;
a = 51;
b = 514;
a = 54;
b = 504;
int nRetval = Compare(a, b);
switch (nRetval)
{
case 1:
MessageBox.Show("a > b");
break;
case -1:
MessageBox.Show("a < b");
break;
case 0:
MessageBox.Show("a == b");
break;
}
}
}
void main()
{
AmazonCompare aCompare = new AmazonCompare();
aCompare.ExampleForAmazonCompare();
}
start building a number using a[0]. when on a[1], you have 2 choices, whether to append a[1] at begining or end. compare both numbers, and continue this way
e.g = {9,10}
in 1st pass, num = 9
2nd pass = max( 109,910 ) = 910
similarly, { 2,3,5,78 }
1st pass = 2
2nd pass = max( 32,23 ) = 32
3rd pass = max(532,325 ) = 532
4th pass = max(78532,53278 ) = 78532
convert int into string. sort array into decreasing order. merge them. comparator function used during sorting
int comperator(char* str1,char* str2,char* str1_ref,char* str2_ref){
if(*str1=='\0' && *str2=='\0')
return 0;
else if(*str1=='\0' && *str2!='\0'){
return comperator(str1_ref,str2,str1_ref,str2_ref);
}
else if(*str1!='\0' && *str2=='\0'){
return comperator(str1,str2_ref,str1_ref,str2_ref);
}
if(*str1==*str2)
return comperator(++str1,++str2,str1_ref,str2_ref);
else if(*str1>*str2)
return 1;
else
return -1;
}
e.g "54">"543" --> 54543
"54"<"545" --> 54554
if it fails in any case pls let me know
<<<#include<stdio.h>
#include<conio.h>
#include<math.h>
int append(int,int);
int append (int x,int y)
{
int c1=0,c2=0;
int x1=x,y1=y;
while(x!=0)
{
c1++;
x=x/10;
}
while(y!=0)
{
c2++;
y=y/10;
}
return (x1*pow(10,c2)+y1);
}
int main()
{
int i,j,temp;
int a[5];
for(i=0;i<5;i++)
scanf("%d",&a[i]);
for(i=0;i<5;i++)
for(j=0;j<4-i;j++)
if(append(a[j],a[j+1])>append(a[j+1],a[j]))
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
for(i=4;i>=0;i--)
printf("%d",a[i]);
getch();
return 0;
}>>>
#include<stdio.h>
#include<conio.h>
#include<math.h>
int append(int,int);
int append (int x,int y)
{
int c1=0,c2=0;
int x1=x,y1=y;
while(x!=0)
{
c1++;
x=x/10;
}
while(y!=0)
{
c2++;
y=y/10;
}
return (x1*pow(10,c2)+y1);
}
int main()
{
int i,j,temp;
int a[5];
for(i=0;i<5;i++)
scanf("%d",&a[i]);
for(i=0;i<5;i++)
for(j=0;j<4-i;j++)
if(append(a[j],a[j+1])>append(a[j+1],a[j]))
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
for(i=4;i>=0;i--)
printf("%d",a[i]);
getch();
return 0;
}
Convert the number into string and sort them.
- Anonymous December 09, 201110, 9 ---->9, 10 after sorting them
2, 3, 5, 78---> 78, 5, 3, 2 after sorting
2, 7, 67, 9-->9, 7, 67, 2 afer sorting
Merge the sored into 1 string