CareerCup

You can solve this problem by writing your own comparer for numbers.
You must sort the list using this comparer. And then just concatenate all the elements.

The main idea of comparer :
1. X > Y <=> XY > YX
2. X < Y <=> XY < YX
3. X = Y <=> XY = YX

Don't forget to take care of the overflowing. (In my implementation below I've assumed that overflowing is impossible)

Implementation using custom created comparer class:

class SpecialComparer : IComparer<int>
{
	public int Compare(int x, int y)
	{
		string xstr  = x.ToString();
		string ystr = y.ToString();

		string XY = xstr + ystr;
		string YX = ystr + xstr;

		// returns 
		//  positive number,	when YX > XY
		//  zero,				when YX = XY
		//  negative number,	when YX < XY
		return YX.CompareTo(XY);
	}
}

static int ComposeTheMaxNumbers(int[] numbers)
{
	SpecialComparer comparer = new SpecialComparer();

	Array.Sort(numbers, comparer);

	StringBuilder result = new StringBuilder();
	foreach (int number in numbers)
	{
		result.Append(number.ToString());
	}

	return int.Parse(result.ToString());
}

However, in C# we may just write a lambda and LINQs expressions:

static int ComposeTheMaxNumbers(int[] numbers)
{
	Array.Sort(numbers, new Comparison<int>((x, y) => (y.ToString() + x.ToString()).CompareTo(x.ToString() + y.ToString())));

	return int.Parse(numbers.Select(_ => _.ToString()).Aggregate((x, y) => x + y));
}

P.S. The second approach is ineffective because all the time we create string's objects. But I think you've got the idea.

Use MSD radix sort and concatenate the numbers in descending order.

Can't it be done by taking the most significant bit and appending the numbers together.

In the above case: {21,9,23}

highest first most significant bit is 9
then it's 2.. but 23 and 21 are same, so we take second most significant bit which is 23
hence 92321 is the answer.

To get the first digit of the number,

int firstDigit (int x) {
    while (x > 9) {
        x /= 10;
    }
    return x;
}

I just skimmed your response. I think it won't work for: 21, 9, 23, 91, 99.

Consider every number as string.
Then sort (descending) them with any sorting method. (Bucket sort can also be used as our string will only contain 0-9)
Once sorted, append each string in order to result string.
Convert result string to number again, which is nothing but maximum possible number.

E.G. {21,9,23} -> {"21","9","23"} ->{"9","23","21"} -> {"92321"} -> 92321

can't think of a efficient way to solve it, give a weird string solution here

public static int maxPermNum(int []arr)
	{
		if(arr == null || arr.length == 0)
			return -1;
	
		StringBuffer sb = new StringBuffer();
	
		for(int i=0; i<arr.length; i++) {
			
			int maxIdx = 0;
			for(int j=0; j<arr.length; j++) {
				if(arr[j] == -1)
					continue;
	
				if(digitComp(arr[j],arr[maxIdx])) {
					maxIdx = j;
				}
			}
	
			sb.append(arr[maxIdx]);
			arr[maxIdx] = -1;
		}
	
		return Integer.parseInt(sb.toString());
	}
	
	public static boolean digitComp(int num1, int num2)
	{
		String str1 = num1+"";
		String str2 = num2+"";
		
		int lenDiff = str1.length() - str2.length();
		String modiStr = lenDiff < 0 ? str1 : str2;
		
		for(int i=0; i<lenDiff; i++)
			modiStr += "9";
		
		boolean isLarger = str1.compareTo(str2)>0 ? true : false;
		return isLarger;
	}

May be do this:

1. Normalize each number to equal length by appending zeroes at the end. So we get something like:
{21,90,23}
2. Now sort it. We get:
{90,23,21}
3. Now reverse-normalize them i.e. remove the zeros that we appended in step 1. So we get: {9,23,21} which is the desired result.

Time complexity = O(nlogn) for sorting + O(n) pre-processing + O(n) post-processing = O(nlogn)
Space complexity = O(n)
where n is the number of elements in the array.

Tip: For performing step 1 of the algorithm, you'll need to find the number with max number of digits. You can find the number of digits in a number by taking log to the base 10.

The following code works if the input array contains integers less than hundred. however this can be genaralised according to the requirements of the interviewer.

