Google Interview Question
Country: United States
@hellohello
Does your function return true if str1 is "bigger" than str2? such as '9' is bigger than '918'? So '9' should be selected first and then '918' appended to it?
Could you please run your function on str1='81' and str2='811' and then swap str1 and str2? I think it will return 'true' in both cases, unless I misunderstood your code. Hard to understand because indentation is gone. Could you please enclose it in {{ { and } }} and repost?
@blckembr you are right. Here is properly indented code with the bug you pointed out fixed.
{{
def compare(str1, str2):
i = 0;
n = len(str1)
m = len(str2)
c1 = ''
c2 = ''
while i < max(n,m):
if i < n: c1 = str1[i]
if i < m: c2 = str2[i]
if(c1 == c2) continue;
return c1 > c2
return n < m
}}
public int concateListOfInt(List<Integer> intList) {
Collections.sort(intList, (a, b) -> {
return lexicalCompareInt(a, b);
})
}
private int lexicalCompareInt(int a, int b) {
int digitA = findHowManyDigit(a);
int digitB = findHowManyDigit(b);
while(digitA >= 1 || digitB >= 1) {
if(getValueForDigit(a, digitA) > getValueForDigit(b, digitB)) {
return 1;
} else if (getValueForDigit(a, digitA) < getValueForDigit(b, digitB)) {
return -1;
} else {
if(digitA > 1)
--digitA;
if(digitB > 1)
--digitB;
}
}
}
private int findHowManyDigit(int value) {
return Math.log10(value) + 1;
}
private int getValueForDigit(int input, int digit) {
return intput / (10 ^ --digit);
}
public int concateListOfInt(List<Integer> intList) {
Collections.sort(intList, (a, b) -> {
return lexicalCompareInt(a, b);
})
}
private int lexicalCompareInt(int a, int b) {
int digitA = findHowManyDigit(a);
int digitB = findHowManyDigit(b);
while(digitA >= 1 || digitB >= 1) {
if(getValueForDigit(a, digitA) > getValueForDigit(b, digitB)) {
return 1;
} else if (getValueForDigit(a, digitA) < getValueForDigit(b, digitB)) {
return -1;
} else {
if(digitA > 1)
--digitA;
if(digitB > 1)
--digitB;
}
}
}
private int findHowManyDigit(int value) {
return Math.log10(value) + 1;
}
private int getValueForDigit(int input, int digit) {
return intput / (10 ^ --digit);
}
R
maxConcat <- function(s) {
s1 <- unique(as.matrix(expand.grid(s,s,s)))
s2 <- s1[(apply(s1, 1, FUN = function(x) length(unique(x))) == 3),]
s3 <- apply(s2, 1, FUN = function(x) paste0(x, collapse = ''))
return(s3[which.max(as.numeric(s3))])
}
x1 <- c('9', '918', '917')
maxConcat(s = x1)
x2 <- c('1','112','113')
maxConcat(s = x2)
Brute force approach would be to check for all possible outcomes. If there are n numbers, they could be combined in n! different ways. Now, we can sort these n! numbers in n!*log(n!) time using comparison based sorting. This probably isn't good enough for even a decent number of numbers. We need to find a better approach.
c# implementation.
using System;
using System.Collections.Generic;
namespace GreatestByConcatenation {
public class MyComparer : IComparer<int> {
public int Compare( int x, int y ) {
if ( x == 0 ) {
return 1;
}
if ( y == 0 ) {
return -1;
}
int numOfDigitsX = (int)Math.Floor( Math.Log10( x ) + 1 );
int numOfDigitsY = (int)Math.Floor( Math.Log10( y ) + 1 );
int XconcatY = (int) ( x * ( Math.Pow( 10, numOfDigitsY ) ) + y );
int YconcatX = (int) ( y * ( Math.Pow( 10, numOfDigitsX ) ) + x );
return XconcatY > YconcatX ? -1 : 1;
}
}
class Program {
private static string GetGreatestByConcatenation( int[] arr ) {
Array.Sort( arr, new MyComparer() );
string greatest = string.Empty;
for ( int i = 0; i < arr.Length; i++ ) {
greatest += arr[ i ];
}
return greatest;
}
static void Main(string[] args) {
//var arr = new int[] { 1, 112, 113 };
var arr = new int[] { 9, 918, 917 };
string greatest = GetGreatestByConcatenation( arr );
Console.WriteLine( greatest );
Console.ReadLine();
}
}
}
Not sure , what you are trying to do here.
public int Compare( int x, int y ) is not getting called anywhere.
Array.Sort( arr, new MyComparer() ); Sorting array will not give you the answer
Collections.sort(li,new Comparator<String>(){
public int compare(String a,String b){
int i=0,j=0;
while(i<a.length() && j<b.length()){
if(Integer.parseInt(a.substring(i,i+1))>Integer.parseInt(b.substring(j,j+1))){
return -1;
}else if(Integer.parseInt(a.substring(i,i+1))<Integer.parseInt(b.substring(j,j+1))){
return 1;
}else{
if(i+1>a.length() && j+1>b.length()){
return 0;
}
if(i+1<a.length()){
i++;
}else{
i=0;
}
if(j+1<b.length()){
j++;
}else{
j=0;
}
}
}
return 0;
}
});
def compare(str1,str2):
a=len(str1)
b=len(str2)
temp=min(a,b)
for i in range(temp):
if(str1[i]<str2[i]):
return str2
if(str1[i]>str2[i]):
return str1
if(str1[i]==str2[i]):
continue
if(a<b):
return str1
else:
return str2
Here is my code for compare. Although i am able to compare properly but not able to use it perfectly in my program. below is my code for main. can please anyone check what is my mistake. Thanks.
array=[]
arr=[]
final=[None] * 5
array=input()
str3=''
arr=map(str,array)
length=len(arr)
print(array)
print(arr)
for i in range(0,length):
count=length-1
for j in range(0,length):
srt3 = str(compare(arr[i],arr[j]))
print(str3)
if(str3 == arr[i]):
count=count-1
print(count)
final[count]=arr[i]
print(final)
def compare(str1,str2):
a=len(str1)
b=len(str2)
temp=min(a,b)
for i in range(temp):
if(str1[i]<str2[i]):
return str2
if(str1[i]>str2[i]):
return str1
if(str1[i]==str2[i]):
continue
if(a<b):
return str1
else:
return str2
Here is my code which i think works fine. The problem is that i am not able to use it properly in this problem. The main (or rest of the implementation of my program) is below. Please check the code below and tell me where i am wrong.
array=[]
arr=[]
final=[None] * 5
array=input()
str3=''
arr=map(str,array)
length=len(arr)
print(array)
print(arr)
for i in range(0,length):
count=length-1
for j in range(0,length):
srt3 = str(compare(arr[i],arr[j]))
print(str3)
if(str3 == arr[i]):
count=count-1
print(count)
final[count]=arr[i]
print(final)
long concat(vector<long>& data)
{
ostringstream oss;
std::sort(data.begin(), data.end(), [&data](long i, long j) -> bool {
ostringstream a, b;
a << i << j;
b << j << i;
return a.str() < b.str();
});
for (vector<long>::reverse_iterator it = data.rbegin(); it != data.rend(); it++)
oss << *it;
istringstream iss(oss.str());
long result;
iss >> result;
return result;
}
Java Code:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class HighestValue {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input[]=new String[]{"9","918","917"};
//String input[]=new String[]{"1","112","113"};
//String input[]=new String[]{"8","991", "89", "51", "5", "0"};
List<String> ls=new LinkedList<String>();
//ls.add(input[0]);
for(int i=0;i<=(input.length-1);i++){
int index=0;
Iterator it=ls.listIterator();
while(it.hasNext()){
String element=(String)it.next();
String str1=element+input[i];
String str2=input[i]+element;
if(str1.compareTo(str2)>0)
index++;
else
break;
}
ls.add(index, input[i]);
}
Iterator it1=ls.listIterator();
while(it1.hasNext()){
System.out.print(it1.next());
}
}
}
I used Linked List data structure in above code. TimeComplexity is O(n^2)
Convert each number to string representation, then sort the numbers in descending order, first comparing the first digit of each number with the others and then the last digit. The biggest number will have the first digit as biggest among all the numbers and also it's last digit. So question boils down to sorting the list of strings by first and last characters, in reverse order
def findHighestValue(l):
if l == None or len(l) == 0:
return None
str_list = map(lambda x: str(x), l)
str_list.sort(key = lambda x: (x[0], x[-1]), reverse=True)
return reduce(lambda x, y: x + y, str_list)
if __name__ == '__main__':
nums = map(lambda x: int(x), raw_input().split(" "))
print "Greatest number possible: ", findHighestValue(nums)
Pretty similar to what others have posted.
int concatenate(int[] nums) {
String[] nums2 = new String[nums.length];
int j = 0;
for (int a : nums) nums2[j++] = String.valueOf(a);
Comparator<String> c = (s1, s2) -> {
for (int i = 0; i < Math.max(s1.length(), s2.length()); i++) {
int i1 = Math.min(s1.length()-1, i);
int i2 = Math.min(s2.length()-1, i);
char n1 = s1.charAt(i1);
char n2 = s2.charAt(i2);
if (n1 != n2) return n2 - n1;
}
return 0;
};
Arrays.sort(nums2, c);
StringBuilder result = new StringBuilder();
for (String s : nums2) result.append(s);
return Integer.valueOf(result.toString());
}
Using a modified version of radix sort
public class MaxPermutation {
public static void main(String[] args) {
int[] numbers = new int[]{9,918,917};
//int[] numbers = new int[]{1,112,113};
//int[] numbers = new int[]{8,991,89,51,5,0};
//int[] numbers = new int[]{9015,901};
MaxPermutation.sort(numbers);
for (int i = 0; i < numbers.length / 2; i++) {
int temp = numbers[i];
numbers[i] = numbers[numbers.length - 1 -i];
numbers[numbers.length - 1 -i] = temp;
}
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i]+" ");
}
System.out.println();
}
public static void sort(int[] a)
{
int i, m = a[0], exp = 1, n = a.length;
int[] b = new int[10];
for (i = 1; i < n; i++)
if (a[i] > m)
m = a[i];
while (m / exp > 0)
{
int[] bucket = new int[10];
for (i = 0; i < n; i++) {
int exp_t = exp;
while (exp_t > 0 && a[i] / exp_t == 0) exp_t /= 10;
if (exp_t == 0) exp_t = 1;
bucket[(a[i] / exp_t) % 10]++;
}
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--) {
int exp_t = exp;
while (exp_t > 0 && a[i] / exp_t == 0) exp_t /= 10;
if (exp_t == 0) exp_t = 1;
b[--bucket[(a[i] / exp_t) % 10]] = a[i];
}
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
}
}
}
Here is the C++ solution running in O( n log n).
Approach is to sort the numbers in alphanumerical order and concatenate them.
e.g.) 9 come earlier than 918 since second number '1' in 918 is smaller than first number '9' of '9'.
Likely, 112 comes earlier than 1 because '2' of 112 is larger than '1' of '1'.
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
bool compare(string left, string right)
{
int lpos=0, rpos=0;
int len = (left.length()>right.length())? left.length(): right.length();
for (int i = 0; i < len; i++)
{
lpos = (i< left.length())? i: left.length()-1;
rpos = (i< right.length())?i: right.length()-1;
if (left[lpos] != right[rpos])
return left[lpos]> right[rpos];
}
}
void concatenate_biggest(vector<string> inputs)
{
string result;
sort(inputs.begin(), inputs.end(), compare);
for (int i = 0; i < inputs.size(); i++)
result+= inputs[i];
cout<<"resut = " <<result<<endl;
}
int main()
{
vector<string> inputs;
inputs.push_back("9");
inputs.push_back("918");
inputs.push_back("917");
concatenate_biggest(inputs);
inputs.clear();
inputs.push_back("1");
inputs.push_back("112");
inputs.push_back("113");
concatenate_biggest(inputs);
return 1;
}
C++11. I couldn't think of a better name for the sorting semantics.
/*
Given a list of integers, find the highest value obtainable by concatenating
these together.
For example, given 9, 918, 917 - The answer is 9918917.
But given 1,112,113 - The answer is 1131121
Written in C++11.
*/
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
// a < ab < ac < bb < b < cb < c < cd
template <typename Container>
struct pseudo_lexicographical_less
{
bool operator()(Container a, Container b) const
{
bool swapped = false;
if (b.size() < a.size())
{
swap(a, b);
swapped = true;
}
// a.size() <= b.size()
auto const p = mismatch(begin(a), end(a), begin(b));
if (p.first == end(a))
{
if (a.size() == b.size())
return false; // swap is irrelevant
else
{
auto const x = *(begin(b) + a.size() - 1);
auto const f = [&](char z) {
return z == x;
};
auto const q = find_if_not(begin(b) + a.size(), end(b), f);
return q == end(b) ? swapped : (*q < x) == swapped;
}
}
else
return (*p.first < *p.second) != swapped;
}
};
template <typename Container>
struct pseudo_lexicographical_greater
{
bool operator()(Container a, Container b) const
{
return pseudo_lexicographical_less<Container>()(b, a);
}
};
int main(int argc, char **argv)
{
if (argc < 2)
exit(EXIT_FAILURE);
vector<string> data(argv + 1, argv + argc);
sort(begin(data), end(data), pseudo_lexicographical_greater<string>());
for (auto i : data)
cout << i << " ";
cout << endl;
}
def compare(x,y):
x=str(x)
y=str(y)
if len(x)==len(y):
return int(x)>int(y)
l = max(len(x),len(y))
xy = (x+y)[:l]
yx = (y+x)[:l]
return int(xy)>int(yx)
def insertion_sort(arr):
for i in range(1,len(arr)):
key_val = arr[i]
scan_pos = i-1
while scan_pos>=0 and not compare(arr[scan_pos],key_val):
arr[scan_pos+1] = arr[scan_pos]
scan_pos -= 1
arr[scan_pos+1] = key_val
return arr
a = [9, 918, 917]
b = [1, 112, 113]
print "".join(map(str,insertion_sort(a)))
print "".join(map(str,insertion_sort(b)))
a = [9, 918, 917]
b = [1, 112, 113]
def compare(x,y):
x=str(x)
y=str(y)
if len(x)==len(y):
return int(x)>int(y)
l = max(len(x),len(y))
xy = (x+y)[:l]
yx = (y+x)[:l]
return int(xy)>int(yx)
def insertion_sort(arr):
for i in range(1,len(arr)):
key_val = arr[i]
scan_pos = i-1
while scan_pos>=0 and not compare(arr[scan_pos],key_val):
arr[scan_pos+1] = arr[scan_pos]
scan_pos -= 1
arr[scan_pos+1] = key_val
return arr
print "".join(map(str,insertion_sort(a)))
print "".join(map(str,insertion_sort(b)))
Convert integers to string. String s1 comes before s2 in concatenation if (s1+s2) > (s2+s1).
Code :
public class Solution {
public int getMaxNumber(int[] inputArray){
int n = inputArray.length;
String[] temp = new String[n];
for(int i = 0 ; i < n ; ++i ){
temp[i] = Integer.toString(inputArray[i]);
}
Arrays.sort(temp,new Comparator<String>(){
public int compare(String s1, String s2){
String a = s1+s2;
String b = s2+s1;
return b.compareTo(a);
}
});
String res = "";
for(String t : temp){
res+= t;
}
return Integer.parseInt(res);
}
public static void main(String[]s){
Solution ob = new Solution();
int[] ar = {9,91,907};
System.out.println(ob.getMaxNumber(ar));
}
}
public String sort(int[] a)
{
String[] ret=new String[a.length];
for(int i=0;i<ret.length;i++)
ret[i]=new Integer(a[i]).toString();
Arrays.sort(ret,new Comparator<String>()
{
public int compare(String x,String y)
{
return (y+x).compareTo(x+y);
}
});
StringBuilder sb=new StringBuilder();
for(String s:ret)
{
sb.append(s);
}
return sb.toString();
}
For questions like these I would prefer writing a Comparator class and then sort the given list of numbers using that comparator. Since conversion to String for a huge amount of number could be very memory inefficient. Below is the Java / Comparator Code:
/*
* @author shivam.maharshi
*/
public class HighestValueByConcantenation {
public static void getHighest(int[] a) {
List<Integer> list = new ArrayList<>();
for (int aa : a)
list.add(aa);
Collections.sort(list, new ConComp());
for (int aa : list)
System.out.print(aa);
}
public static void main(String[] args) {
// int[] a = {9, 918, 917};
int[] a = { 1, 112, 113 };
getHighest(a);
}
}
class ConComp implements java.util.Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
while (o1 != 0) {
l1.add(o1 % 10);
o1 = o1 / 10;
}
while (o2 != 0) {
l2.add(o2 % 10);
o2 = o2 / 10;
}
int i = l1.size() - 1;
int j = l2.size() - 1;
while (i >= 0 && j >= 0) {
if (l1.get(i) > l2.get(j))
return -1;
else if (l1.get(i) < l2.get(j))
return 1;
i--;
j--;
}
if (i != -1) {
int lastDigit = l1.get(i + 1);
while (i >= 0) {
if (l1.get(i) < lastDigit)
return 1;
else if (l1.get(i) > lastDigit)
return -1;
i--;
}
}
if (j != -1) {
int lastDigit = l2.get(j + 1);
while (j >= 0) {
if (l2.get(j) < lastDigit)
return -1;
else if (l2.get(j) > lastDigit)
return 1;
j--;
}
}
return 0;
}
}
C++ code:
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
struct MyCmp {
bool operator() (const string& a, const string& b) const
{
long long anum = atol(string(a + b).c_str());
long long bnum = atol(string(b + a).c_str());
return (anum > bnum);
}
} mycmp;
int main(int argc, char *argv[])
{
vector<string> nums;
for (int i=1; i< argc; i++)
nums.push_back(argv[i]);
if (nums.size() == 0) {
cout << "usage: " << string(argv[0]) << " str1 str2 ...";
throw string("try again ");
}
std::sort(nums.begin(), nums.end(), mycmp);
vector<string>::iterator itr = nums.begin();
for (;itr != nums.end(); itr++)
cout << *itr;
cout << endl;
return 0;
}
C++ code:
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
struct MyCmp {
bool operator() (const string& a, const string& b) const
{
long long anum = atol(string(a + b).c_str());
long long bnum = atol(string(b + a).c_str());
return (anum > bnum);
}
} mycmp;
int main(int argc, char *argv[])
{
vector<string> nums;
for (int i=1; i< argc; i++)
nums.push_back(argv[i]);
if (nums.size() == 0) {
cout << "usage: " << string(argv[0]) << " str1 str2 ...";
throw string("try again ");
}
std::sort(nums.begin(), nums.end(), mycmp);
vector<string>::iterator itr = nums.begin();
for (;itr != nums.end(); itr++)
cout << *itr;
cout << endl;
return 0;
}
class Solution {
public:
class vecComp {
public:
bool operator()(vector<int>& v1, vector<int>& v2) {
if (v1.size() == 0) return !(v2.size() == 0);
if (v2.size() == 0) return (v1.size() == 0);
int i = v1.size()-1, j = v2.size()-1;
while (i >=0 && j >= 0) {
if (v1[i] > v2[j]) return false;
if (v1[i] < v2[j]) return true;
if (v1[i] == v2[j]) {
if (i > 0) i--;
if (j > 0) j--;
}
}
return true;
}
};
int maxNum(vector<int> nums)
{
int ndigits = 0, ans = 0;
priority_queue<vector<int>, vector<vector<int>>, vecComp> digits;
for (int num : nums) {
vector<int> d;
while (num != 0) {
d.push_back(num%10);
num /= 10;
ndigits++;
}
digits.push(d);
}
int p = pow(10, ndigits - 1); // overflow!!!!
while (!digits.empty()) {
vector<int> d = digits.top();
digits.pop();
for (int i = d.size() - 1; i >= 0; i--) {
ans += p * d[i];
p /= 10;
}
}
return ans;
}
};
We need to handle something like:
{ 54, 5454546 } ==> 545454654
or
{ 45, 4545453 } ==> 454545453
So, in C++, the compare function should be:
bool Compare(const std::string &x, const std::string &y) {
int length = std::max(x.size(), y.size());
for (int i = 0; i < length; ++i) {
char charX = x[i % x.size()];
char charY = y[i % y.size()];
if (charX != charY) {
return charX > charY;
}
}
// equal
return true;
}
DP solution
public static void main(String ar[]){
TestMyCode t=new TestMyCode();
int[] a= {1,112,113};
System.out.println(t.maxNumber(a));
}
private int maxNumber(int[] a) {
// TODO Auto-generated method stub
if(a.length<=2){
return Math.max(concatinate(a[0], a[1]),concatinate(a[1], a[0]));
}
int max=Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
max= Math.max(concatinate(a[i], maxNumber(removeIthNumber(a,i))),
concatinate(maxNumber(removeIthNumber(a,i)),a[i]));
}
return max;
}
private int concatinate(int i, int j) {
// TODO Auto-generated method stub
int temp=j;
//int iC=0;
int jC=0;
while(temp!=0){
temp=temp/10;
jC++;
}
for(int k=1;k<=jC;k++){
i=i*10;
}
return i+j;
}
private int[] removeIthNumber(int[] a, int i) {
// TODO Auto-generated method stub
int[] result=new int[a.length-1];
for (int j = 0; j < result.length; j++) {
if(j==i)continue;
result[j]=a[j];
}
return result;
}
public static void main(String ar[]){
TestMyCode t=new TestMyCode();
int[] a= {1,112,113};
System.out.println(t.maxNumber(a));
}
private int maxNumber(int[] a) {
// TODO Auto-generated method stub
if(a.length<=2){
return Math.max(concatinate(a[0], a[1]),concatinate(a[1], a[0]));
}
int max=Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
max= Math.max(concatinate(a[i], maxNumber(removeIthNumber(a,i))),
concatinate(maxNumber(removeIthNumber(a,i)),a[i]));
}
return max;
}
private int concatinate(int i, int j) {
// TODO Auto-generated method stub
int temp=j;
//int iC=0;
int jC=0;
while(temp!=0){
temp=temp/10;
jC++;
}
for(int k=1;k<=jC;k++){
i=i*10;
}
return i+j;
}
private int[] removeIthNumber(int[] a, int i) {
// TODO Auto-generated method stub
int[] result=new int[a.length-1];
for (int j = 0; j < result.length; j++) {
if(j==i)continue;
result[j]=a[j];
}
return result;
}}
public static void main(String ar[]){
TestMyCode t=new TestMyCode();
int[] a= {1,112,113};
System.out.println(t.maxNumber(a));
}
private int maxNumber(int[] a) {
// TODO Auto-generated method stub
if(a.length<=2){
return Math.max(concatinate(a[0], a[1]),concatinate(a[1], a[0]));
}
int max=Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
max= Math.max(concatinate(a[i], maxNumber(removeIthNumber(a,i))),
concatinate(maxNumber(removeIthNumber(a,i)),a[i]));
}
return max;
}
private int concatinate(int i, int j) {
// TODO Auto-generated method stub
int temp=j;
//int iC=0;
int jC=0;
while(temp!=0){
temp=temp/10;
jC++;
}
for(int k=1;k<=jC;k++){
i=i*10;
}
return i+j;
}
private int[] removeIthNumber(int[] a, int i) {
// TODO Auto-generated method stub
int[] result=new int[a.length-1];
for (int j = 0; j < result.length; j++) {
if(j==i)continue;
result[j]=a[j];
}
return result;
}
Java code:
Function return type is String for avoiding overflow
import java.util.Arrays;
import java.util.Comparator;
import org.apache.commons.lang3.ArrayUtils;
public class MaxConcatenatedInteger {
public static String getMaxConcatenatedNumber(int[] numbers) {
final Integer[] sN = ArrayUtils.toObject(numbers);
Arrays.sort(sN, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
char[] digitsO1 = o1.toString().toCharArray();
char[] digitsO2 = o2.toString().toCharArray();
int n = Math.max(digitsO1.length, digitsO2.length);
char digit1 = 0;
char digit2 = 0;
for (int i = 0; i < n; i++) {
if (i < digitsO1.length)
digit1 = digitsO1[i];
if (i < digitsO2.length)
digit2 = digitsO2[i];
if (digit1 < digit2)
return 1;
if (digit1 > digit2)
return -1;
}
return 0;
}
});
StringBuffer sb = new StringBuffer();
for (int i = 0; i < sN.length; i++) {
sb.append(sN[i]);
}
return sb.toString();
}
public static void main(String[] args) {
int[] numbers = { 9, 918, 917 };
System.out.println("Result:" + getMaxConcatenatedNumber(numbers));
int[] numbers2 = { 1, 112, 113 };
System.out.println("Result:" + getMaxConcatenatedNumber(numbers2));
int[] numbers3 = { 8, 991, 89, 51, 5, 0 };
System.out.println("Result:" + getMaxConcatenatedNumber(numbers3));
}
}
The code does not work for 9015, 901
You take the last digit from the shorter number of compare it with the suffix of the shorter string. But you should compare the prefix of shorter string after you get to the end of the shorter string: you compare the 5 to 1, instead you should compare 9 (from 901) to 5.
public int concateListOfInt(List<Integer> intList) {
Collections.sort(intList, (a, b) -> {
return lexicalCompareInt(a, b);
})
}
private int lexicalCompareInt(int a, int b) {
int digitA = findHowManyDigit(a);
int digitB = findHowManyDigit(b);
while(digitA >= 1 || digitB >= 1) {
if(getValueForDigit(a, digitA) > getValueForDigit(b, digitB)) {
return 1;
} else if (getValueForDigit(a, digitA) < getValueForDigit(b, digitB)) {
return -1;
} else {
if(digitA > 1)
--digitA;
if(digitB > 1)
--digitB;
}
}
}
private int findHowManyDigit(int value) {
return Math.log10(value) + 1;
}
private int getValueForDigit(int input, int digit) {
return intput / (10 ^ --digit);
}
Convert the int's to string's. Then sort them using this function and concatenate.
- hellohello November 20, 2015To compare, find the first character by which they differ and compare them.
def compare(str1, str2):
i = 0;
n = len(str1)
m = len(str2)
c1 = ''
c2 = ''
while i < max(n,m):
if i < n: c1 = str1[i]
if i < m: c2 = str2[i]
if(c1 == c2) continue;
return c1 > c2
return true;