Microsoft Interview Question Software Engineer / Developers
Team: WF
Country: United States
Interview Type: Phone Interview
public void sort(Integer[] a)
{
Arrays.sort(a, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b)
{
if(a == 0) return b;
else if(b == 0) return a;
else return concat(b, a) - concat(a, b);
}
private int concat(Integer a, Integer b)
{
return (int)(a * Math.pow(10, ((int)Math.floor(Math.log10(b)) + 1)) + b);
}
});
}
I did the following. Assuming the time complexity of sorting is O(n log n), the algorithm runs in O(n log n). However, it requires additional space for the string array.
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
void SortMax(int* arr, int len);
bool StringCompare(string s1, string s2);
string toString(int val);
int main()
{
int arr[5] = {4, 94, 9, 14, 91};
int len = 5; //sizeof(arr)/sizeof(int);
cout<<"Original array"<<endl;
for(int i = 0; i < len; i++)
cout<<arr[i]<<" ";
cout<<endl;
SortMax(arr, len);
cout<<"Sorted array"<<endl;
for(int i = 0; i < len; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
void SortMax(int* arr, int len)
{
string strarr[len];
for(int i = 0; i < len; i++)
strarr[i] = toString(arr[i]);
std::sort(strarr, strarr+len, StringCompare);
for(int i = 0; i < len; i++){
arr[i] = atoi(strarr[i].c_str());
}
}
bool StringCompare(string s1, string s2)
{
if(atoi((s1 + s2).c_str()) > atoi((s2 + s1).c_str()))
return true;
else
return false;
}
string toString(int val)
{
stringstream ss;
ss<<val;
return ss.str();
}
Here is the algorithm in which the numbers will be modified and then bring back to original.
Consider an example. { 69, 8, 841, 89, 9, 941, 998, 854 }
Find the maximum - its 998.
Modify the numbers by making each number having same number of digits as the maximum is having. Repeat the last digit as many times required to convert it in a digit having same number of digits as the maximum. Here the array will become
{ 699, 888, 841, 899, 999, 941, 998, 854 }
Sort the modified array.
{ 999, 998, 941, 899, 888, 854, 841, 699 }
Change the modified numbers back.
{ 9, 998, 941, 89, 8, 854, 841, 69 }
Concat from beginning to end. And you have the solution.
This soultion doesn't work properly, for example NumberOfDigits function will return 0 for the number 0 but we all know that every number contains at least one digit.
I think you can use any comparison based sorting algorithm. The only thing needs to be changed is the comparison rule: for two integers a and b, a > b if ab > ba (here ab means concatenating a and b, eg. a = 9, b = 94, ab = 994).
Then we can use merge sort which achieves O(nlgn) time complexity.
Lets assume we have 'N' numbers and the largest one is some 'M' digits long. The following algorithm is inefficient but has a smaller time complexity in 'N'.
1- Go through the list once and separate the numbers based on first digit, which is 10 categories. C9 > C8 > ... > C1 > C0
2- For category Ci, the first digit is 'i'. Drop it and categorize again based on second digit. You get the categories Ci9 > Ci8 > ... > Ci0.
3- If the largest number is M digits, then you will at most have 10^M different categories. How ever, each time you do a sorting of at most "N" numbers, i.e., time complexity < O(N10^M ).
My point is you can do better than O(N log N) because this is not a generic sorting problem. For instance, lets assume all the numbers are single digit. Then the time complexity is obviously O(N). Just put all the 9's first, then 8's, ..., then 0's.
Use Quick Sort instead of bubble sort.
Also, Instead of concat and check , just check the significant digits and get the order !
public class SortMaxValue {
public static void main(String []args)
{
int []input = {13,54,56,745,45,76,879,12,91,8,9,99,989,543,887};
new SortMaxValue().sortMaxValue(input);
new SortMaxValue().displayArray(input);
}
public void displayArray(int [] input)
{
for(int i = 0;i < input.length;i++)
System.out.print(input[i] + " ");
}
public void sortMaxValue(int []input)
{
for(int i = 0;i < input.length;i++)
{
for(int j = 0;j < input.length - i - 1;j++)
{
if(!compareElements(input[j],input[j+1]))
swap(input,j,j+1);
}
}
}
public boolean compareElements(int input1,int input2) // returns true if input1 has higher precedence over input2(eg . 9 over 83)
{
if(input1 == input2)
return false;
int l1 = noOfDigits(input1);
int l2 = noOfDigits(input2);
int l1copy = l1;
int l2copy = l2;
int i1copy = input1;
int i2copy = input2;
boolean flag;
int n;
if(l1 < l2)
{
n = l1;
flag = true;
}
else
{
n = l2;
flag = false;
}
while(input1 / (int)Math.pow(10,l1-1) == input2 / (int)Math.pow(10,l2-1) && n > 1)
{
input1 %= Math.pow(10,l1-1);
input2 %= Math.pow(10,l2-1);
l1--;
l2--;
n--;
}
if(input1 / (int) Math.pow(10,l1-1) > input2 / (int)Math.pow(10,l2-1))
return true;
else if(input1 / (int) Math.pow(10,l1-1) < input2 / (int)Math.pow(10,l2-1))
return false;
else
{
if(flag)
{
input2 %= Math.pow(10,l2-1);
if(input2 / (int) Math.pow(10,l2-2) >= i2copy / (int) Math.pow(10,l2copy-1))
return false;
else
return true;
}
else
{
input1 %= Math.pow(10,l1-1);
if(input1 / (int) Math.pow(10,l1-2) >= i1copy / (int) Math.pow(10,l1copy-1))
return true;
else
return false;
}
}
}
public int noOfDigits(int n)
{
int digits;
for(digits = 0;n > 0;digits++)
{
n /= 10;
}
return digits;
}
public void swap(int []a,int x,int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
void reverseastring(char *s,int n)
{
int l=0,r=n-1;
while(l<r)
{
s[l]=s[l]+s[r]-(s[r]=s[l]);
l++;
r--;
}
}
void int2char(int a,char *s,int base)
{
int i=0;
while(a)
{
s[i]='0'+a%base;
a/=base;
i++;
}
s[i]='\0';
reverseastring(s,i);
return;
}
bool compar(const int a,const int b)
{
char s[2010],s1[2010];
int2char(a,s,10);
int2char(b,s1,10);
char te[2010];
strcpy(te,s);
return (atoi(strcat(s,s1))>atoi(strcat(s1,te)));
}
main()
{
int n;
cin >> n;
int a[2010];
char s[2010];
int i;
for(i=0;i<n;i++)
{
cin >> a[i];
}
char s1[2010];
sort(a,a+n,compar);
for(i=0;i<n;i++)
cout <<a[i] <<" ";
cout<<endl;
}
How about just sorting the array , keep index where number of digits increase :
so : 4,94,9,14,1 -> 1,4,9,14,94 using quick\merge sort ( nlogn )
set index "2-digit" to 3 , meaning in position 3 in the array , we start 2 digit's number and so on.
now - start concatenating number :biggest 1 digit with biggest 2 digit and so on.
continue with how many numbers you have.
1. convert it into string. since a integer type has limited range. we can regard it to be O(n).
2. construct a trie tree. the internal order should be from 9 to 0. it takes n * avg-length, as stated above, we roughly consider it to be n
3. dfs trie tree. on a single path we print the node that terminated earlier first.
the total number of nodes is no more than n * avg-length.
So we have O(3 * max-length * n) = O(n) where max-length is 10 if int32
Still Use QuickSort. The only difference is comparison condition.
public class ConcatSort {
public static void quickSort(int[] array) {
quickSortT(array, 0, array.length - 1);
}
public static void quickSortT(int[] array, int left, int right) {
if (left < right) {
int pivotIdx = (int) (Math.random() * (right - left)) + left;
int newPivotIdx = partition(array, left, right, pivotIdx);
quickSortT(array, left, newPivotIdx - 1);
quickSortT(array, newPivotIdx + 1, right);
}
}
private static int partition(int[] array, int left, int right, int pivotIdx) {
int pivotValue = array[pivotIdx];
swap(array, right, pivotIdx);
int storedIdx = left;
for (int i = left; i < right; i++) {
// only different part with normal quick sort partition
int result = compAfterExpand(array[i], pivotValue);
if (result == -1) {
// array[i] < pivotValue
swap(array, i, storedIdx);
storedIdx++;
}
}
swap(array, storedIdx, right);
return storedIdx;
}
private static int compAfterExpand(int num, int pivotValue) {
String numStr = String.valueOf(num);
String pivotStr = String.valueOf(pivotValue);
int diff = pivotStr.length() - numStr.length();
if (diff < 0) {
// expand pivotStr
int n = -diff;
while (n > 0) {
pivotStr = pivotStr.concat(""
+ pivotStr.charAt(pivotStr.length() - 1));
n--;
}
} else if (diff > 0) {
// expand numStr
int n = diff;
while (n > 0) {
numStr = numStr.concat("" + numStr.charAt(numStr.length() - 1));
n--;
}
}
if (Integer.parseInt(numStr) > Integer.parseInt(pivotStr)) {
return -1;
}
return 0;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void sortByConcat(int[] array) {
if (array == null || array.length <= 1) {
return;
}
quickSort(array);
}
public static void main(String[] args) {
int[] array = { 4, 94, 9, 14, 1 };
sortByConcat(array);
for (int i : array) {
System.out.print(i + "\t");
}
}
}
We can achieve O(n log n) time using a straight forward QuickSort or Merge Sort.
- CameronWills November 11, 2012The trick is with the comparison step of the sort. as detailed here:
stackoverflow.com/questions/5037503/how-can-i-manipulate-an-array-to-make-the-largest-number
Its not as simple as comparing the elements of the array. When you comparing two integer elements x and y during the sort, compare the concatenation xy against the concatenation yx to figure out which is larger.