void inteperm(int*a, int n){
	list<int> temp[3];
	for(int i=0;i<n;i++){
		if(a[i]/10 == 0)
			temp[0].push_back(a[i]);
		else if(a[i]/10 < 10)
			temp[1].push_back(a[i]);
		else if(a[i]/100 < 10)
			temp[2].push_back(a[i]);
	}
	for(int i=0;i<3;i++)
		temp[i].sort(comp);
	list<int>::iterator it,it1,it2,it3;
	it1 = temp[0].begin();
	it2 = temp[1].begin();

	int k,l,res = 0;
	while(!temp[0].empty()){
		k = *(it1);
		while(*it1 == k){
			res = res*10 + k;
			it1 = temp[0].erase(it1);
		}
		k *= 10;
		res *= 10;
		l = *it2;
		while(l >= k){
			while(*it2 == l){
				res = res*10 + l;
				it2 = temp[1].erase(it2);
			}
			l = *it2;
		}
	}
	cout<<res<<endl;
}

Use MSD radix sort and "concatenate" the numbers in descending order.

Here any sorting algorithm will work but the main thing is that in case of comparision between two number we compare the Most significant digit of two numbers, if there is tie than we compare next digit of nos.
Here is my code. I have used quick sort.

#include<stdio.h>
 
int reverse(int x)
  {
     int r,rv;
     rv=0; 
      while(x!=0)
       {
         r=x%10;
         rv=rv*10 +r;
         x=x/10;
      }
      return rv;


 }
                                
 int comp(int a, int b)          // return 1 if Most most significant digit of a is greater most significant digit of b 
 {                               // if tie than check for next digit
     int x,y;
     x=reverse(a);               // reverse both no first for accessing the digit in right to left manner
     y=reverse(b);               //if a=9 and b=90 than x=9 and y=9
   
 
     while((x !=0) && (y!=0))
       {
          if((x%10)> (y%10))
            return 1;
          else if((x%10) < (y%10))
             return 0;
          x=x/10;
          y=y/10;

       }
     if(x==0 && y==0)                         
       { if(a<b) return 1; else return 0;   } 
         
    else if(x==0)
      return 1 && (a%10);
     
    else 
      return 1  && !(b%10);



 }

  void print_array(int *ar, int n)
   {
      int i;
      for(i=n-1;i>=0;i--)
   {
       printf("%d  ",ar[i]);

   

   } 

    }
 

 int split(int *ar,int lower,int upper)
{
   int i,p,q,t;
   p= lower+1;
   q= upper;
   i=ar[lower];

    while(q>= p)
     {

       while(comp(i,ar[p]))
        p++;
      
       while(comp(ar[q],i))
        q--;  
  
       if(q>p)
        {
          t=ar[p];
          ar[p]=ar[q];
          ar[q]=t; 

        }

    

    }



         t=ar[lower];
         ar[lower]=ar[q];
         ar[q]=t;
  return q;

}


 void quick_sort(int * ar, int lower,int upper)
 {    int i;
    if(upper > lower)
      {
        i= split(ar,lower,upper);
        quick_sort(ar,lower,i-1);
        quick_sort(ar,i+1,upper);
      }
     
 }





int main()
{
   int ar[10],i,n;
     
   printf("Enter how many no :  \n");
   scanf("%d",&n);
   
   for(i=0;i<n;i++)
     {
      printf("enter no %d : ",i+1);
      scanf("%d",&ar[i]);
      printf("\n");

     }    

     quick_sort(ar,0,n-1);
    print_array(ar,n);
    

}



 test:
     Enter how many no :  
7
enter no 1 : 0

enter no 2 : 90

enter no 3 : 89

enter no 4 : 99

enter no 5 : 900

enter no 6 : 990

enter no 7 : 99000

99  990  99000  90  900  89  0 



Enter how many no :  
5
enter no 1 : 99

enter no 2 : 91

enter no 3 : 22

enter no 4 : 21

enter no 5 : 9

9  99  91  22  21

String[] input= {"9","2","80","86"};
List<String> wordList = Arrays.asList(input);
Collections.sort(wordList);
StringBuffer result = new StringBuffer();
for(int i = wordList.size()-1 ; i >= 0 ; i--)
result.append(wordList.get(i));
System.out.println(result);

Please comment if solution is not feasible.

convert the int elements into string elements and sort them(like words)
e.g
> input {21,9,23}
> convert into array of String {21,9,23}
> sort the array of String {9,23,21}
>make a complete String(92321) from array and convert it into integer

// Find max number which can be formed from an array

#include <iostream>
#include <conio.h>

using namespace std;

struct Node
{
	int data;
	Node *next;

	Node(int data)
	{
		this->data = data;
		this->next = NULL;
	}

