CareerCup

Just use counting sort ( O(n) ). Then rearrange the number starting with the biggest one.
Note that the nested for loop below make a total of n iterations only. So the resulting code is O(n).

public int getLargestRearranged( int number ){
   int[] digitCounts = new int[10];
      
   int remainingDigits = number;
   while( remainingDigits > 0 ){
      int currentDigit = remainingDigits % 10;
      remainingDigits /= 10;
      digitCounts[currentDigit]++;
   }
   
   int rearrangedNumber = 0;
   for( int i = 9; i >= 0; i-- ){
      
      if( digitCounts[i] == 0 ) continue;
      
      for( int j = 0; j < digitCounts[i]; j++ ){
         rearrangedNumber *= 10;
         rearrangedNumber += i;
      }
   }
   
   return rearrangedNumber;
}

public static int max(int n) {
	int[] digits = new int[10];
		
	while(n > 0) {
		digits[n%10] += 1;
		n = n/10;
	}
	int result = 0;
	int i = digits.length - 1;
	while(i > 0) {
		if(digits[i] > 0) {
			result = result * 10 + i;
			digits[i] -= 1;
			continue;
		}
		i--;
	}
	return result;
}