Microsoft Interview Question Software Engineer in Tests
Team: Windows Phone
Country: United States
Interview Type: In-Person
public static String expandPhone(final String phone) {
final StringBuilder sb = new StringBuilder(phone.length());
for (final char ch : phone.toCharArray()) {
if (Character.isDigit(ch)) {
sb.append(ch);
} else {
switch (Character.toUpperCase(ch)) {
case 'A':
case 'B':
case 'C':
sb.append(2);
break;
case 'D':
case 'E':
case 'F':
sb.append(3);
break;
case 'G':
case 'H':
case 'I':
sb.append(4);
break;
case 'J':
case 'K':
case 'L':
sb.append(5);
break;
case 'M':
case 'N':
case 'O':
sb.append(6);
break;
case 'P':
case 'Q':
case 'R':
case 'S':
sb.append(7);
break;
case 'T':
case 'U':
case 'V':
sb.append(8);
break;
case 'W':
case 'X':
case 'Y':
case 'Z':
sb.append(9);
break;
}
}
}
return sb.toString();
}
I think this is a good entry-level *screening* question.
Firstly, its solutions don't require foreknowledge of any "trick", just a basic understanding of ASCII layout and how to use it to do character translations.
Secondly, an efficient implementation is very elementary, and, as we see from earlier posted solutions, there are a variety of ways to solve the problem. It's easy to code in <10-15 minutes, perhaps longer for a candidate with minimal experience or for someone who feels a lot of stress or nervousness when interviewing for a job.
I personally only use this question for screening out the bottom 1:50 candidates, or those candidates who can't program at all under the stress of an interview. It will NOT tell me anything about the quality of the candidate when she/he writes an adequate solution.
Here's a straight forward solution in D that uses only an array table to translate the letters to numbers. It's more efficient than the hash-map solutions and simply leverages the positional adjacency of successive characters 'A'...'Z' in UTF-8 or ASCII encoding.
// This code is in D
string mapPhoneDigits(string s)
{
static string tbl = "22233344455566677778889999";
assert(tbl.length==26);
// An Appender is somewhat similar to StringBuilder in java.
// Alternatively the programmer could simply write each char to stdout
auto result = appender!string();
foreach (c; s)
{
if (c>='0' && c<='9')
result.put(c);
else if (c>='A' && c<='Z')
result.put(tbl[c-'A']);
}
return result.data;
}
int main(string[] argv)
{
string phoneNumber = "1-800-COM-CAST";
writeln(phoneNumber, " => ", mapPhoneDigits(phoneNumber) );
return 0;
}
Note to interviewers: Please do NOT waste your time with this question when interviewing senior candidates. Sadly, I recently experienced a company asking this question when I interviewed with them -- it's terribly easy and shows the candidate that the interviewer needs more training. On the other hand, if I accept their offer I can immediately help the team to improve their interview process :-)
Thanks Eric. I am new to programming and a quick question. Is it not necessary to convert the final phone number (string) to an int (or long)?
class Program
{
public static string getDigitsFromPhoneString(string str)
{
char[] pnArray = str.ToCharArray();
StringBuilder strBldr = new StringBuilder();
foreach (char chr in pnArray)
{
int res;
if (chr != '-')
{
if (Int32.TryParse(chr.ToString(), out res))
{
strBldr.Append(chr);
}
else
{
char ch = getDigitfor(chr);
if(ch != ' ')
strBldr.Append(ch);
}
}
}
return strBldr.ToString();
}
public static char getDigitfor(char chr)
{
switch (chr)
{
case 'a':
case 'b':
case 'c':
return '2';
//Similarly for rest characters
default: return ' ';
}
}
static void Main(string[] args)
{
getDigitsFromPhoneString("1800abacba");
}
}
#include<stdio.h>
#include<string.h>
main()
{
char a[20];
int b=0,i;
scanf("%s",a);
for(i=0;i<strlen(a);i++)
{
if(a[i]>='A'&&a[i]<='O')
{
b=b*10+(a[i]-'A')/3+2;
}
if(a[i]>='a'&&a[i]<='o')
{
b=b*10+(a[i]-'a')/3+2;
}
if(a[i]>='P'&&a[i]<='Z')
{
b=b*10+(a[i]-'P')/4+7;
}
if(a[i]>='p'&&a[i]<='z')
{
b=b*10+(a[i]-'p')/4+7;
}
}
printf("%d",b);
}
public Hashtable LookupTable()
{
var lookup = new Hashtable();
lookup['C'] = '2';
lookup['O'] = '6';
lookup['M'] = '6';
lookup['A'] = '2';
lookup['S'] = '7';
lookup['T'] = '8';
//....
return lookup;
}
public string TransformNumber(string cell)
{
var lookup = LookupTable();
var output = new StringBuilder();
int n = 0;
foreach (var number in cell)
{
if (number == '-')
{
continue;
}
if (!Int32.TryParse(number.ToString(), out n))
{
output.Append(lookup[number]);
}
else
{
output.Append(number);
}
}
return output.ToString();
}
}
}
public string telephonewords(string str)
{
char[] ca = str.ToCharArray();
int i=0;
Dictionary<char, int> dic = new Dictionary<char, int>();
dic.Add('A', 2);
dic.Add('a', 2);
dic.Add('B', 2);
dic.Add('b', 2);
dic.Add('C', 2);
dic.Add('c', 2);
dic.Add('D', 3);
dic.Add('d', 3);
dic.Add('E', 3);
dic.Add('e', 3);
dic.Add('F', 3);
dic.Add('f', 3);
dic.Add('G', 4);
dic.Add('g', 4);
dic.Add('H', 4);
dic.Add('h', 4);
dic.Add('I', 4);
dic.Add('i', 4);
dic.Add('J', 5);
dic.Add('j', 5);
dic.Add('K', 5);
dic.Add('k', 5);
dic.Add('L', 5);
dic.Add('l', 5);
dic.Add('M', 6);
dic.Add('m', 6);
dic.Add('N', 6);
dic.Add('n', 6);
dic.Add('O', 6);
dic.Add('o', 6);
dic.Add('P', 7);
dic.Add('p', 7);
dic.Add('Q', 7);
dic.Add('q', 7);
dic.Add('R', 7);
dic.Add('r', 7);
dic.Add('S', 7);
dic.Add('s', 7);
dic.Add('T', 8);
dic.Add('t', 8);
dic.Add('U', 8);
dic.Add('u', 8);
dic.Add('V', 8);
dic.Add('v', 8);
dic.Add('W', 9);
dic.Add('w', 9);
dic.Add('X', 9);
dic.Add('x', 9);
dic.Add('Y', 9);
dic.Add('y', 9);
dic.Add('Z', 9);
dic.Add('z', 9);
dic.Add('1', 1);
dic.Add('2', 2);
dic.Add('3', 3);
dic.Add('4', 4);
dic.Add('5', 5);
dic.Add('6', 6);
dic.Add('7', 7);
dic.Add('8', 8);
dic.Add('9', 9);
dic.Add('0', 0);
StringBuilder sb = new StringBuilder();
//foreach (KeyValuePair<Char, int> pair in dic)
//{
// Console.WriteLine("Key: {0}, Value: {1}", pair.Key, pair.Value );
//}
while(i< ca.Length)
{
if (ca[i] == '-')
i++;
if (dic.ContainsKey(ca[i]))
{
sb.Append(dic[ca[i]]);
i++;
}
}
// Console.WriteLine(sb);
return sb.ToString();
}
my $s = '1-800-COM-CAST';
my %hash = (
'2' => ['a', 'b', 'c'],
'3' => ['d', 'e', 'f'],
'4' => ['g', 'h', 'i'],
'5' => ['j', 'k', 'l'],
'6' => ['m', 'n', 'o'],
'7' => ['p', 'q', 'r', 's'],
'8' => ['t', 'u', 'v'],
'9' => ['w', 'x', 'y', 'z'],
);
foreach $key (keys %hash)
{
foreach $value (@{$hash{$key}})
{
if($s =~ /$value/i)
{
$s =~ s/$1/$key/g;
}
}
}
print "Now My string is $s";
This is an excellent candidate for using hash tables:
A possible solutions is as follows:
int lookUp(char character)
{
unordered_map< char , char > map;
map['a'] = 2;
map['b'] = 2;
map['c'] = 2;
...
map['x'] = 9;
map['y'] = 9;
map['z'] = 9;
map['A'] = 2;
map['B'] = 2;
map['C'] = 2;
...
map['X'] = 9;
map['Y'] = 9;
map['Z'] = 9;
// Makes sure the character key is in the hash map
assert(map.find(character) != map.end());
return map[character];
}
void printPhoneNumber(string alphaNumber)
{
for (int i = 0; i < alphaNumber.size(); ++i)
{
char currentCharacter = alphaNumber.at(i);
if (isdigit(currentCharacter))
cout << currentCharacter;
else if (currentCharacter == '-')
continue;
else
{
int digit = lookUp(currentCharacter);
cout << digit;
}
}
cout << endl;
}
int main()
{
string alphaNumber = "1-800-COM-CAST";
printPhoneNumber(alphaNumber); // Valid phone number
string alphaNumber2 = "1-800-C??-CAST";
printPhoneNumber(alphaNumber2); // Throws an Assertion error
return 0;
}
This took me longer than 15 minutes, so I guess I'm at the bottom of those 50 candidates. Here's a java solution that breaks out the functions a little more, but otherwise very similar to Leif's.
I'm assuming that the input is a string, and that this is code that should be written on the whiteboard, hence avoiding a long enum.
public class PhoneNumberParser{
public static void main(String[] args){
String s = "1-800-COM-CAST";
System.out.println(phoneNumParser(s));
return;
}
private static String phoneNumParser(String s){
s = s.toUpperCase();
StringBuilder outputString = new StringBuilder();
for(int i = 0; i<s.length();i++){
char c = s.charAt(i);
if (charIsLetter(c)) outputString.append(letterToNumber(c));
else if (charIsNumber(c)) outputString.append(c);
}
return outputString.toString();
}
private static Boolean charIsNumber(char c){
if (c >= '0' || c <= '9') return true;
else return false;
}
private static Boolean charIsLetter(char c){
if (c >= 'A' && c <= 'Z') return true;
else return false;
}
//Used a table instead of enum to make the code shorter
private static char letterToNumber(char c){
char[] lettersTable = {'1','1','1','2','2','2','3','3',
'3','4','4','4','5','5','5','6','6','6','7',
'7','7','8','8','8','9','9','9','9'};
return lettersTable[c - 'A'];
}
}
Solution in Java.
package com.practice;
import java.util.HashMap;
public class FormatedPhoneNumberTest {
private static HashMap<String, Integer> mapAlphaPhone = initPhoneMapping();
public static void main(String[] args) {
// Test
FormatedPhoneNumberTest fpnt = new FormatedPhoneNumberTest();
String phoneNumber = "1-800-COM-CAST";
System.out.println(fpnt.getFormattedPhoneNumber(phoneNumber));
}
public String getFormattedPhoneNumber(String phoneNumber) {
phoneNumber = removeSpecialChars(phoneNumber);
StringBuffer sf = new StringBuffer();
System.out.println("PHONE: " + phoneNumber);
for(int i=0; i < phoneNumber.length(); ++ i) {
if(mapAlphaPhone.containsKey(phoneNumber.substring(i, i + 1))) {
sf.append(mapAlphaPhone.get(phoneNumber.substring(i, i+1)));
}
else {
sf.append(phoneNumber.substring(i, i + 1));
}
}
return sf.toString();
}
public String removeSpecialChars(String str) {
str = str.replace("-", "");
str = str.replace(".", "");
str = str.replace("(", "");
str = str.replace(")", "");
return str;
}
public static HashMap<String, Integer> initPhoneMapping() {
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
hashMap.put("A",2);
hashMap.put("B",2);
hashMap.put("C",2);
hashMap.put("D",3);
hashMap.put("E",3);
hashMap.put("F",3);
hashMap.put("G",4);
hashMap.put("H",4);
hashMap.put("I",4);
hashMap.put("J",5);
hashMap.put("K",5);
hashMap.put("L",5);
hashMap.put("M",6);
hashMap.put("N",6);
hashMap.put("O",6);
hashMap.put("P",7);
hashMap.put("Q",7);
hashMap.put("R",7);
hashMap.put("S",7);
hashMap.put("T",8);
hashMap.put("U",8);
hashMap.put("V",8);
hashMap.put("W",9);
hashMap.put("X",9);
hashMap.put("Y",9);
hashMap.put("Z",9);
return hashMap;
}
}
package collections;
import java.util.regex.Pattern;
public class TelephineAlphanumeric {
private String PATTERN="[a-z]";
private String phoneNumber="";
private int currPosition=0;
Pattern pattern=null;
public TelephineAlphanumeric()
{
pattern=Pattern.compile(PATTERN);
}
public TelephineAlphanumeric(String phoneNumber)
{
pattern=Pattern.compile(PATTERN);
this.phoneNumber=phoneNumber.toLowerCase();
findTelephoneNumber(this.phoneNumber);
}
private int getPositionNumber(char ch)
{
int temp = (int)ch;
if(temp<=122 && temp>=97)
{
int pos=(temp-96);
int pool=pos / 3;
int rem=pos % 3;
if(rem>0)pool++;
pos=pool+1;
return pos ;
}
else
{
return 0;
}
}
public void setTelephoneNumber(String phoneNumber)
{
if (phoneNumber==null||phoneNumber.length()==0)
{
throw new RuntimeException("Input Is Not Valid.");
}
this.currPosition=0;
this.phoneNumber=phoneNumber.toLowerCase();
findTelephoneNumber(this.phoneNumber);
}
private void findTelephoneNumber(String phoneNumber)
{
char posChar=this.phoneNumber.charAt(this.currPosition);
String currChar=String.valueOf(posChar);
int posNum=getPositionNumber(posChar);
if(isMatch(currChar)&&posNum>0)
{
this.phoneNumber=this.phoneNumber.replaceAll(currChar,String.valueOf(posNum));
}
this.currPosition++;
if(this.currPosition<this.phoneNumber.length())
{
findTelephoneNumber(this.phoneNumber);
}
else
{
return;
}
}
private String getPhoneNumber()
{
this.phoneNumber=this.phoneNumber.replaceAll("-", "");
return this.phoneNumber;
}
private boolean isMatch(String input)
{
if(this.pattern.matcher(input).matches())
{
return true;
}
return false;
}
public static void main(String[] args) {
TelephineAlphanumeric telNum= new TelephineAlphanumeric();
telNum.setTelephoneNumber("1800-2-ABVBBBZ");
System.out.println(telNum.getPhoneNumber());
}
}
Here is my solution in Ruby:
#!/usr/bin/env ruby
class String
def alphanum_to_num
@pad ||=
begin
pad = Hash.new("")
groups = ["+","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"]
groups.each_with_index do |g,i|
a = g.split("")
a.each do |k|
pad[k] = i
end
end
(0..9).each{|v| pad[v.to_s] = v}
pad["-"] = ""
pad
end
s = self.split("-").join.split("")
s.collect{|v| @pad[v.upcase]}.join
end
end
numbers = ["1-800-COM-CAST","1-800-comcast","321-fiddley","a really stupid number"]
numbers.each do |n|
puts "#{n} -> #{n.alphanum_to_num}"
end
Store the mapping in a hashmap;
- Subhajit June 16, 2013A -> 2
B -> 2
...
Z-> 9
Then parse the input stream and for characters look up in the hashmap and get the digit for the alphabet.