	~Node()
	{
		if (this->next)
		{
			delete this->next;
		}

		this->next = NULL;
	}
};

int no_of_digits(int num)
{
	int digits = 0;

	do
	{
		num = num / 10;

		++digits;
	}
	while(num > 0);

	return digits;
}

int get_digit(int num, int pos, int ndigits)
{
	if (ndigits > 1)
	{
		int value = num;
		int digit = num;

		while((ndigits - pos) > 0)
		{
			digit = value % 10;
			value = value / 10;
			++pos;
		}

		return digit;
	}

	return num;
}

int max_num(int num1, int num2)
{
	int n1digits = no_of_digits(num1);
	int n2digits = no_of_digits(num2);

	if (n1digits == n2digits)
	{
		return (num1 > num2 ? num1 : num2);
	}
	else
	{
		int min_digits = (n1digits < n2digits ? n1digits : n2digits);

		for(int i = 0; i < min_digits; ++i)
		{
			int n1digit = get_digit(num1, i, n1digits);
			int n2digit = get_digit(num2, i, n2digits);

			if (n1digit > n2digit)
			{
				return num1;
			}
			else if (n1digit < n2digit)
			{
				return num2;
			}
		}

		return num1; // Return any value
	}
}

void insert_node(Node** root, int num)
{
	Node *t = *root;
	Node *prev = t;

	Node *new_node = new Node(num);

	while (t)
	{
		if (max_num(t->data, num) == num)
		{
			new_node->next = t;

			if (t == *root)
			{
				*root = new_node;
			}

			break;
		}
		
		prev = t;
		t = t->next;
	}

	prev->next = new_node;
}

int find_max_num(int *a, int size)
{
	int max_num = 0;

	Node *root = NULL;

	for(int i = 0; i < size; ++i)
	{
		int num = a[i];

		if (root == NULL)
		{
			root = new Node(num);
		}
		else
		{
			insert_node(&root, num);
		}
	}

	Node *temp = root;
	while (temp)
	{
		int multiplier = 10;

		if (temp->data > 9)
		{
			int ndigits = no_of_digits(temp->data);
			multiplier = (int) pow(10.0, ndigits);
		}

		max_num *= multiplier;
		max_num += temp->data;

		temp = temp->next;
	}

	delete root;

	return max_num;
}

int main()
{
	// int a[] = { 1, 4, 2, 5, 9, 3};
	int a[] = { 6, 55, 3, 65, 43};

	int max_num = find_max_num (a, sizeof(a) / sizeof(int));

	cout << "Max Num => " << max_num;

	getch();
	return 0;
}

sites.google.com/site/spaceofjameschen/home/number-and-string/ind-the-max-no-that-can-be-formed-by-any-permutation-of-the-arrangement
vector<string> vec;
char buffer[256];
for(int i = 0; i < len; ++i){
itoa(arr[i], buffer, 10);
vec.push_back(buffer);
}

sort(vec.begin(), vec.end(), [](string str1, string str2)->bool
{
int len = str1.size() > str2.size() ? str2.size() : str1.size();

int i = 0;
while(i < len - 1 && str1[i] == str2[i]) i++;

if(i < len) return (str1[i] > str2[i]);

return (i == str1.size());

});
string ret;
for(auto it = vec.begin(); it != vec.end(); ++it) ret += *it;

return ret;

We can use max heap sort , and here max will be decided on the comparison of leftmost digit.
In java , a comparator can be provided and then it can be sorted using max heap.

> Visit each array element
> For each element extract digits
> Create an array,say M, of size 10 , and for each digit increment value of M[digit] by 1
> No in descending order visit M
> Print each element K, by M[K] times

Use MSD radix sort to sort the numbers in descending order. Starting from the maximum value, keep concatenating the numbers.

1)consider an array of n integers.
2) create a hash of n entries with value as number of digits for each integer element in arr.
3)iterate in N^2 fashion for all un-appended elements. (think on this why 2 loops!!)
4) in the inner loop, find the maximum leftmost digit.
5) in case of a tie, keep a utility method handy to resolve them.
6) keep on appending the integers to a string (u can always write one!!).
7) update hash for all appended entries with -1.


following code snippet gives only an idea (not tested on compiler):

//utility method to return number of digits for an element
int nDigits(int num)
{
    int n=0;
    while(num>0)
    {
    	num/=10;
    	n++;
    }
    return n;
}

