Microsoft Interview Question Senior Software Development Engineers
Team: Bing
Country: United States
Interview Type: In-Person
My answer:
Observation: each three digit number is spelled the same, the only difference is the magnitude (million, thousand, hundred). Hence write a utility function which processes a number from 0-999 and call it for hundreds, thousands and millions.
Algorithm:
- create a HashMap<int, string> for the below values
0 - zero
1 - one
...
9 - nine
10 - ten
11 - eleven
12 - twelve
....
19 - nineteen
20 - twenty
30 - thirty
40 - fourty
...
90 - ninety
100 - one hundred
200 - two hundred
...
900 - nine hundred
- Now calculate ones, tens and hundreds place and form a string. Care should be taken to handle numbers from 10-19, since you need not worry about ones place for them.
/*
2 functions assumed
1) findMaxDecimalPlace e.g for 123 it will return 100 for 1202 -> 1000
2) print function which return string value on the assumption that we have mapping
something like this
1 -> "one", 2 -> "two", upto 19
and 20 -> "twenty"....90 "Ninety", 100 -> "hundred and",
1000 -> "thousand" and so on
*/
public void IntToString(int number) {
if (number <= 20) {
System.out.println(print(number));
return;
}
while (number > 0) {
int maxdecimalPlace = findMaxDecimalPlace(number);
if (number / maxdecimalPlace > 0) {
if (number / maxdecimalPlace < 20) {
System.out.println(print(number - (number % maxdecimalPlace))
+ print(number % maxdecimalPlace));
break;
}
System.out.println(print(number - (number % maxdecimalPlace)));
number = number % maxdecimalPlace;
} else {
System.out.println(print(number));
}
}
}
///------ code fix ----///
/*
2 functions assumed
1) findMaxDecimalPlace e.g for 123 it will return 100 for 1202 -> 1000
2) print function which return string value on the assumption that we have mapping
something like this
1 -> "one", 2 -> "two", upto 19
and 20 -> "twenty", 30 -> "thirty", 40 -> "forty"....90 "Ninety", 100 -> "hundred and",
1000 -> "thousand" and so on
and some logic inside for cases like 5000 => "five" + "thousand"
*/
public void IntToString(int number) {
while (number > 0) {
if (number <= 20) {
System.out.println(print(number));
break;
}
int maxdecimalPlace = findMaxDecimalPlace(number);
if (number / maxdecimalPlace > 0) {
System.out.println(print(number - (number % maxdecimalPlace)));
number = number % maxdecimalPlace;
} else {
System.out.println(print(number));
break;
}
}
}
How are you dealing with "ten thousand" as 99999 will be ninety nine thousand nine hundred ninty nine
void createhash(map<int,string> & hashmap) {
hashmap.insert(pair<int,string>(1,'one'));
.
. hashmap.insert(pair<int,string>(10,'ten'));
hashmap.insert(pair<int,string>(19,'nineteen'));
hashmap.insert(pair<int,string>(20,'twenty'));
hashmap.insert(pair<int,string>(30,'thirty'));
.
hashmap.insert(pair<int,string>(90,'ninety'));
hashmap.insert(pair<int,string>(100,'one hundred and'));
hashmap.insert(pair<int,string>(900,'nine hundred and'));
}
string createstring(double num) {
string str="";
int digits[9]= {0};
int len=0;
if !(num) {
str = "zero";
return str;
}
if (num < 21) {
str = hashmap(num);
return str;
}
while(num) {
digits[len++] = num % 10;
num = num / 10;
}
str = 3digitutility(digits,8);
if (str) {
str += " million ";
}
str += 3digitutility(digits,5);
if (str) {
str += " thousand ";
}
str += 3digitutility(digits,2);
return str;
}
string 3digitutility(char[] arr,int i) {
string str="";
int len = 3;
while (len--) {
if (arr[i]) {
switch (len) {
case 3:
str += hashmap(arr[i]*100);
break;
case 2:
if (arr[i] > 1 ) {
str += hashmap(arr[i]*10);
} else {
str += hashmap(arr[i]*10 + arr[i--]);
}
break;
case 1:
str += hashmap(arr[i])
break;
}
i--;
}
}
Maintain an 'order' table as below.
order[0] = ""
order[1] = thousand
order[2] = million
order[3] = billion
order[4] = trillion
...
Have another table called text[] such as:
text[0] = "zero"
text[1] = "one"
..
text[999] = "nine hundred and ninety nine"
1. Count the number of digits to figure out the what 'order' the number belongs to - say, millions or thousands or units. This is obtained by order[(digit_count(n) -1)/3]
2. Chomp 3 digits at a time and print out: text[chomped_digits] + order[(digit_count(n) -1)/3] If chomping the number from MSDs is difficult, reverse the number, extract the last 3 LSDs using a % operator and then again reverse the extracted 3(or less) digits.
3. Go back to step 1 until the number is exhausted.
For ex:
1.123,456:
One hundred and twenty three *thousand*(order), four hundred and fifty six
2. 9,999,999
Nine *million*, nine hundred and ninety nine *thousand*, nine hundred and ninety nine.
This will work till 9999
/// <summary>
/// sureshsundar21@live.com
/// </summary>
public class NumberToString
{
Dictionary<int, string> dict = null;
public NumberToString()
{
dict = new Dictionary<int, string>();
dict.Add(1, "One"); dict.Add(2, "Two"); dict.Add(3, "Three"); dict.Add(4, "Four"); dict.Add(5, "Five");
dict.Add(6, "Six"); dict.Add(7, "Seven"); dict.Add(8, "Eight"); dict.Add(9, "Nine"); dict.Add(10, "Ten");
dict.Add(11, "Eleven"); dict.Add(12, "Twelve"); dict.Add(13, "Thirteen"); dict.Add(14, "Fourteen"); dict.Add(15, "Fifteen");
dict.Add(16, "Sixteen"); dict.Add(17, "Seventeen"); dict.Add(18, "Eighteen"); dict.Add(19, "Nighteen");
dict.Add(20, "Twenty"); dict.Add(30, "Thirty"); dict.Add(40, "Fourty"); dict.Add(50, "Fifty"); dict.Add(60, "Sixty");
dict.Add(70, "Seventy"); dict.Add(80, "Eighty"); dict.Add(90, "Nighty"); dict.Add(100, "hundread"); dict.Add(1000, "thousand");
}
public string ConvertToString(int input)
{
if (input < 10)
{
return (dict[input]);
}
else if (input > 9 && input < 20)
{
return (dict[input]);
}
else if (input > 20)
{
StringBuilder str = new StringBuilder();
List<KeyValuePair<int, int>> list = SplitNumber(input);
foreach (var entry in list)
{
if (entry.Value > 10 && entry.Key > 0)
{
str.Append(dict[Convert.ToInt32(entry.Key)]).Append(" ").Append(dict[Convert.ToInt32(entry.Value)]).Append(" ");
}
else if (entry.Value == 10 && entry.Key > 0)
{
str.Append(dict[(entry.Key * entry.Value)]).Append(" ");
}
else if (entry.Value == 1 && entry.Key > 0)
{
if (list.Count > 2)
str.Append(" and ");
str.Append(dict[entry.Key]);
}
}
return str.ToString();
}
return string.Empty;
}
public List<KeyValuePair<int, int>> SplitNumber(int input)
{
List<KeyValuePair<int, int>> list = new List<KeyValuePair<int, int>>();
int lenindex = 0;
string inputstr = Convert.ToString(input);
int len = inputstr.Length;
lenindex = len - 1;
int digit = 0;
while (lenindex > 0)
{
string divider = string.Empty;
//char =
for (int count = 0; count < lenindex; count++)
{
divider = divider + "0";
}
divider = "1" + divider;
digit = input / Convert.ToInt32(divider);
list.Add(new KeyValuePair<int, int>(digit, Convert.ToInt32(divider)));
input = input - (digit * Convert.ToInt32(divider));
lenindex--;
}
list.Add(new KeyValuePair<int, int>(input, 1));
return list;
}
}
string NumToString(int n)
{
string[] one_dig = {"zero", "one", ..., "nine"};
string[] two_dig_minor = {"ten", "eleven", ..., "nineteen"};
string[] two_dig_major = {"twenty", "thirty", ..., "ninety"};
string[] unit = {"hundred", "thousand", ..., "trillion"};
string result = "";
if (n < 0)
return "error";
while (true)
{
int tenPow = Math.Log(n);
if (tenPow == 0) //1 digit
{
s = s + dig1[n];
break;
}
else if (n < 20)
{
s = s + two_dig_minor[n - 10];
break;
}
else if (n < 100)
{
int temp = n / (Math.Pow(10, tenPow)); // n = n / (10 ^ tenPow);
s = s + two_dig_major[n - 2];
n = n % (Math.Pow(10, tenPow));
}
else
{
int temp = n / (Math.Pow(10, tenPow)); // n = n / (10 ^ tenPow);
s = s + dig1[temp] + unit[tenPow - 2];
n = n % (Math.Pow(10, tenPow));
}
}
return s;
}
import queue
#import list
d_h = {
2 : 'ten',
3 : 'hundred',
4 : 'thousand',
5 : 'thousand',
6 : 'lakh',
7 : 'lakh',
8 : 'crore',
9 : 'crore'
}
ty_di = ['elevan','twelve','thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen']
se_di = ['ten','twenty','thirty','forty','fifty','sixty','seventy','eighty','ninty']
one_di = ['one','two','three','four','five','six','seven','eight','nine']
def populate(f_item,s_item,let):
#print (f_item,s_item,let)
if s_item !=0 and f_item != 0:
if s_item != 1:
let.append(se_di[s_item-1] +' '+one_di[f_item-1] )
#let.append()
else:
let.append(ty_di[f_item-1])
elif s_item ==0 and f_item != 0:
let.append(one_di[f_item-1])
elif s_item !=0:
let.append(se_di[s_item-1])
else:
pass
def letters(s):
q = queue.Queue()
l = len(s)
let = []
digit = 1
p_index = 0
for i in range(l-1,-1,-1):
q.put((s[i],digit))
digit = (digit+1)
while (not q.empty()):
ele,digit = q.get()
n = int(ele)
#print (let , ele , digit)
if digit == 2:
s_item = n
f_item = let.pop()
populate(f_item,s_item,let)
p_index = digit
elif digit == 3:
if n != 0:
let.append(d_h[digit])
let.append(one_di[n-1])
p_index = digit
else:
pass
elif digit > 3:
if (digit % 2) != 0 :
f_item = let.pop()
s_item = n
#print (f_item,s_item)
if n != 0 or f_item != 0:
let.append(d_h[digit])
populate(f_item,s_item,let)
p_index = digit
else:
let.append(n)
else:
let.append(n)
if (p_index != digit):
item = let.pop()
if digit in d_h:
let.append(d_h[digit])
let.append(one_di[item-1])
else:
let.append(one_di[item-1])
#let = let.reverse()
print (' '.join(let[::-1]))
if __name__ =='__main__':
print ("Enter the Number:")
s = (input())
letters(s)
Declare an array of number[]={"one","two" ... }; upto 99
and another array of place[]= {"hundred","thousand" ... }; upto your need.
now count the number of digits
e.g while(1){
v=x/10; /* v is any temp variable and x contain your number */
count++; /* initial value = 0 */
if(v==0)
break;
}
on count we get the no. of digits .
Reverse the digit
e.g
temp=v;
num=0;
while(temp!=0){
v=x%10;
num=num*10+v;
x=x/10;
temp--;
}
now on every odd value of v (i.e number of digits ) read two at a time (>3)
suppose : 12345
so here we have 5 digits ,therefor read first two value at a time 12
and do it as
char *ch;
ch=number[12];
printf ch;
if digit==5
ch=place[2]; and so on...
printf ch;
o/p = twelve thousand
and for last three digit read first
ch=number[v];
print ch;
if(v==3)
ch=place[1];
print ch;
/* append the result to o/p */
o/p = twelve thousand three hundred
if(v<3)
ch=number[v];
print ch;
append answer with o/p
o/p = twelve thousand three hundred forty five
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/*
* Bharath P
* Please send an email @ bharath.paturi@gmail.com for any clarifications or issues
*/
public class GetAllCombinations
{
private static String inputArr [][] = {{"One", "Two", "Three", "Four", "Five","Six", "Seven", "Eight", "Nine"},
{"Ten", "Twenty", "Thirty", "Fourty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety",},
{"One Hundered", "Two Hundred", "Three Hundered", "Four Hundred", "Five Hundered", "Six Hundred", "Seven Hundered", "Eight Hundred", "Nine Hundred"},
{"One Thousand", "Two Thousand", "Three Thousand", "Four Thousand", "Five Thousand", "Six Thousand", "Seven Thousand", "eight thousand", "Nine Thousand"},
{"Ten Thousand", "Twenty Thousand", "Thirty Thousand", "Forty Thousand", "Fifty Thousand", "Sixty Thousand", "Seventy Thousand", "Eighty Thousand", "Ninty Thousand"},
{"One Lakh", "Two Lakh", "Three Lakh", "Four Lakh", "Five Lakh", "Six Lakh", "Seven Lakh", "Eight Lakh", "Nine Lakh"},
{"Ten Lakh", "Twenty Lakh", "Thirty Lakh", "Fourty Lakh", "Fifty Lakh", "Sixty Lakh", "Seventy Lakh", "Eighty lakh", "Ninety Lakh"},
{"One Crore", "Two Crore", "Three Crore", "Four Crore", "Five Crore", "Six Crore", "Seven Crore", "Eight Crore", "Nine Crore"},
{"Ten Crore", "Twenty Crore", "Thirty Crore", "Fourty Crore", "Fifty Crore", "Sixty Crore", "Seventy Crore", "Eighty Crore", "Ninty Crore"}};
private static Map<String, String> map = new HashMap<String, String>();
public static void main(String[] args)
{
long num = 7111111;
int multipleOfTen = 1;
List<String> list = new ArrayList<String>();
map.put("TenOne", "Eleven");
map.put("TenTwo", "Twelve");
map.put("TenThree", "Thirteen");
map.put("TenFour", "Fourteen");
map.put("TenFive", "Fifteen");
map.put("TenSix", "Sixteen");
map.put("TenSeven", "Seventeen");
map.put("TenEight", "Eighteen");
map.put("TenNine", "Nineteen");
long originalNum = num;
while (num > 0)
{
long remainder = num % 10;
num = num/10;
if (remainder != 0)
{
remainder = remainder - 1;
}
else
{
multipleOfTen += 1;
continue;
}
String s = inputArr[multipleOfTen - 1][(int)remainder];
if (list.size() > 0)
{
String [] currentSplit = s.split(" ");
String [] previousSplit = list.get(list.size() - 1).split(" ");
if (currentSplit.length == 2 &&
previousSplit.length == 2 &&
currentSplit[1].equals(previousSplit[1]))
{
String oldString = list.remove(list.size() - 1);
String newString = currentSplit[0] + oldString;
String [] stringSplit = newString.split(" ");
if (map.get(stringSplit[0]) != null)
{
list.add(map.get(stringSplit[0]) + " " + stringSplit[1]);
}
else
{
list.add(stringSplit[0] + " " + stringSplit[1]);
}
}
else
{
if (map.get(currentSplit[0] + previousSplit[0])!= null)
{
String value = map.get(currentSplit[0] + previousSplit[0]);
list.remove(list.size() - 1);
list.add(value);
}
else
{
list.add(s);
}
}
}
else
{
list.add(s);
}
multipleOfTen += 1;
}
if (originalNum == 0)
{
System.out.println("Zero");
}
else
{
//Final String building
StringBuilder s= new StringBuilder();
for (int i = list.size() - 1; i >=0; i--)
{
s.append(list.get(i) + ", ");
}
s.replace(s.length() - 2 , s.length() - 1, "");
System.out.println(originalNum + ": " + s);
}
}
}
public void test() {
int input = 90;
HashMap<Integer, String> hash = new HashMap<Integer, String>();
hash.put(1, "one");
hash.put(2, "two");
hash.put(3, "three");
hash.put(4, "four");
hash.put(5, "five");
hash.put(6, "six");
hash.put(7, "seven");
hash.put(8, "eight");
hash.put(9, "nine");
hash.put(11, "eleven");
hash.put(12, "twelve");
hash.put(13, "thirteen");
hash.put(14, "fourteen");
hash.put(15, "fifteen");
hash.put(16, "sixteen");
hash.put(17, "seventeen");
hash.put(18, "eighteen");
hash.put(19, "ninteen");
hash.put(10, "ten");
hash.put(20, "twenty");
hash.put(30, "thirty");
hash.put(40, "fourty");
hash.put(50, "fifty");
hash.put(60, "sixty");
hash.put(70, "seventy");
hash.put(80, "eighty");
hash.put(90, "ninety");
int number = input;
int count = 0;
if (number == 0) {
count = 1;
} else {
while (number != 0) {
number = number / 10;
count++;
}
}
for (int i = count - 1; i >= 0; i--) {
int x = input / (int) Math.pow(10, i);
input = input - x*(int) Math.pow(10, i);
if (i == 2) {
System.out.print("" + hash.get(x) + " hundred ");
}
if (i == 1) {
if (x == 0) {
} else if (x != 1) {
System.out.print("" + hash.get(x * 10) + " ");
} else {
System.out.print("" + hash.get(x * 10 + input) + " ");
break;
}
}
if (i == 0 && x != 0) {
System.out.println("" + hash.get(x));
}
}
}
Here is my solution, assuming printing it using Indian Number (Lakh, Crore)
It can be converted to Million/Billion convention, keeping same concept
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Testyourskills
{
/// <summary>
/// Given a number give its english form
/// Max number is: 999, 999, 999
/// Author: Pramod Kumar Chandoria
/// </summary>
public class NumberToWord
{
private IDictionary<int, string> mUnitByIndex = new Dictionary<int, string> {{2, ""}, {3, " Hundred "},{5, " Thousand "}, {7, " Lakh "}, {9, " Crore "}};
private IDictionary<int, string> mNumberBetween11To19 = new Dictionary<int, string> {{1, "Eleven"},{2, "Twelve"}, {3, "Thirteen"}, {4, "Fourteen"}, {5, "Fifteen"},{6, "Sixteen"}, {7, "Seventeen"}, {8, "Eighteen"}, {9, "Ninteen"}};
private IDictionary<int, string> mTenNumberWordMap = new Dictionary<int, string> {{1, "Ten"},{2, "Twenty"}, {3, "Thirty"}, {4, "Fourty"}, {5, "Fifty"},{6, "Sixty"}, {7, "Seventy"}, {8, "Eighty"}, {9, "Ninty"}};
private IDictionary<int, string> mUnitNumberWordMap = new Dictionary<int, string> { { 0, "Zero" }, { 1, "One" }, { 2, "Two" }, { 3, "Three" }, { 4, "Four" }, { 5, "Five" }, { 6, "Six" }, { 7, "Seven" }, { 8, "Eight" }, { 9, "Nine" } };
public string ToWord(int number)
{
int n = number;
if (n < 0 || n > 999999999)
{
return "Number supported between 0 to 999,999,999";
}
if (n < 10)
{
return mUnitNumberWordMap[n];
}
String sNumber = "";
IList<short> numbers = new List<short>();
int index = 0;
int lastDigit = 0;
while (n > 0)
{
index++;
int currentDigit = n%10;
if (index == 1)
{
// NO OOP
}
else if (index == 2)
{
sNumber = getWordByTwoDigit(currentDigit, lastDigit) + " " + sNumber;
}
else if (index == 3)
{
if (currentDigit > 0)
{
sNumber = mUnitNumberWordMap[currentDigit] + " Hundred " + sNumber; // TODO: Add AND
}
}
else if (index %2 == 0) {
// Do something only if last unit
if (n < 10)
{
sNumber = mUnitNumberWordMap[currentDigit] + mUnitByIndex[index + 1] + sNumber;
}
}
else
{
sNumber = getWordByTwoDigit(currentDigit, lastDigit) + mUnitByIndex[index] + sNumber;
}
lastDigit = currentDigit;
n = n / 10;
}
return sNumber;
}
private string getWordByTwoDigit(int unit, int lastDigit)
{
if (unit == 0)
{
if (lastDigit > 0)
{
return mUnitNumberWordMap[lastDigit];
} else {
return "";
}
}
if (unit == 1)
{
return mNumberBetween11To19[lastDigit];
}
var result = mTenNumberWordMap[unit];
if (lastDigit > 0)
{
result += " " + mUnitNumberWordMap[lastDigit];
}
return result;
}
static void Main(string[] args)
{
var nToW = new NumberToWord();
Console.WriteLine("56789= " + nToW.ToWord(56789));
Console.WriteLine("1000= " + nToW.ToWord(1000));
Console.WriteLine("1= " + nToW.ToWord(1));
Console.WriteLine("0= " + nToW.ToWord(0));
Console.WriteLine("20= " + nToW.ToWord(20));
Console.WriteLine("100= " + nToW.ToWord(100));
Console.WriteLine("111= " + nToW.ToWord(111));
Console.WriteLine("999,999,999= " + nToW.ToWord(999999999));
Console.WriteLine("-999,999,999= " + nToW.ToWord(-999999999));
Console.WriteLine("1999,999,999= " + nToW.ToWord(1999999999));
}
}
}
Here is console output of this program
56789= Fifty Six Thousand Seven Hundred Eighty Nine
1000= One Thousand
1= One
0= Zero
20= Twenty
100= One Hundred
111= One Hundred Eleven
999,999,999= Ninty Nine Crore Ninty Nine Lakh Ninty Nine Thousand Nine Hundred N
inty Nine
-999,999,999= Number supported between 0 to 999,999,999
1999,999,999= Number supported between 0 to 999,999,999
Press any key to continue . . .
A working solution in Python. The only thing it lacks is it doesn't insert the word "and".
units = ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
teens = ["", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
tens = ["", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
thousands = ["", "thousand", "million", "billion", "trillion"]
def num_words(num):
words = []
if num == 0:
words.append("zero")
else:
numstr = str(num)
groups = (len(numstr) + 2) / 3
numstr = numstr.zfill(groups * 3)
for i in range(0, groups * 3, 3):
h = int(numstr[i])
t = int(numstr[i+1])
u = int(numstr[i+2])
g = groups - (i / 3 + 1)
if h >= 1:
words.append(units[h])
words.append("hundred")
if t > 1:
words.append(tens[t])
if u >= 1:
words.append(units[u])
elif t == 1:
if u >= 1:
words.append(teens[u])
else:
words.append(tens[t])
else:
if u >= 1:
words.append(units[u])
if g >= 1 and (h + t + u) > 0:
words.append(thousands[g])
return " ".join(words)
- sma.jazayeri February 16, 2014string NumToString(int n) { string[] one_dig = {"zero", "one", ..., "nine"}; string[] two_dig_minor = {"ten", "eleven", ..., "nineteen"}; string[] two_dig_major = {"twenty", "thirty", ..., "ninety"}; string[] unit = {"hundred", "thousand", ..., "trillion"}; string s = ""; if (n < 0) return "error"; while (true) { int tenPow = Math.Log(n); if (tenPow == 0) //1 digit { s = s + dig1[n]; break; } else if (n < 20) { s = s + two_dig_minor[n - 10]; break; } else if (n < 100) { int temp = n / (Math.Pow(10, tenPow)); // n = n / (10 ^ tenPow); s = s + two_dig_major[n - 2]; n = n % (Math.Pow(10, tenPow)); } else { int temp = n / (Math.Pow(10, tenPow)); // n = n / (10 ^ tenPow); s = s + dig1[temp] + unit[tenPow - 2]; n = n % (Math.Pow(10, tenPow)); } } return s; }