I just tried for my first programming interview and one of the questions was to write a program that given a 7 digit telephone number, could print all possible combinations of letters that each number could represent.
A second part of the question was, what about if this was a 12 digit international number? How would that effect you design.
I don't have the code I wrote in the interview, but I got the impression he wasn't happy with it. What is the best way to do this?
The obvious solution is a function to map a digit to a list of keys, and then a function that would generate the possible combinations:
The first is obvious, the second is more problematic because you have around 3^number of digits combinations, which can be a very large number.
One way to do it is to look at each possibility for digit matching as a digit in a number (on base 4) and implement something close to a counter (jumping over some instances, since there are usually less than 4 letters mappable to a digit).
The more obvious solutions would be nested loops or recursion, which are both less elegant, but in my opinion valid.
Another thing for which care must be taken is to avoid scalability issues (e.g. keeping the possibilities in memory, etc.) since we are talking about a lot of combinations.
P.S. Another interesting extension of the question would be localization.
namespace WordsFromPhoneNumber
{
/// <summary>
/// Summary description for WordsFromPhoneNumber
/// </summary>
[TestClass]
public class WordsFromPhoneNumber
{
private static string[] Chars = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
public WordsFromPhoneNumber()
{
//
// TODO: Add constructor logic here
//
}
#region overhead
private TestContext testContextInstance;
/// <summary>
///Gets or sets the test context which provides
///information about and functionality for the current test run.
///</summary>
public TestContext TestContext
{
get
{
return testContextInstance;
}
set
{
testContextInstance = value;
}
}
#region Additional test attributes
//
// You can use the following additional attributes as you write your tests:
//
// Use ClassInitialize to run code before running the first test in the class
// [ClassInitialize()]
// public static void MyClassInitialize(TestContext testContext) { }
//
// Use ClassCleanup to run code after all tests in a class have run
// [ClassCleanup()]
// public static void MyClassCleanup() { }
//
// Use TestInitialize to run code before running each test
// [TestInitialize()]
// public void MyTestInitialize() { }
//
// Use TestCleanup to run code after each test has run
// [TestCleanup()]
// public void MyTestCleanup() { }
//
#endregion
[TestMethod]
public void TestMethod1()
{
IList<string> words = Words(new int[] { 2 });
Assert.IsNotNull(words, "null");
Assert.IsTrue(words.Count == 3, "count");
Assert.IsTrue(words[0] == "A", "a");
Assert.IsTrue(words[1] == "B", "b");
Assert.IsTrue(words[2] == "C", "c");
}
[TestMethod]
public void TestMethod23()
{
IList<string> words = Words(new int[] { 2 , 3});
Assert.IsNotNull(words, "null");
Assert.AreEqual(words.Count , 9, "count");
Assert.AreEqual(words[0] , "AD", "AD");
Assert.AreEqual(words[1] , "AE", "AE");
Assert.AreEqual(words[2] , "AF", "AF");
Assert.AreEqual(words[3] , "BD", "BD");
Assert.AreEqual(words[4] , "BE", "BE");
Assert.AreEqual(words[5] , "BF", "BF");
Assert.AreEqual(words[6] , "CD", "CD");
Assert.AreEqual(words[7] , "CE", "CE");
Assert.AreEqual(words[8] , "CF", "CF");
}
[TestMethod]
public void TestAll()
{
int[] number = new int [4];
Generate(number, 0);
}
private void Generate(int[] number, int index)
{
for (int x = 0; x <= 9; x += 3)
{
number[index] = x;
if (index == number.Length - 1)
{
var w = Words(number);
Assert.IsNotNull(w);
foreach (var xx in number)
{
Console.Write(xx.ToString());
}
Console.WriteLine(" possible words:\n");
foreach (var ww in w)
{
Console.Write("{0} ", ww);
}
Console.WriteLine("\n\n\n");
}
else
{
Generate(number, index + 1);
}
}
}
#endregion
private IList<string> Words(int[] number)
{
List<string> words = new List<string>(100);
Assert.IsNotNull(number, "null");
Assert.IsTrue(number.Length > 0, "length");
StringBuilder word = new StringBuilder(number.Length);
AddWords(number, 0, word, words);
return words;
}
private void AddWords(int[] number, int index, StringBuilder word, List<string> words)
{
Assert.IsTrue(index < number.Length, "index < length");
Assert.IsTrue(number[index] >= 0, "number >= 0");
Assert.IsTrue(number[index] <= 9, "number <= 9");
foreach (var c in Chars[number[index]].ToCharArray())
{
word.Append(c);
if (index < number.Length - 1)
{
AddWords(number, index + 1, word, words);
}
else
{
words.Add(word.ToString());
}
word.Length = word.Length - 1;
}
}
}
}
Use a list L where L[i] = the symbols that digit i can represent.
L[1] = @,.,! (for example) L[2] = a,b,c
Etc.
Then you can do something like this (pseudo-C):
void f(int k, int st[])
{
if ( k > numberOfDigits )
{
print contents of st[];
return;
}
for each character c in L[Digit At Position k]
{
st[k] = c;
f(k + 1, st);
}
}
Assuming each list contains 3 characters, we have 3^7 possibilities for 7 digits and 3^12 for 12, which isn't that many. If you need all combinations, I don't see a much better way. You can avoid recursion and whatnot, but you're not going to get something a lot faster than this no matter what.
In Java using recursion:
import java.util.LinkedList;
import java.util.List;
public class Main {
// Number-to-letter mappings in order from zero to nine
public static String mappings[][] = {
{"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
{"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"},
{"T", "U", "V"}, {"W", "X", "Y", "Z"}
};
public static void generateCombosHelper(List<String> combos,
String prefix, String remaining) {
// The current digit we are working with
int digit = Integer.parseInt(remaining.substring(0, 1));
if (remaining.length() == 1) {
// We have reached the last digit in the phone number, so add
// all possible prefix-digit combinations to the list
for (int i = 0; i < mappings[digit].length; i++) {
combos.add(prefix + mappings[digit][i]);
}
} else {
// Recursively call this method with each possible new
// prefix and the remaining part of the phone number.
for (int i = 0; i < mappings[digit].length; i++) {
generateCombosHelper(combos, prefix + mappings[digit][i],
remaining.substring(1));
}
}
}
public static List<String> generateCombos(String phoneNumber) {
// This will hold the final list of combinations
List<String> combos = new LinkedList<String>();
// Call the helper method with an empty prefix and the entire
// phone number as the remaining part.
generateCombosHelper(combos, "", phoneNumber);
return combos;
}
public static void main(String[] args) {
String phone = "3456789";
List<String> combos = generateCombos(phone);
for (String s : combos) {
System.out.println(s);
}
}
}
This version in C# is reasonably efficient, and it works for non-western digits (like "۱۲۳۴۵۶۷" for example).
static void Main(string[] args)
{
string phoneNumber = null;
if (1 <= args.Length)
phoneNumber = args[0];
if (string.IsNullOrEmpty(phoneNumber))
{
Console.WriteLine("No phone number supplied.");
return;
}
else
{
Console.WriteLine("Alphabetic phone numbers for \"{0}\":", phoneNumber);
foreach (string phoneNumberText in GetPhoneNumberCombos(phoneNumber))
Console.Write("{0}\t", phoneNumberText);
}
}
public static IEnumerable<string> GetPhoneNumberCombos(string phoneNumber)
{
phoneNumber = RemoveNondigits(phoneNumber);
if (string.IsNullOrEmpty(phoneNumber))
return new List<string>();
char[] combo = new char[phoneNumber.Length];
return GetRemainingPhoneNumberCombos(phoneNumber, combo, 0);
}
private static string RemoveNondigits(string phoneNumber)
{
if (phoneNumber == null)
return null;
StringBuilder sb = new StringBuilder();
foreach (char nextChar in phoneNumber)
if (char.IsDigit(nextChar))
sb.Append(nextChar);
return sb.ToString();
}
private static IEnumerable<string> GetRemainingPhoneNumberCombos(string phoneNumber, char[] combo, int nextDigitIndex)
{
if (combo.Length - 1 == nextDigitIndex)
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
yield return new string(combo);
}
}
else
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
foreach (string result in GetRemainingPhoneNumberCombos(phoneNumber, combo, nextDigitIndex + 1))
yield return result;
}
}
}
private static char[][] phoneNumberAlphaMapping = new char[][]
{
new char[] { '0' },
new char[] { '1' },
new char[] { 'a', 'b', 'c' },
new char[] { 'd', 'e', 'f' },
new char[] { 'g', 'h', 'i' },
new char[] { 'j', 'k', 'l' },
new char[] { 'm', 'n', 'o' },
new char[] { 'p', 'q', 'r', 's' },
new char[] { 't', 'u', 'v' },
new char[] { 'w', 'x', 'y', 'z' }
};
In Python, iterative:
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def word_numbers(input):
input = str(input)
ret = ['']
for char in input:
letters = digit_map.get(char, '')
ret = [prefix+letter for prefix in ret for letter in letters]
return ret
ret is a list of results so far; initially it is populated with one item, the empty string. Then, for each character in the input string, it looks up the list of letters that match it from the dict defined at the top. It then replaces the list ret with the every combination of existing prefix and possible letter.
Oracle SQL: Usable with any phone number length and can easily support localization.
CREATE TABLE digit_character_map (digit number(1), character varchar2(1));
SELECT replace(permutations,' ','') AS permutations
FROM (SELECT sys_connect_by_path(map.CHARACTER,' ') AS permutations, LEVEL AS lvl
FROM digit_character_map map
START WITH map.digit = substr('12345',1,1)
CONNECT BY digit = substr('12345',LEVEL,1))
WHERE lvl = length('12345');