//utilty method to return indexed digit of an element
int iDigit(int num,int index)
{
	int n,rem;
	for(int i=1;i<=index;i++)
	{
		rem=num%10;
		num/=10;
    }
}
//utility method to break a tie
int compare(int *arr,int fIndex,int sIndex,int f, int s)
{
	if(f==0)
	return fIndex;
	if(s==0)
	return sIndex;
	x=iDigit(arr[fIndex],f);
	y=iDigit(arr[sIndex],s);
	if(x==y)
		return compare(arr,fIndex,sIndex,f-1,s-1);
	else
		return fIndex?x>y:sIndex;
}

1st step:
==========
create hash of number of digits:
=================================
arr[n];//lets assume
for(i=0;i<n;i++)
	hash[i]=nDigits(arr[i]);

2nd step:
==========
iterations:
=============
for(i=0;i<n;i++)
{
	max=-1;index=-1;
	for(j=0;j<n;j++)//in each iteration will find one entry
	{
		if(hash[j]!=-1)
		{
			x=iDigit(arr[j],hash[j]);
			if(x>max)
			{
				max=x;
				index=i;
			}
			if(x==max)
			{
				y=compare(arr,index,j,hash[index],hash[j]);
				index=y;//we already have max
			}
	    }
		hash[index]=-1;
		append(str,arr[index])
    }
}

Instead of a Radix sort, I opted for a quicksort with a custom comparison method for less space complexity. Here is some working java code.

public class LargestPerm {
	
	static int[] arr = {21, 9, 23};
	
	public static void main(String[] args) {
		qsort(arr, 0, arr.length-1);
		StringBuffer sb = new StringBuffer();
		
		for (int a : arr) 
			sb.append(Integer.toString(a));
		
		System.out.println(sb.toString());
	}
	
	public static void qsort(int[] arr, int a, int b) {
		if (arr.length <= 1) 
			return;
		if (a > b) return;
		int piv = arr[(a + b)/2];
		int start = a; 
		int end = b;
		while (start <= end) {
			while (compare(arr[start], piv)) // start > piv
				start++;
			while (compare(piv, arr[end])) // end < piv
				end--;
			if (start <= end) {
				int tmp = arr[start];
				arr[start] = arr[end];
				arr[end] = tmp;
				start++;
				end--;
			}
		}
		qsort(arr, a, end);
		qsort(arr, start, b);
	}
	
	public static boolean compare(int a, int b) {
		if (a == b) 
			return false;
		char[] aa = Integer.toString(a).toCharArray();
		char[] bb = Integer.toString(b).toCharArray();
		int i = 0;
		while (i < aa.length && i < bb.length) {
			if (aa[i] > bb[i]) return true;
			else if (bb[i] > aa[i]) return false;
			else i++;
		}
		return true;
	}
}

Instead of a Radix sort, I opted for a quicksort with a custom comparison method for less space complexity. Here is some working java code.

public class LargestPerm {
	
	static int[] arr = {21, 9, 23};
	
	public static void main(String[] args) {
		qsort(arr, 0, arr.length-1);
		StringBuffer sb = new StringBuffer();
		
		for (int a : arr) 
			sb.append(Integer.toString(a));
		
		System.out.println(sb.toString());
	}
	
	public static void qsort(int[] arr, int a, int b) {
		if (arr.length <= 1) 
			return;
		if (a > b) return;
		int piv = arr[(a + b)/2];
		int start = a; 
		int end = b;
		while (start <= end) {
			while (compare(arr[start], piv)) // start > piv
				start++;
			while (compare(piv, arr[end])) // end < piv
				end--;
			if (start <= end) {
				int tmp = arr[start];
				arr[start] = arr[end];
				arr[end] = tmp;
				start++;
				end--;
			}
		}
		qsort(arr, a, end);
		qsort(arr, start, b);
	}
	
	public static boolean compare(int a, int b) {
		if (a == b) 
			return false;
		char[] aa = Integer.toString(a).toCharArray();
		char[] bb = Integer.toString(b).toCharArray();
		int i = 0;
		while (i < aa.length && i < bb.length) {
			if (aa[i] > bb[i]) return true;
			else if (bb[i] > aa[i]) return false;
			else i++;
		}
		return true;
	}
}

Use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers. Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

here's an ap[proach that works
1. sort using MSB and list them in different buckets (buckets of digits of MSB)
2. then in each bucket sort using next significant digit
if it is one digit number then insert a dummy digit which is the same digit itself
eg if 9's bucket has 9,91,93 then we sort 99,93,91 (remember 99 is actually n
3. loop step 2 till we have sorted the max width of the number with largets number of digits
4. arrange them in descending fashion while deleting the dummy diigits

