Google Interview Question Software Engineer / Developers
Again just to prove my earlier algorithm, if you check the sorted array in the example [9,94,4,14,1], you can see that
9 > 94 (when you try it as 994 > 949)
94 > 4 (because 944 > 494)
4 > 14 (because 414 > 144)
14 > 1 (because 141 > 114)
Done!!
okay given an array like this
9009, 664, 64, 19, 7, 9, 24, 964, 99
@Kishore:
can u demonstrate the answer with ur algo
@blueskin:
I did not write the code to execute and give you an answer.
You can do it yourself as all u need is a 10 line quicksort program.
If you find an error in my logic, you can dispute it by giving an example. To dispute a logic you just need 2-3 input numbers.
Please don't get me wrong as i don't want to take the pain of writing code.
I'd try using a trie-based approach.
For input: 9,94,4,14,1
root has 3 edges {9,4,1}
9 has two edges {$,4}
1 has two edges {4,$}
which is something like
/|\
/ | \
9 4 1
/ \ / \
$ 4 4 $
leaves are: 9, 94, 4, 14, 1
concatenated string: 9944141
the only trick seems to define order of $. As edge (4) is smaller than preceding value (i.e. 9), $ comes to left of 4. In the other case, $ comes after 4 (for 1).
report any flaw that you could catch here. thanks.
Jinxed, I think you are wrong. According to the algorithm mentioned above 9>8 so 89 comes first then 8 comes next
Hi,
Group the elements based on their MSB, sort the elements within each group (as well sort the groups also based on MSB)
Now start concatenating of two elements within group (u can always check the value also while concatenating that which one is bigger) do the same with elements of out side the groups
ex: 9,100
{9},{100} (since MSB of 100 is 1)
so final element will be 9100
ex: 9,99,91,5,59,8,81,4,44,21
goup {9,91,99} ,{8,81} ,{5,59} ,{4,44} ,{21}
start concatenating
991 >919 so 991
99199 < 99991 so 99991
similarly in second group 881
in third 595
in fourth 444
in fifth 21
so final 9999188159544421
u r comment is always welcome let me know if i am missing something...
hi implemented your idea
here is the tcl coding
proc group { data key } {
set final ""
for { set i 0 } { $i < [ llength $data ] } { incr i } {
set temp [ lindex $data $i ]
set pre $temp
while { $temp > 0 } {
set pre $temp
set temp [ expr { $temp / 10 } ]
}
if { $pre == $key } {
lappend final [ lindex $data $i ]
}
}
return $final
}
proc gather { data } {
while { [ llength $data ] != 1 } {
set final ""
set temp "[ lindex $data 0 ][ lindex $data 1 ]"
lappend final $temp
for { set i 2 } { $i < [ llength $data ] } { incr i } {
lappend final [ lindex $data $i ]
}
set data [ lsort $final ]
}
return $data
}
set data "100 9"
set result ""
for { set i 1 } { $i < 10 } { incr i } {
set temp_group [ group $data $i ]
if { [ lindex $temp_group 0 ] != "" } {
lappend result [ gather [ lsort $temp_group ] ]
}
}
set result [ lsort -decreasing $result ]
puts [ join $result "" ]
public static void concateMaxValue(int[] data, int left, int right) {
if(left < right) {
int part = partition(data,left,right);
concateMaxValue(data, left, part);
concateMaxValue(data, part + 1, right);
}
}
private static int partition(int[] data, int left, int right) {
int mid = (left+right)>>1;
int i = left;
int j = right;
String value1, value2;
while (true) {
while (i < right){
value1 = Integer.toString(data[mid])+Integer.toString(data[i]);
value2 = Integer.toString(data[i])+Integer.toString(data[mid]);
if (Integer.valueOf(value1)< Integer.valueOf(value2)){
i++;
} else {
break;
}
}
while (j > left) {
value1 = Integer.toString(data[mid])+Integer.toString(data[j]);
value2 = Integer.toString(data[j])+Integer.toString(data[mid]);
if (Integer.valueOf(value1)> Integer.valueOf(value2)){
j--;
} else {
break;
}
}
if (i < j){
swap(data, i, j);
i++;
j--;
}
else {
return j;
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
K rounds where is the maximum number of digits in any number in array.
k=0;
For each rounds
1. Sort the array based on the Kth (from left or MSB) digit.
2. In case of comparison like 8 and 89 where k=2, if the kth digit is greater than (k-1)th digit(i.e. 9>8 in 89),put 89 first otherwise 8.
3. k++
I don't know if this would work fine...this is the first thing which came to my mind instantly, so i shared it
1. Sort in lexicographically decreasing . Using radix sort base 10. With constraint if number is having only one digit then if second digit of first element of corresponding sorted list is less than the current number then append that number at first position and after that this number of this array wont take part in sorting.
2. Now concatenate all starting from 9.
Let's compare these two numbers (letters represent digits): xyzab and xyz
the two possibilities are:
xyzabxyz
xyzxyzab
if a=x then we continue the comparison
if b=y -- || --
now we have to compare x to z then y to a...
I am afraid none of the solutions above works for such cases.
I tried to work my approach with the case you mentioned. Here's two examples:
input: 123, 12312
as the digit after 123 is "1" which is less than 3, the concatenation would be 12312312, which is bigger than 12312123
input: 123, 12341
as the digit after 123 is "4" which is bigger than 3, the concatenation would be 12341123, which is bigger than 12312341
pls, give an example where you think my above approach fails. thanks.
Hi,
I posted the answer below. I guess it works for all cases and is simple. Can you check and let me know if you see issues.
I am copying it again here:
++++++++++++++++++++++++++++++++++++++++
quick sort the input BUT
while comparing two inputs A and B
instead of doing the regular A > B, DO THIS
if(ToInt('AB') > ToInt('BA')) return 1
Example:
The idea is why would you chose '9' over '94'. All I have to check is whether '994' is greater than '949'. I hope that is clear. Once you sort them by this fashion, you have the sorted list. Just concatenate to get the answer.
+++++++++++++++++++++++++++++++++++++++
else -1;
Your approach works fine for all cases I tried. I assumed all inputs are strings (because there is no specification), and quicksort gives O(nm logn) solution where n is size of input, m = length of final result (i.e. summation of inputs' length).
Heres the approach
if i and j are the 2 numbers...count the number of continuous ones at the front and back of i and j...let them ifrnt,iback,jfrnt,jback...
if(iback+jfrnt)>(jback+ifrnt)
i should come before j
else
j should come before i
eg:12315,123--->123 is 1111011--->front=4,back=2
12315 is 11000000011011--->front=2,back=2...so 12315 should come before 123
Take another array ,size same as the number of numbers of the previous array.Get the average of the digits of the previous array elements.Put them into the second array after sorting these averages .Print the array elements of the previous one according the array order.
e.g: [4, 94, 9, 14, 1]
second array contains:[4,6.5,9,2.5,1]after sorting (non increasing)[9,6.5,4,2.5,1]
so print..
9,94,4,14,1
one thing to remember you must have to put a mark whether this number is from two or three or.. or one give priority one>two>three...
please give comment if i am wrong
In support of Kishore 's argument ::
public class quicksort_modified {
static int cnt;
public static int addup(int a,int b)
{
String s1,s2;
s1= Integer.toString(a);
s2= Integer.toString(b);
return (Integer.parseInt((s1+s2)));
}
public static int lng(int a)
{
int ln=0;
while(a!=0)
{
ln++;
a=a/10;
}
return ln;
}
public static int partition(int a[],int l, int h)
{
int x=a[h],temp;
int i=l-1,j;
for (j=l;j<h;j++)
{
if(lng(a[j]) == lng(x))
{
if (a[j]>=a[h])
{
cnt++;
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
else if ( addup(a[j],x) >= addup(x,a[j]) )
{
cnt++;
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i+1];
a[i+1]=a[h];
a[h]=temp;
return i+1;
}
public static void quicksort(int a[],int l,int h)
{
if (l<=h)
{
int pivo=partition(a,l,h);
quicksort(a,l,pivo-1);
quicksort(a,pivo+1,h);
}
}
public static void main(String[] args)
{
int[] a={4,94,9,14,1},i;
quicksort(a,0,4);
/*for(i=0;i<5;i++)
System.out.println("\n %d"+a[i]);*/
StringBuffer sb = new StringBuffer();
for (int j = 0; j < a.length; j++) {
sb.append(a[j]);
}
System.out.println(sb);
System.out.println("\n Number of comparisons : "+cnt);
}
}
package simple;
import java.util.Arrays;
public class arrComp {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[] arr= {90,9,19,0,5};
printArray(arr);
Arrays.sort(arr,new intComp());
printArray(arr);
}
private static void printArray(Integer[] arr) {
// TODO Auto-generated method stub
String result = "";
for( Integer a: arr){
//System.out.print(a+" ");
String temp=Integer.toString(a);
result+=temp;
}
System.out.println("Result= "+ result);
}
}
package simple;
import java.util.Comparator;
public class intComp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
String firstNum =Integer.toString(o1);
String secNum =Integer.toString(o2);
String firstSec=firstNum+secNum;
String secFirst=secNum+firstNum;
Integer fs= Integer.parseInt(firstSec);
Integer sf=Integer.parseInt(secFirst);
return (-fs.compareTo(sf));
}
}
We could sort for each digit keeping the rule that:
1. Sort all digits in ascending order if the digits are less than previous digit.
2. Sort all digits in descending order if the digits are greater than previous digit.
Eg. we have two digits XYZ, ABC, XD
First sort on X and A
Next for all X based digits sort for Y, D (using the above rules).
1. please find my code below. it is compiled and executable code.
2. API: int IsGreater(int a, int b) takes two integers.
return 1 if a > b ( i.e a's value is lexicographically greater than b's value )
return 0 if a > b ( i.e a's value is lexicographically less than b's value )
Example 1: a = 8, b=89 then a < b
Exmaple 2: a = 7, b = 76 then a > b
Example 3: a=7 b=778 then a<b
3. I used selection sort to sort the array lexicographically.
4. I am achiebing lexicographical order by using IsGreater() API.
5. Time complexity O(n^2);
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverse(char *str,int len) {
int i=0;
char ch;
for(i=0;i<=(len-1)/2;i++) {
ch=str[i];
str[i]=str[len-1-i];
str[len-1-i]=ch;
}
}
char* itoa(int number) {
char *str= (char * ) malloc(sizeof(char)*20);
int negFlag=0,pos=0;
if(number<0) {
negFlag=1;
number=-number;
}
while(number>0) {
str[pos++]='0'+number%10;
number=number/10;
}
if(negFlag) {
str[pos++]='-';
}
str[pos]='\0';
reverse(str,pos);
return str;
}
int IsGreater(int a, int b)
{
char *str1 = itoa( a ) ;
char *str2 = itoa( b ) ;
int len1 = strlen(str1);
int len2 = strlen(str2);
// printf("\n str1 = %s str2 = %s \n", str1, str2 );
int i =0;
int j =0;
while( i< len1 && i < len2 )
{
if( str1[i] > str2[i] )
{
return 1;
}
else if( str1[i] < str2[i] )
{
return 0;
}
else
{
i++;
}
}
j = i;
i--;
while( j< len1 || j < len2 )
{
if( len1 < len2 )
{
if( str1[i] > str2[j] )
{
return 1;
}
else if( str1[i] < str2[j] )
{
return 0;
}
else
{
j++;
}
}
else
{
if( str1[j] > str2[i] )
{
return 1;
}
else if( str1[j] < str2[i] )
{
return 0;
}
else
{
j++;
}
}
} // end of while
}
void Swap( int data[], int i, int j )
{
if( i != j)
{
data[i] = data[i] ^ data[j] ;
data[j] = data[i] ^ data[j] ;
data[i] = data[i] ^ data[j] ;
}
}
int main()
{
int data[] = {4,94, 9,14,1,8,89,7,76,778} ;
int data_size = sizeof(data) / sizeof(int) ;
int i = 0;
int j;
int max_index;
while( i < data_size )
printf("\t %d , ", data[i++] );
printf("\n \n ");
/* Selection Descending order sort */
for( i = 0 ; i < data_size ; i++ )
{
max_index = i;
for( j= data_size ; j > i ; j-- )
{
if( IsGreater( data[j], data[max_index] ))
{
// printf("\n j = %d max_index = %d \n", j, max_index );
max_index = j;
}
}
Swap( data, max_index, i );
}
i = 0;
while( i < data_size )
printf("\t %d , ", data[i++] );
return 0;
}
Go brute force. Use backtracking
public static void main(String[] args) {
int[] array = { 4, 94, 9, 14, 1 };
System.out.println(findMax(array));
}
public static int findMax(int[] array) {
boolean[] used = new boolean[array.length];
return doFindMax(array, used, 0, 0, 0);
}
private static int doFindMax(int[] array, boolean[] used, int count,
int current, int max) {
if (count == array.length) {
return (current > max) ? current : max;
}
for (int i = 0; i < array.length; i++) {
if (!used[i]) {
used[i] = true;
int newValue = Integer.valueOf(current + "" + array[i]);
int t = doFindMax(array, used, count + 1, newValue, max);
if (t > max) {
max = t;
}
used[i] = false;
}
}
return max;
}
Pretty simple solution:
1)Parse the array, if the integer length is greater that 1, find the quotient and remainder by dividing it by 10, i.e. if it is 94%10 is we get 9,4. Like wise split the elements as follows 4,9,4,9,1,4,1. Sort this array you will get the maximum value.
2) if the integer length is greater than split it recursively by dividing it with 100 and then with 10, (applies for all cases).
In support of @Kishore answer:
bool GreaterCombined(const int& a, const int& b) {
stringstream ssab, ssba;
ssab << a << b;
ssba << b << a;
int ab, ba;
ssab >> ab;
ssba >> ba;
return ab > ba;
}
int main(int argc, char** argv) {
int array[5] = {4, 94, 9, 14, 1};
vector<int> input(array, array+5);
sort(input.begin(), input.end(), GreaterCombined);
for (int i = 0; i < 5; ++i)
cout << input[i] << " ";
cout << endl;
}
for (int i=0;i<n;i++) {
for(int j=i;j<n;j++) {
if(Integer.Valueof(a[i]).CharAt(0) < Integer.Valueof(a[i+1]).CharAt(0)) {
swap(a[i],a[i+1]);Lo
}else if(Integer.Valueof(a[i]).CharAt(0) == Integer.Valueof(a[i+1]).CharAt(0)) {
if(strlen(Integer.Valueof(a[i]) < strlen(Integer.Valueof(a[i+1]) ) {
swap(a[i],a[i+1]);
}
}
}
}
The logic behind this is that we have to check that ab and ba for two integers a & b . Suppose a = 9 and b = 94. So, ab = 994 && ba = 949 thus, ab > ba. hence order will be 9, 94. This can be done by implementing our own comparator.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
class Sort implements Comparator<Integer> {
public int compare(Integer a, Integer b) {
String first = a.toString();
String second = b.toString();
return (first+second).compareTo(second+first);
}
}
public class ComparatorSort {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Integer [] inputArray = new Integer[n];
for(int i=0;i<n;i++)
inputArray[i] = Integer.parseInt(br.readLine());
Arrays.sort(inputArray, new Sort());
for(int i=n-1;i>=0;i--)
System.out.print(inputArray[i] + " ");
System.out.println();
}
}
Sort the string array of numbers by comparing the two strings in the custom compare function.
bool compare(const string x,const string y)
{
return (atoi((x+y).c_str))<(atoi((y+x).c_str));
}
call it as sort(array.begin(),array.end(),compare);
It's a well known solution. I wish to ask if you could formally prove it as well. It seems giving a ready-made solution may not be too much impressive over a concrete explanation (if it's been asked). Thanks.
When u r considering two strings, you are arranging it in such a way that it leads to the largest number possible.
Now, why it works for the complete array.
Just consider an analogy for sorting numbers.U compare and sort two numbers at a time and the sort algorithm make it valid over the complete array. Similarly, here we are comparing and making maximum value out of two numbers at a time and the sort algorithm is making the same valid over the complete array.
how do you prove if(compare(a, b) && compare(b, c)) then compare(a, c) == true? thank you
If you use atof instead of atoi, you can account for the case of 989 9 97, so that you get 998997 instead of 989997. Basically you are comparing floats instead of ints.
it wont work try a={9,97,1}if u r sorting in lexicographically decreasing order u wud get 9791 if increasing 1997.
u have to traverse the array once and bring all the numbers which have only 9's to the front and then sort the remaining portion in lexicographically decreasing order
here is a recursive solution for this problem
public static void main(String[] args)
{
int arr[] = {9, 97, 1};
StringBuffer buf = new StringBuffer();
for(int i = 0; i < arr.length; i++) {
buf.append(arr[i]);
}
extractLargeNumber("", buf.toString());
}
public static void extractLargeNumber(String st, String chars)
{
if (chars.length() <= 1)
{
value = Integer.parseInt(st + chars);
if(value > max) max = value;
}
else
{
for (int i = 0; i < chars.length(); i++)
{
try {
String newString = chars.substring(0, i) + chars.substring(i + 1);
extractLargeNumber(st + chars.charAt(i), newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
This might work...
logic is to extract a max no with two integers in the array in each iteration then add it to the global optNo to make it max
which will contains the final max no.
#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
std::string optNo;
bool
cmp(const std::string f, const std::string s)
{
if( atoi(f.c_str()) > atoi(s.c_str()) )
return true;
else
return false;
}
std::string
GetOptByCmp(const std::string f, const std::string s) {
if(cmp(f+s,s+f))
return f+s;
else
return s+f;
}
int
main()
{
int a[]={0, 10, 9, 100, 6};
int n=5, s;
char buf[30], buf1[30];
std::string tmp,ltmp;
unsigned char c;
for(int i=0; i<n; i++)
{
if(a[i] <0)
continue;
sprintf(buf, "%d", a[i]);
tmp=buf;
for(int k=0; k<n; k++)
{
if(k==i || a[k]<0)
continue;
sprintf(buf1, "%d", a[k]);
if( cmp(ltmp=GetOptByCmp(buf, buf1), tmp) )
{
tmp= ltmp; s= k;
}
}
a[i] = -1;
a[s] = -1;
optNo=GetOptByCmp(optNo, tmp);
}
std::cout << "Max No: " << optNo << std::endl;
}
return 0;
}
Convert to a String array and use custom comparator
@Override
public int compare(String aStr, String bStr) {
int aLen = aStr.length();
int bLen = bStr.length();
if (aLen == 1 && bLen > 1) {
String bFirst = bStr.substring(0, 1);
if (aStr.equals(bFirst)) {
return -1;
}
}
if (aLen > 1 && bLen == 1) {
String aFirst = aStr.substring(0, 1);
if (bStr.equals(aFirst)) {
return 1;
}
}
int compare = aStr.compareTo(bStr);
if (compare > 0) {
return -1;
} else if (compare < 0) {
return 1;
} else {
return 0;
}
}
Please check this code
#include<stdio.h>
int compare(char *s1,char *s2)
{
if(s1 == NULL && s2 == NULL)
return 0;
if(s1 == NULL)
return -1;
if(s2 == NULL)
return 1;
while(*s1 && *s2)
{
if(*s1 < *s2)
return -1;
if(*s1 > *s2)
return 1;
s1++;
s2++;
}
if(*s1)
return 1;
if(*s2)
return -1;
return 0;
}
char *itoa(char *str,int a)
{
char *result=str,*start=str,*end;
int mod=0;
if(a<0)
{
*str = '-';
start++;
str++;
a=-a;
}
while(a >= 10)
{
mod = a%10;
a = a/10;
*str = 48 + mod;
str++;
}
*str = 48 + a;
end=str;
*(str+1)='\0';
while(start < end)
{
*start = *start ^ *end;
*end = *start ^ *end;
*start = *start ^ *end;
start++;
end--;
}
return result;
}
char* concat(char *s1,char *s2)
{
if(s1 == NULL && s2 == NULL)
return NULL;
if(s1 == NULL)
return s2;
if(s2 == NULL)
return s1;
char *result=s1;
while(*s1)
{
s1++;
}
while(*s2)
{
*s1=*s2;
s1++;
s2++;
}
*s1=*s2;
return result;
}
void sort(int a[],int n)
{
int i=0,j=0;
char *s1=(char*)malloc(1024);
char *s2=(char*)malloc(1024);
char *s3=(char*)malloc(1024);
char *s4=(char*)malloc(1024);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(compare( concat(itoa(s1,a[i]),itoa(s2,a[j])), concat(itoa(s3,a[j]),itoa(s4,a[i])) )==-1)
{
a[i] = a[i]^a[j];
a[j] = a[i]^a[j];
a[i] = a[i]^a[j];
}
}
}
}
int main()
{
int a[]={10,9};
int n=2,i=0;
sort(a,n);
for(i=0;i<n;i++)
{
printf("%d",a[i]);
}
return 0;
}
Feedbacks are welcome.
In question it is given that :
2 3 5 78
ans: 78532
Infact answer should be 87532 right ?
1. find the elements which are single digit and sort it
2. compare the highest element in step #1 with first digit of the 2 digit #
2.a. if it's higher place all 1 digit numbers followed by the 2 digit
2.b. else, place 2 digit # first followed by 1 digit numbers
this works in array having many 1 digit numbers and only 1 two digit number
just to follow up with the above answer, if we an array containing variation of numbers like: 5, 6, 70, 80, 900, 950 (numbers of different digits)
all we need to do is find out the largest number we can generate for 1 digit, 2 digit, 3 digit. and then sort those sub-problem answers based on the first digit.
for array 5,6,70,80,900,950
1 digit: 65 [1st digit is 6]
2 digit: 8070 [1st digit is 8]
3 digit: 950900 [1st digit is 9]
now look at the 1st digit of the above sub-problem answer and then sort them to get final answer:
final answer:
950900807065
- - -
such a horrible solution. If u r trying to promote your blog at least have the content on your blog correct
The following code does it. It sorts the list based on a custom comparator. The code is quiet self explanatory.
/* The class name doesn't have to be Main, as long as the class is not public. */
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;
class MyComp implements Comparator<Integer> {
public int compare(Integer a1, Integer b1) {
String a = a1.toString();
String b = b1.toString();
int min = Math.min(a.length(),b.length());
for(int i = 0;i<min;i++) {
if(a.charAt(i) > b.charAt(i))
return -1;
}
if(a.length() > b.length()) return 1;
return -11;
}
}
class LexicographicSortOfNumbers {
LexicographicSortOfNumbers() {
}
static void main(String args[]) {
int arr[] = {1,9,98};
TreeSet<Integer> ts = new TreeSet<Integer>(new MyComp());
ts.add(1);
ts.add(98);
ts.add(9);
for (Integer element : ts) {
System.out.print(element + " ");
}
}
}
The following code does it. It sorts the list based on a custom comparator. The code is quiet self explanatory.
/* The class name doesn't have to be Main, as long as the class is not public. */
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;
class MyComp implements Comparator<Integer> {
public int compare(Integer a1, Integer b1) {
String a = a1.toString();
String b = b1.toString();
int min = Math.min(a.length(),b.length());
for(int i = 0;i<min;i++) {
if(a.charAt(i) > b.charAt(i))
return -1;
}
if(a.length() > b.length()) return 1;
return -11;
}
}
class LexicographicSortOfNumbers {
LexicographicSortOfNumbers() {
}
static void main(String args[]) {
int arr[] = {1,9,98};
TreeSet<Integer> ts = new TreeSet<Integer>(new MyComp());
ts.add(1);
ts.add(98);
ts.add(9);
for (Integer element : ts) {
System.out.print(element + " ");
}
}
}
Run through the array and select only the elements that have the largest leftmost digit. These elements are possible candidates to lead off the largest number. Imagine left-aligning all these elements. Now look at the next leftmost digit. If an element does not have a next leftmost digit, append an unused element to it in all possible ways, thereby expanding the list. Once all the candidates have at least a next leftmost digit, run through the list again and select only the elements that have the largest next leftmost digit. You can see where this is going: at each step we are figuring out the next leading digit for the largest number, appending with elements whenever needed to make sure we can make a selection from the list of possible candidates. The list of candidates will expand as we append elements and shrink as we eliminate them as being prefixes for the largest number. The prefixes themselves will grow in a jagged way but at the very end we will arrive at one number (or list of identical numbers), which will be largest possible.
<pre lang="" line="1" title="CodeMonkey22622" class="run-this">import java.util.Arrays;
import java.util.Comparator;
/**
* @author jk
* Given an integer array, sort the integer array such that the concatenated
* integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1]
* where the result integer is 9944141
*/
public class G61SortArrayForMaxValue {
/**
* @param a
* @returns the sorted integer
*/
public static Integer[] sortArrayForMaxValue(Integer[] a) {
// lexicographically comparator
final Comparator<Integer> c = new Comparator<Integer>() {
public int compare(Integer v1, Integer v2){
return v2.toString().compareTo(v1.toString());
}
};
Arrays.sort(a, c);
return a;
}
public static void main(String[] args) {
Integer[] a = {4, 94, 9, 14, 1};
Integer[] r = sortArrayForMaxValue(a);
for (int i = 0; i < r.length; i++) {
System.out.printf("%d ", r[i]);
}
}
}
</pre><pre title="CodeMonkey22622" input="yes">
</pre>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void concatinate(int a[], int n)
{
char s[100];
int t1, t2;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
sprintf(s, "%d%d",a[i],a[j]);
t1 = atoi(s);
sprintf(s, "%d%d",a[j],a[i]);
t2 = atoi(s);
if(t1 < t2)
swap(&a[i], &a[j]);
}
}
}
int main(void)
{
int a[] = {4, 94, 9, 14, 1};
concatinate(a, 5);
for(int i = 0; i < 5; i++)
{
cout << a[i];
}
cout << endl;
}
Traverse the integer array. While traversing find out number of 9s, 8s, 7s and so on. Finally print a string with number of 9s found + number of 8s found and so on
Java code
void printLargetNumber(int[] array) {
String[] numbers = new String[10];
for (int i=0; i<array.length; i++) {
String number = array[i] + "";
for (int j=0; j<number.length(); j++) {
numbers[number.charAt(j) - '0'] += number.charAt(j) + "";
}
}
for (int i=9; i>=0; i--) {
if (numbers[i].length() > 0)
System.out.print(numbers[i]);
}
}
I think we can adopt this solution:
First, we extend the number in the array into a N digit number. The “extend” way is like this, say N=3,
78, MSB=7, extend(78)=788; // we put MSB at the end
3, MSB=3, extend(3) =333;
101 MSB=1, extend(101)=101;
Then we can simply sort the array by the extended value of the array element, then print them out;
The code is like this:
int extend( int A, int N)
{
int temp=A;
int digit=1;
while(A/10) {A=A/10;digit++;}
int MSB= A;
int base=1;
int z=N-digit;
while(z--)
{
temp= temp*10+MSB;
}
return temp;
}
void specialsort( int* m, int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
{
if( extend(m[i],3)<extend(m[j],3) )
{
m[i]= m[i]^m[j];
m[j]= m[i]^m[j];
m[i]= m[i]^m[j];
}
}
}
void showtable( int *m, int n)
{
for(int i=0;i<n;i++)
cout<<m[i];
cout<<endl;
}
I think we can adopt this solution:
First, we extend the number in the array into a N digit number. The “extend” way is like this, say N=3,
78, MSB=7, extend(78)=788; // we put MSB at the end
3, MSB=3, extend(3) =333;
101 MSB=1, extend(101)=101;
Then we can simply sort the array by the extended value of the array element, then print them out;
The code is like this:
int extend( int A, int N)
{
int temp=A;
int digit=1;
while(A/10) {A=A/10;digit++;}
int MSB= A;
int base=1;
int z=N-digit;
while(z--)
{
temp= temp*10+MSB;
}
return temp;
}
void specialsort( int* m, int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
{
if( extend(m[i],3)<extend(m[j],3) )
{
m[i]= m[i]^m[j];
m[j]= m[i]^m[j];
m[i]= m[i]^m[j];
}
}
}
void showtable( int *m, int n)
{
for(int i=0;i<n;i++)
cout<<m[i];
cout<<endl;
}
Sort the array with a new comparator that when comparing two integers, concat them as strings in different order before comparing. For example, compare 9 and 91 becomes comparing "991" and "919" and thus 9 is great than 91. Java code below:
public int compare(Integer a, Integer b) {
String s1 = a.toString() + b.toString();
String s2 = b.toString() + a.toString();
int c = s1.compareTo(s2);
return -c;
}
given two number x, y. we should find the first digits from left to right which i.digit is different from y.digit.
here is the code.
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int i, int j)
{
int a[100];
int b[100];
int n1, n2;
if (i == 0)
{
a[0] = 0;
n1 = 1;
}
else
{
for (n1 = 0; i; ++n1)
{
a[n1] = i % 10;
i /= 10;
}
}
if (j == 0)
{
b[0] = 0;
n2 = 1;
}
else
{
for (n2 = 0; j; ++n2)
{
b[n2] = j % 10;
j /= 10;
}
}
for (--n1, --n2; n1 >= 0 && n2 >= 0; --n1, --n2)
{
if (a[n1] != b[n2])
{
break;
}
}
int s1, s2;
if (n1 >= 0 && n2 >= 0)
{
s1 = a[n1];
s2 = b[n2];
}
else if (n1 < 0 && n2 >= 0)
{
while (n2 >= 0)
{
if (a[0] == b[n2])
{
--n2;
}
else
{
break;
}
}
if (n2 >= 0)
{
s1 = a[0];
s2 = b[n2];
}
else
{
s1 = a[0];
s2 = b[0];
}
}
else if (n1 >= 0 && n2 < 0)
{
while (n1 >= 0)
{
if (a[n1] == b[0])
{
--n1;
}
else
{
break;
}
}
if (n1 >= 0)
{
s1 = a[n1];
s2 = b[0];
}
else
{
s1 = a[0];
s2 = b[0];
}
}
else
{
s1 = a[0];
s2 = b[0];
}
return s1 > s2;
}
void reorder(int *array, int n)
{
sort(array, array + n, cmp);
for (int i = 0; i < n; ++i)
{
cout << array[i];
}
cout << endl;
}
int main()
{
int n;
cin >> n;
int array[1000];
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
reorder(array, n);
return 0;
}
Lexicographical Sort :
#include<stdio.h>
#include<string.h>
char a[][5]={"9","99","91","5","59","8","81","4","44","21"};
void swap(int i,int j)
{
char temp[5];
strcpy(temp,a[i]);
strcpy(a[i],a[j]);
strcpy(a[j],temp);
}
void quicksort(int beg,int end)
{
char pivot[5];
int i,j;
strcpy(pivot,a[beg]);
if(beg<end)
{
i=beg;
j=end+1;
while(i<j)
{
while(i<end)
{
++i;
if(strcmp(a[i],pivot)>0)
break;
}
while(j>beg)
{
--j;
if(strcmp(a[j],pivot)<0)
break;
}
if(i<j)
swap(i,j);
}
swap(j,beg);
quicksort(beg,j-1);
quicksort(j+1,end);
}
}
int main()
{
int i;
quicksort(0,9);
for(i=9;i>=0;i--)
printf("%s",a[i]);
return 0;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
char a[][4]={"9","99","91","5","59","8","81","4","44","21"};
void swap(int i,int j)
{
char temp[5];
strcpy(temp,a[i]);
strcpy(a[i],a[j]);
strcpy(a[j],temp);
}
void quicksort(int beg,int end)
{
char pivot[5];
int i,j;
strcpy(pivot,a[beg]);
if(beg<end)
{
i=beg;
j=end+1;
while(i<j)
{
while(i<end)
{
++i;
if(strcmp(a[i],pivot)>0)
break;
}
while(j>beg)
{
--j;
if(strcmp(a[j],pivot)<0)
break;
}
if(i<j)
swap(i,j);
}
swap(j,beg);
quicksort(beg,j-1);
quicksort(j+1,end);
}
}
int main()
{
int i;
quicksort(0,9);
for(i=9;i>=0;i--)
printf("%s",a[i]);
getch();
return 0;
}
Java Code
public static void quickSort(int a[]){
if(a==null||a.length<2)return;
quicksort(a,0,a.length-1);
}
private static void quicksort(int a[],int start, int end){
if(end<=start)return;
int j = partition(a, start, end);
quicksort(a,start,j-1);
quicksort(a,j+1,end);
}
private static int partition(int a[],int start,int end){
int i = start;
int j = end+1;
int pivot = a[start];
while(true){
while(compareMax(a[++i],pivot)<0)
if(i==end)break;
while(compareMax(pivot,a[--j])<0)
if(j==start)break;
if(i>=j)break;
swap(a,i,j);
}
//put pivot in the correct position;
swap(a,start,j);
return j;
}
private static int compareMax(int i,int j){
int ij = Integer.valueOf(String.valueOf(i).concat(String.valueOf(j)));
int ji = Integer.valueOf(String.valueOf(j).concat(String.valueOf(i)));
if(ij<ji)
return 1;
if(ij==ji)return 0;
return-1;
}
def cmplt(a, b):
sa = str(a)
sb = str(b)
return int(sa+sb) < int(sb+sa)
def mins(a, s):
currmin = 0
for i in range(s):
if cmplt(a[i], a[currmin]):
currmin = i
return currmin
def arrange(a):
for i in range(len(a), 0, -1):
m = mins(a, i)
t = a[i-1]
a[i-1] = a[m]
a[m] = t
return a
Here is my approach :-
1. Sort array according to the first digit of each number
(for given input, it should be - 94, 9, 4, 1, 14, keeping order is not necessary)
2. Now run a loop from i=0 to n-1 elements , pick pair each time (like 0, 1 then 1, 2....)
if(no. of digits of a and b are equal)
continue
else // formNum(a, b) - form a number eg, formNum(74, 23) - 7423
if(formNum(a, b) < formNum(b, a)
swap(a, b);
Now just print that array, we get the largest number.
Here's the code
/*
Given an integer array, sort the integer array such that the concatenated
integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted
to [9,94,4,14,1] where the result integer is 9944141
*/
#include<iostream>
using namespace std;
int digits(int num)
{
if(!num)
return 0;
int count = 0;
while(num)
{
num /= 10;
count++;
}
return count;
}
int formNum(int a, int b)
{
int digA = digits(a);
int digB = digits(b);
int factor = 1;
for(int i=0;i<digB;i++)
factor = 10*factor;
return (a*factor + b);
}
int MSB(int num)
{
if(num<=9)
return num;
else
{
while(num>=10)
num /= 10;
}
return num;
}
void function(int arr[], int size)
{
for(int i=0;i<size;i++)
{
for(int j=i+1;j<=size;j++)
{
if(MSB(arr[i]) < MSB(arr[j]))
swap(arr[i], arr[j]);
}
}
for(int i=0;i<size;i++)
{
if(digits(arr[i]) == digits(arr[i+1]))
continue;
else
{
if(formNum(arr[i], arr[i+1]) < formNum(arr[i+1], arr[i]))
swap(arr[i], arr[i+1]);
}
}
cout<<" Number is :- ";
for(int i=0;i<=size;i++)
cout<<arr[i];
cout<<endl;
}
int main()
{
int arr[] = {9,99,91,5,59,8,81,4,44,21};
int size = sizeof(arr)/sizeof(*arr);
function(arr, size-1);
system("PAUSE");
return 0;
}
Please comment on the approach. I know, i get the right answer but i just want your comments on approach.
Sort them lexicographically can yield a wrong result. So to say "14" is greater than "1" so if we sort from high to low then we will put "14" followed by "1". To solve this is to write a special class which implements Comparable. In compareTo() we need to do the following.
public static class wiredInt implements Comparable{
String val;
public wiredInt(int v){ val = ""+v;}
@Override
public int compareTo(Object arg0) {
String other = ((wiredInt) arg0).val;
for(int i=0;i<val.length();i++){
if(i == other.length()) return 1;
if(val.charAt(i) < other.charAt(i)) return 1;
if(val.charAt(i) > other.charAt(i)) return -1;
}
return 1;
}
public String toString(){return val;}
}//end class
After that, simply cast the int array to this class and simply use sort it. (see below)
/**
* Sort the integer array such that the concatenated integer of the
* result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to
* [9,94,4,14,1] where the result integer is 9,944,141
* @param intarray
*/
public static void wiredSort(int[] intarray){
Vector<wiredInt> intArray_ = new Vector<wiredInt>();
for(int i=0;i<intarray.length;i++)
intArray_.add(new wiredInt(intarray[i]));
java.util.Collections.sort(intArray_);
for(int i=0;i<intarray.length;i++)
System.out.print(intArray_.get(i));
}
Logic in descending order quick sort with compartor
Am working on the radix sort MSB thingy, any smarter ideas
bool is_lesser(int* A, int i, int j)
{
std::stringstream str1;
str1 << A[i] << A[j];
std::stringstream str2;
str2 << A[j] << A[i];
return atoi(str1.str().c_str()) > atoi(str2.str().c_str());
}
// descending order
// greater ... pivot .. lesser
// 7, 8, 98, 979, 40, 14, 4, 99
// 8, 7
int partition(int *A, int p, int q)
{
if(p>=q)
{
return p;
}
int pivot = A[p], i = p, j = p+1;
while(j<=q)
{
if(is_lesser(A, p, j))
{
j++;
}
else
{
swap_(A, i+1, j);
j++; i++;
}
}
swap_(A, p, i);
return i;
}
void quicksort(int *A, int p, int q)
{
if(p >= q)
return;
int r = partition(A, p, q);
if(r > q)
return;
quicksort(A, p, r-1);
quicksort(A, r+1, q);
}
int main(int argc, char* argv[])
{
static const int N = 8;
int A[N] = {99, 87, 77, 14, 4, 43, 98, 9};
std::cout << "initial array ";
for(int i=0; i<N; ++i)
std::cout << A[i] << " ";
std::cout << std::endl;
quicksort(A, 0, N-1);
for(int i=0; i<N; ++i)
std::cout << A[i] << " ";
std::cout << std::endl;
return 0;
}
I think the answer is simple, unless i missed something really big:
quick sort the input BUT while comparing two inputs A and B instead of doing the regular A > B, DO THIS if(ToInt('AB') > ToInt('BA')) return 1 else -1;Example:
- Kishore February 18, 2011The idea is why would you chose '9' over '94'. All I have to check is whether '994' is greater than '949'. I hope that is clear. Once you sort them by this fashion, you have the sorted list. Just concatenate to get the answer.
I tried on few inputs. Let me know if this does not work or needs tweaking.