Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
int max_num(int num) {
bool is_neg = num < 0;
if(is_neg) {
num = num * -1;
}
int count[10];
for(int i = 0; i < 10; ++i) {
count[i] = 0;
}
while(num != 0) {
++count[num % 10];
num /= 10;
}
if(!is_neg) {
for(int i = 9; i >= 0; --i) {
while(count[i] != 0) {
num = num * 10 + i;
count[i]--;
}
}
} else {
for(int i = 0; i < 10; ++i) {
while(count[i] != 0) {
num = num * 10 + i;
count[i]--;
}
}
num = num * -1;
}
return num;
}
What are these lines of code doing??
for(i=9;i>=0;i--)
{
while(arr[i])
{
new_number=new_number*10+i;
arr[i]--;
}
}
Smart solution and well done ! This is what interviewers most probably are looking for during technical interviews. As for accounting for the negative numbers, I think it's just a matter of checking the sign before starting extracting the individual digits and keeping a flag for that.
To answer Anonymous:
for(i=9;i>=0;i--)
{
while(arr[i])
{
new_number=new_number*10+i;
arr[i]--;
}
}
The former lines of code created a histogram representation of the number. The while loop uses the elements of the histogram, one at a time from 9->0. The arr[i]-- indicates that one element of the histogram has been used up.
one solution could be:
1. Make an array of size 10 countDigitMap[10] = {0};
2. Start taking out least significant digit of number.
3. and keep wcountDigitMap[digit]++;
4. loop from end form ( 9, 8 ... 0 ) and print digits in map with count > 0.
guys if u have any better than this one please comment below.
one big mistake that i saw in arun and pankaj.
u have taken the number in int.. int has limitation..
below code takes jst the input char by char and put outs in the order.
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
char c;
int a[10]={0};
while((c=getchar())!='\n')
{
a[c-'0']++;
}
for (int i=9;i>=0; i--)
{
while(a[i])
{cout<<i;
a[i]--;
}
}
return 0;
}
int digit(int n , int l)
{
for(int i = 0; i<l i++)
{
n = n/10;
}
return n%10;
}
int biggestNumber(int number)
{
n1=number;
int n1, n2, l=1,
while(n1>9)
{
n1=n1/10;
l++;
}
n2=number;
for(i=0; i<l; i++)
{
d1= digit(n2 , i);
for(j=0; j<l; j++)
{
d2= digit(n2, j);
if(d1>d2)
{
n2= n2 - (d1-d2)*pow(10 , i) + (d1-d2)*pow(10 , j);
}}
}
return n2;
}
int digit(int n , int l)
{
for(int i = 0; i<l i++)
{
n = n/10;
}
return n%10;
}
int biggestNumber(int number)
{
n1=number;
int n1, n2, l=1,
while(n1>9)
{
n1=n1/10;
l++;
}
n2=number;
for(i=0; i<l; i++)
{
d1= digit(n2 , i);
for(j=0; j<l; j++)
{
d2= digit(n2, j);
if(d1>d2)
{
n2= n2 - (d1-d2)*pow(10 , i) + (d1-d2)*pow(10 , j);
}}
}
return n2;
}
int digit(int n , int l)
{
for(int i = 0; i<l i++)
{
n = n/10;
}
return n%10;
}
int biggestNumber(int number)
{
n1=number;
int n1, n2, l=1,
while(n1>9)
{
n1=n1/10;
l++;
}
n2=number;
for(i=0; i<l; i++)
{
d1= digit(n2 , i);
for(j=0; j<l; j++)
{
d2= digit(n2, j);
if(d1>d2)
{
n2= n2 - (d1-d2)*pow(10 , i) + (d1-d2)*pow(10 , j);
}}
}
return n2;
}
do not need count array.
int digit(int num, int bit) //bit numbered from 0
{
return num/(pow(10.0,bit))-(int)(num/(pow(10.0,(bit+1))))*10;
}
int biggestnum(int num)
{
int result=digit(num,0);
int countend=num;
int i=0;
while((int)(countend/10)!=0)
{
i++;
int j=0;
int d=digit(num,i);
while(j<i&&d>digit(result,j))
{
j++;
}
result=result%(int)(pow(10.0,j))+(int)(result/(int)pow(10.0,j))*pow(10.0,j+1)+d*(int)pow(10.0,j);
countend/=10;
}
return result;
}
Use bubble sort because it is simple and it use a constant space + 1 cell for the swap.
Order from high to low.
#define SIZE 3
int tab[SIZE];
int swapped=1;
while(swapped)
{
swapped=0;
for(i=0; i<SIZE-1 ; i++)
{
if(tab[i]<tab[i+1])
{
temp = tab[i];
tab[i] = tab[i+1];
tab[i+1] = temp;
swapped=1;
}
}
}
for(i=0; i<SIZE ; i++)
{
printf("%d", tab[i]);
}
Interesting but I cant figure out how to implement in this case. Could you provide some code?
I was thinking about inserting digit at the proper bit index, then iterate through each bit to generate the number. But it won't work when the number has duplicate digits.
main()
- Pankaj February 28, 2012{
int a=2347869;
int x=a,new_number=0;
int arr[10]={0};
int i,temp;
while(x)
{
temp=x%10;
arr[temp]=arr[temp]+1;
x=x/10;
}
for(i=9;i>=0;i--)
{
while(arr[i])
{
new_number=new_number*10+i;
arr[i]--;
}
}
printf("%d ",new_number);
}
this algo takes constant space.....using array of size 10