Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
you can even use simple bubble sorting and swap two elements if by their exchange can produce a bugger number.
simple code follows:
String[]s = new String[n]; // take input
for (int i = 0 ; i < n;i++)
s[i]= in.next();
/** simple bubble sort **/
for (int i = 0 ;i < n ; i++)
for (int j = i+1;j<n;j++) {
String p=s[j]+s[i];
if ( p.compareTo(s[i]+s[j])>0)
{
String t = s[i];
s[i]=s[j];
s[j]=t;
}
}
/** print largest number *******/
for (int i = 0;i<n;i++)
System.out.print(s[i]);
System.out.println("");
Here is the logic:
Basically, sorting means arrangement of number. To do so we need to swap numbers based on some condition...
|Below is the logic of that condition...
we have 2 numbers lets say
94 and 9
calculate number of digits. which are 2 and 1 respectively.
then
inumber = 9*(10^2)+94;
jnumber = 94*(10^1)+9;
compare above numbers and then make decision of swapping....
I hope it helps....
I dont think approach suggested by ANONYMOUS would work as here we cant break integers as in 19 as 1 and 9, make 91 out of it. 19 would appear in final output as 19 only.
It is just an simple sorting question with a little twist by changing the elementary compare operator so I don't think there is one answer to this problem. Any algorithm would work but O(n log n) type algorithms like mergesort and quicksort should be a good answer. Any comparison based sorting algorithms would do. Here I have implemented both in java for random arrays. Have a look those interested but there is absolutely no change in these basic algorithms except for the change in compare operator:
import java.util.Arrays;
import java.util.Random;
public class AnyClass
{
private final static int MAX_SIZE = 10 ;
private final static int MAX = 20;
public static void mergeSort(int a[])
{
if(a.length <= 1)
return;
int first[] = new int[a.length / 2];
int second[] = new int[a.length - first.length];
for(int x = 0; x < first.length; x++)
first[x] = a[x];
for(int x = first.length, y = 0; x < a.length; x++, y++)
second[y] = a[x];
//Split the array again
mergeSort(first);
mergeSort(second);
merge(first, second, a);
}
private static int[] merge(int first[], int second[], int[] a)
{
int x = 0;
int y = 0;
int z = 0;
while(x < first.length && y < second.length){
if(compareInt(first[x],second[y])){
a[z] = first[x];
x++;
}
else{
a[z] = second[y];
y++;
}
z++;
}
//copy remaining elements to the tail of a[];
for(int i = x; i < first.length; i++){
a[z] = first[i];
z++;
}
for(int i = y; i < second.length; i++){
a[z] = second[i];
z++;
}
return a;
}
public static boolean compareInt(int x, int y){
return (Integer.parseInt(Integer.toString(x)+Integer.toString(y))>
Integer.parseInt(Integer.toString(y)+Integer.toString(x)));
}
public static void quickSort(int[] a, int p, int r)
{
if(p<r)
{
int q=partition(a,p,r);
quickSort(a,p,q);
quickSort(a,q+1,r);
}
}
private static int partition(int[] a, int p, int r) {
int x = a[p];
int i = p-1 ;
int j = r+1 ;
while (true) {
i++;
while ( i< r && compareInt(x,a[i]))
i++;
j--;
while (j>p && compareInt(x,a[j]))
j--;
if (i < j)
swap(a, 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;
}
public static void main(String args[]){
Random generator = new Random();
int[] numbers = new int[generator.nextInt(MAX_SIZE)];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
//int[] numbers = {4, 94, 9, 14, 1};
System.out.println("Unsorted Array:"+Arrays.toString(numbers));
mergeSort(numbers);
System.out.println("Sorted Array via Mergesort:"+Arrays.toString(numbers));
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
System.out.println("Unsorted Array:"+Arrays.toString(numbers));
quickSort(numbers, 0, numbers.length - 1);
System.out.println("Sorted Array via QuickSort:"+Arrays.toString(numbers));
}
}
#include<stdio.h>
#include<stdlib.h>
int greater(int k,int l)
{
int temp=0;
int templ;
int tempk;
int kl;
int lk;
if(k==-100000)
return(0);
if(l==-100000)
return(1);
temp=10;
templ=l;
tempk=k;
while(templ/10!=0)
{
templ=templ%10;
temp=temp*10;
}
kl=k*temp+l;
temp=10;
while(tempk/10!=0)
{
tempk=tempk%10;
temp=temp*10;
}
lk=l*temp+k;
if(kl>lk)
return(1);
else
return(0);
}
Modified_Merge(int A[],int p,int r,int q)
{
int *l1;
int *l2;
int n1;
int n2;
int i;
int j;
int k;
n1=r-p+1;
n2=q-r;
l1=(int *)malloc((n1+1)*sizeof(int));
l2=(int *)malloc((n2+1)*sizeof(int));
for(i=0;i<n1;i++)
l1[i]=A[p+i];
for(j=0;j<n2;j++)
l2[j]=A[r+1+j];
l1[n1]=-100000;
l2[n2]=-100000;
i=0;
j=0;
k=p;
while(i!=n1||j!=n2)
{
if(greater(l1[i],l2[j]))
{
A[k]=l1[i];
i++;
k++;
}
else
{
A[k]=l2[j];
j++;
k++;
}
}
}
Modified_Merge_Sort(int A[],int p,int q)
{
int r;
if(p<q)
{
// printf("yessss%d,%d\n",p,q);
r=(p+q)/2;
Modified_Merge_Sort(A,p,r);
Modified_Merge_Sort(A,r+1,q);
Modified_Merge(A,p,r,q);
}
else
return;
}
int main()
{
int n;
int *A;
int i=0;
printf("Inter the number of Integer:\n");
scanf("%d",&n);
A=(int *)malloc(n*sizeof(int));
while(i<n)
{
scanf("%d",A+i);
i++;
}
Modified_Merge_Sort(A,0,n-1);
for(i=0;i<n;i++)
printf("%d,",A[i]);
}
Most of the codes given here are joining the two nos. and comparing them and then taking decisions which no wud come first. The logic is fine but we'll have problems in handling big nos. if its a 5-6 digit no. how wud u keep a 12 digit no in int variable ( it cud b bigger than 12 digits also)
one approach i think is to reverse the nos. nd then sort them acc to the remainder they give wen divided by 10 ( we hav to do it recursively if last digit is same )
after sorting with this rule ... reverse the nos again back.
Yes, you may have a valid point but it won't happen if you override the compare operator for comparing two integers by joining them as string and reconverting to long number. You can check Long.MAX_VALUE is bigger two Intger.MAX_VALUE joined side by side. After all you just need a boolean value in the end.
However, if you are still not satisfied, there is a very simple technique to override compare operator without getting into problems like you mentioned. Just compare the integers as strings, character by character. With this logic any string that begins with a higher order number gets preference. For. eg.
'9'> '81' (because second string begins with 8)or '76'>'597' (because second string begins with 5). I don't think this is something very difficult to implement.
you can even use simple bubble sort and swap two elements if their exchange can produce a bigger number.
simple code follows:
String[]s = new String[n]; // take input
for (int i = 0 ; i < n;i++)
s[i]= in.next();
/** simple bubble sort **/
for (int i = 0 ;i < n ; i++)
for (int j = i+1;j<n;j++) {
String p=s[j]+s[i];
if ( p.compareTo(s[i]+s[j])>0)
{
String t = s[i];
s[i]=s[j];
s[j]=t;
}
}
/** print largest number *******/
for (int i = 0;i<n;i++)
System.out.print(s[i]);
System.out.println("");
import java.util.*;
public class IntegerSort {
public static void main(String args[]) {
IntegerSort is = new IntegerSort();
is.printSort();
}
public void printSort(){
Integer[] input = new Integer[]{4,94,9,14};
Arrays.sort(input, new MyIntegerComparator());
System.out.println(Arrays.toString(input));
}
public class MyIntegerComparator implements Comparator {
public int compare(Object io1, Object io2){
Integer i1 = (Integer)io1;
Integer i2 = (Integer)io2;
if(i1*Math.pow(10,intLength(i2))+i2 > i2*Math.pow(10,intLength(i1)) + i1){
return -1;
}else if(i1*Math.pow(10,intLength(i2))+i2 == i2*Math.pow(10,intLength(i1)) + i1) {
return 0;
}else{
return 1;
}
}
}
public int intLength(int i){
return 1 + (int)Math.floor(Math.log10(i));
}
}
How about using permutation?
package algos.pq;
public class Permutation {
private static int greatestNumber;
public static void main(String[] args) {
int a[] = { 4, 94, 1, 14, 9 };
int[] expectedResult = { 9, 94, 4, 14, 1 };
permutation(a, a.length);
if (greatestNumber == getAsNumber(expectedResult)) {
System.out.println("Goal");
System.out.println(greatestNumber);
} else {
System.out.println("fail");
System.out.println(greatestNumber);
}
}
private static void permutation(int[] a, int n) {
if (n == 1) {
int maybeTheNumber = getAsNumber(a);
if (greatestNumber < maybeTheNumber)
greatestNumber = maybeTheNumber;
return;
}
for (int i = 0; i < n; i++) {
swap(a, i, n - 1);
permutation(a, n - 1);
swap(a, i, n - 1);
}
}
private static void swap(int[] a, int i, int j) {
int c;
c = a[i];
a[i] = a[j];
a[j] = c;
}
//quick and dirty
private static int getAsNumber(int[] expectedResult) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < expectedResult.length; i++) {
builder.append(expectedResult[i]);
}
return Integer.parseInt(builder.toString());
}
}
import java.util.Arrays;
import java.util.Comparator;
public class TestMe {
static class LexComparator implements Comparator<Integer> {
public static final LexComparator INSTANCE = new LexComparator();
private LexComparator() {
};
@Override
public int compare(Integer o1, Integer o2) {
return String.valueOf(o1).compareTo(String.valueOf(o2));
}
}
// Is a prefix of b?
static boolean isPrefix(int a, int b) {
if (a == b) {
return true;
}
while (b != 0 && a != b) {
b /= 10;
}
return (a == b);
}
static boolean higherLexPart(int b, int a) {
if (a == b) {
return true;
}
int b_ = b;
int c = 1;
while (a != b_) {
b_ /= 10;
c *= 10;
}
c = b % c;
return LexComparator.INSTANCE.compare(a, c) < 0;
}
static String maxCombo(Integer nos[]) {
StringBuilder sb = new StringBuilder();
Arrays.sort(nos, LexComparator.INSTANCE);
int start, end;
for (int i = nos.length - 1; i >= 0; --i) {
start = end = i;
while (start > 0 && isPrefix(nos[start - 1], nos[start])) {
--start;
}
i = start;
StringBuilder sb1 = new StringBuilder();
sb1.append(nos[start++]);
while (start <= end) {
if (higherLexPart(nos[start], nos[start - 1])) {
sb1.insert(0, nos[start]);
} else {
sb1.append(nos[start]);
}
++start;
}
sb.append(sb1);
}
return sb.toString();
}
public static void main(String[] args) {
Integer nos[] = new Integer[] { 7, 78, 788, 7886 };
System.out.println(maxCombo(nos));
nos = new Integer[] { 7, 8, 89, 899, 8999, 8999 };
System.out.println(maxCombo(nos));
nos = new Integer[] { 123, 123, 123, 5456, 45236, 634534, 34345 };
System.out.println(maxCombo(nos));
}
}
I think a custom comparator is enough:
def wsort(ls):
def _wcompare(x, y):
sx = list(str(x))
sy = list(str(y))
while True:
hx = sx.pop(0)
hy = sy.pop(0)
if hx != hy:
return int(hx) - int(hy)
else:
if not sx:
return 1
elif not sy:
return -1
print _wcompare(95, 9)
return sorted(ls, cmp=_wcompare, reverse=True)
import java.util.Arrays;
import java.util.Comparator;
class LengthCom implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
String s1 = o1.toString();
String s2 = o2.toString();
int len = s1.length() - s2.length();
if(len>0){
s1 = s1.substring( s2.length());
}
if(len <0 ){
s2 = s2.substring( s1.length());
}
int f1 = Integer.parseInt(s1);
int f2 = Integer.parseInt(s2);
if(f1>f2)
return -1;
if(f1<f2)
return 1;
return 0;
}
}
public class NumberSorting {
public static void main(String st[]){
int a[] ={9,94,4,14,1};
Integer []aInt = new Integer[a.length];
int i = 0;
while (a.length >i){
aInt[i] = a[i];
i++;
}
LengthCom com = new LengthCom();
Arrays.sort(aInt,com);
for(Integer ad : aInt)
System.out.print(ad+", ");
}
}
public class IntComparator implements Comparator<Integer>{
@Override
public int compare(Integer arg0, Integer arg1) {
if(Integer.parseInt(arg0+""+arg1)>Integer.parseInt(arg1+""+arg0))
return 1;
else if(Integer.parseInt(arg0+""+arg1)<Integer.parseInt(arg1+""+arg0))
return -1;
return 0;
}
}
Here What I am thinking,
compare digit from left to right
it may not be the best approach but I would love to hear whats wrong in this algo.
I have implement my logic using bubble sort but bubble sort can be replaced with another efficient algos.
int a[8]={19,23,45,939,2,34,512,213};
int len = sizeof(a)/sizeof(a[0]);
jugardSort(a,len);
Code:
int numofdigits(int n){
if (n == 0) return 1;
int l;
for (l = 0 ; n > 0 ;++l)
n /= 10;
return l;
}
int getDigit(int from, int index){
return (int(from / pow(10.0, index))) % 10;
}
int isNeedSwap(int a,int b){
int an = numofdigits(a);
int bn = numofdigits(b);
int max = an < bn ? an: bn;
int digitIndex = 1;
do{
int ad = getDigit(a,an-digitIndex);
int bd = getDigit(b,bn-digitIndex);
if(ad < bd){
return 1;
}
else if(ad > bd){
return 0;
}
digitIndex++;
}while(digitIndex <= max);
return 0;
}
void jugardSort(int array[],int n){
//Bubble Sort, You can use any sorting algo here
for(int x=0; x<n; x++){
for(int y=0; y<n-1; y++){
int needSwap = isNeedSwap(array[y],array[y+1]);
if(needSwap){
int temp = array[y+1];
array[y+1] = array[y];
array[y] = temp;
}
}
}
for(int i=0;i<n;i++){
printf(" %d ",array[i]);
}
}
class MyComparater {
public int compareTo(int i, int j) {
String a = i.toString();
String b = j.toString();
if (a.length() > b.length()) {
String c = a;
a = b;
b = c;
}
for (int i=0; i<b.length(); i++) {
int mod_i = i % a.length();
if (a.charAt(mod_i) > b.charAt(i)) {
return 1;
}
if (a.charAt(mod_i) < b.charAt(i)) {
return -1;
}
}
return 0;
}
}
Arrays.sort(data_array, new MyComparator());
public static void main(String[] args) {
// TODO code application logic here
Integer a[] = { 4, 94, 9, 14, 1};
Comparator<Integer> NewComparator = new MaxNumberOfTwoStringsComparator();
Arrays.sort(a, NewComparator);
for(int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public class MaxNumberOfTwoStringsComparator implements Comparator{
@Override
public int compare(Object o1, Object o2) {
String s1 = o1.toString();
String s2 = o2.toString();
int a = Integer.parseInt(s1);
int b = Integer.parseInt(s2);
int vala = a * (int)Math.pow(10, s2.length()) + b;
int valb = b * (int)Math.pow(10, s1.length()) + a;
return vala < valb ? 1 : vala == valb? 0 : -1;
}
}
compare 1st digits in numbers and sort them,
if two numbers have same first digit,check the 2nd digit.
here for ab..a is first digit.
for two numbers ab,c compare a and c if c is bigger swap numbers
else for ab and ad compare b and d swap if b<d an so on.
This is exactly the kind of stupid question I hate to give candidates because there's a non-obvious "trick". The trick is, as previously demonstrated, to simply replace the "less" predicate of a std sort algorithm and sort concatenated strings instead of integers. The quoted time complexity is technically incorrect, however, since most library quick-sorts degenerate to selection sort for small n (usually <32) giving the average time complexity for the sort as O(n) swaps (look it up if you don't believe me!)
We can further optimize by noting that the the int<==>string conversions of the earlier algorithms are cheaper than the log/pow versions and we can sacrifice a little memory to avoid converting to/from strings more than once. Here is the algorithm in D, and note also that I used the chain operation which avoids actually concatenating the strings in the inline closure-predicate.
void joinedSort(int[] values)
{
write(values);
auto svalues = to!(string[])(values);
bool predicate(string a, string b) { return cmp( chain(a, b), chain(b, a) ) > 0; }
sort!(predicate)(svalues);
copy(to!(int[])(svalues), values);
writeln(" => ", values);
}
int main(string[] argv)
{
joinedSort([ 4, 94, 9, 14, 1 ]);
return 0;
}
radix sort won't work...
here we need to decide if we want to swap numbers or not
- mahadev October 11, 2012