void FindMaxValueFormed(int a[], int n)
{
	int i,cnt=0;
	int mult=10,indx=0,v;


	int m=maxValue(a,n); //returns the largest element of array a
	char *result=new char[m];
	memset(result,0,sizeof(char)*m);

	for(i=0;i<n;i++)
	{
		if(a[i]>=10)
			break;
		cnt++;
	}
	
	for(i=cnt-1;i>=0;i--)
	{
		v=a[i];
		result[indx++]=v+'0';
	}
	result[indx]='\0';

	for(i=n-1;i>=cnt;i--)
	{
		v=a[i];
		while(v>mult)
		{
			int tmp=v/mult;
			result[indx++]=tmp+'0';
			v=v%mult;
		}
		result[indx++]=v+'0';
	}
	result[indx]='\0';
	cout<<result;

	delete [] result;
}

sort(arr);
for(i=0;i<n;i++)
{
  if(arr[i]<10)
    b[index1++]=a[i];
  if(arr[i]>=10)
    c[index2++]=a[i];
}
i=0;j=0;
while(i<index1 && j<index2)
{
  if(b[i]>c[i]/10)
  {
     printf("%d",b[i]);
     i++;
  }
  else
  {
     printf("%d",c[j]);
     j++;
  }
}
if(i>index1)
{
   for(k=index1-1;k>=i;k--)
     printf("%d",b[k]);
}
if(j>index2)
{
    for(k=index2-1;k>=j;k--)
      printf("%d",c[k]);
}
delete [] b;
delete [] c;

sorting the original array takes O(n lg n).
arrays b and c together require at most O(n) space.

a simple java prog.not sure about the complexity:-check arrays.sort class

public static void main(String [] args){
		int [] a1 ={29,9,215,77};

		String s1 = Integer.toString(a1[0]);
		String s2 = Integer.toString(a1[1]);
		String s3 = Integer.toString(a1[2]);
		String s4 = Integer.toString(a1[3]);
		
		String va[] = {s1,s2,s3,s4};

		Arrays.sort(va);
		System.out.println(va[3]+va[2]+va[1]+va[0]);

}

I think we can use binary search tree but with slightly different strategy . while inserting a number in BST we first compare the most significant digit
- if most significant digit of no is greater than the most significant digit of root than we will move right otherwise left.
-if most significant digit of no is equal to most significant digit of root value we compare the next digit of no. with next digit of root value and repeat step1.
-after creating the tree we traverse as RIGHT,ROOT and LEFT manner recursively.
eg: 21,9,23
21 --------------- root node
\
9 ---------------9 > 2(most significant digit of 9 and 21) so move rt
/
23------------------2=2(most significant digit 21 and 23) so compare (second most significant digit) of 21 and 23 (i.e. 1 and 3, 1< 3) so move right but 2<9 (most significant digit of 21 and 9) so move left.

now traverse in RIGHT ROOT LEFT manner
will result 9 23 21.

If there is a single digit in the list, repeat the number to make a two digit and then sort the list. That should do the trick i think.

For example
{82, 85, 83, 8, 89, 78, 79, 76, 7}

make the same digit to the single digit number
{82, 85, 83, 88, 89, 78, 79, 76, 77}

Now sort and remove the extra appended digit.
That is your answer once you concatenate all numbers.

O(N log N) - assumption string comparison is O(1)

import java.util.Arrays;
public class TestMe {
    private static class ShadyInt implements Comparable<ShadyInt> {
        String i;
        ShadyInt(String i) {
            this.i = i;
        }
        @Override
        public int compareTo(ShadyInt that) {
            if (this.i.equals(that.i)) {
                return 0;
            }
            String thisthat = this.i + that.i;
            String thatthis = that.i + this.i;
            if (thisthat.compareTo(thatthis) > 0) {
                return 1;
            } else {
                return -1;
            }
        }
        @Override
        public String toString() {
            return i;
        }
    }
    public static void printMaxInt(String nos[]) {
        ShadyInt noss[] = new ShadyInt[nos.length];
        for (int i = 0; i < nos.length; ++i) {
            noss[i] = new ShadyInt(nos[i]);
        }
        Arrays.sort(noss);
        for (int i = noss.length - 1; i >= 0; --i) {
            System.out.print(noss[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        printMaxInt(new String[] { "6", "63", "637", "6378" });
        printMaxInt(new String[] { "6", "67", "673", "6738" });
        printMaxInt(new String[] { "1", "12", "121", "1234" });
        printMaxInt(new String[] { "99", "98", "91", "9" });
    }
}