CareerCup

static final char[][] keyPad = {
   {}, {}, { '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' }
   };
static void printCombinations(int[] number) {
 if (number != null && number.length > 0)
 printer(number, 0, "");
}
static void printer(int[] number, int index, String current) {
 if (index >= number.length) {
  System.out.println(current);
 return;
 }
 if (number[index] >= keyPad.length || keyPad[number[index]].length == 0) {
  printer(number, index + 1, current);
  return;
 }
 for (char c : keyPad[number[index]])
  printer(number, index + 1, current + String.valueOf(c));
}

public LinkedList<String> matchPhoneAddress(int[] inputs) {
		LinkedList<String> allCombinations = findAllCombs(inputs);
		LinkedList<String> results = new LinkedList<String>();
		for (String combination : allCombinations) {
			if (phoneAddressContains(combination)) {
				results.add(combination);
			}
		}
		return results;
	}
	
	public LinkedList<String> findAllCombs(int[] inputs) {
		if (inputs == null) {
			return null;
		}
		
		int size = inputs.length;
		LinkedList<String> results = new LinkedList<String>();

		if (size == 1) {
			results.addAll(getLetters(inputs[0]));
			return results;
		}
		
		LinkedList<String> letters = getLetters(inputs[size - 1]);
		LinkedList<String> previousResults = findAllCombs(Arrays.copyOf(inputs, size-1));
		for (String letter : letters) {
			for (String previousResult : previousResults) {
				results.add(previousResult + letter);
			}
		}
		
		return results;
	}

If I understand it correct, the interviewer wants to search the phone book using alphabets rather than phone number. If so, this question is similar to Google's auto-complete function introduced a while ago.

The simplest way is to search the phone book letter by letter. Take the first key stroke, convert it to the three letters it may represent and search the first letter in phone book matching one of the three. This process repeats itself on the remaining result set until there's no match found.

One alternative approach I can think of is to convert letters in phone book into corresponding keys and store the numeric value as strings in a sorted tree or array. The search is then performed on number rather than alphabet, hence reducing the complexity by 2/3.

The time complexity for both approaches is log(n) to begin with (provided the address book is already stored in sorted data structure) and decreases as more keystrokes are added.

This should depend on what you would like to permute: either to permute based on number, or permute based on char.

I have provided 2 versions of code.

public class Phonebook {

	static final char[][] keyPad = {
		   {}, {}, { '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' }
		   };
	
	static final char[][] used = {
		   {}, {}, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },
		   { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }
		   };
	
	static StringBuilder strb = new StringBuilder();
	
	static void permute(int[] input, int len){
		if(strb.length() == len){
			// print out since we are done with all numbers
			System.out.println(strb);
		}
		
		for(int k: input){
			if(used[k].length < 1 || used[k][0] == 1)continue;
			
			// print the chars belonging to this k
			for(char c: keyPad[k]){
				strb.append(c);
			}			
			if(used[k].length > 1)
				used[k][0] = 1;
			
			permute(input, len);
			
			used[k][0] = 0;
			strb.setLength(strb.length() - keyPad[k].length);
		}
	}
	
	static void permute_chars(int[] input, int len){
		if(strb.length() == len){
			//print out since we are done with all chars
			System.out.println(strb);
		}
		
		for(int k : input){
			for(int j = 0; j < keyPad[k].length; j++){
				if(used[k][j] == 1) continue;
				strb.append(keyPad[k][j]);
				used[k][j] = 1;
				
				permute_chars(input, len);
				
				strb.setLength(strb.length()-1);
				used[k][j] = 0;
			}
		}
	}
	
	public static void main(String[] args){
		int[] input = new int[]{1,2,3};
		int sum = 0;
		for(int k: input){
			sum += keyPad[k].length;
		}
		//Phonebook.permute_chars(input, sum);
		Phonebook.permute(input, sum);
	}
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PhoneKeyPad
{
    /// <summary>
    /// Mobile phone's keypad where "2" is mapped to ABC, "3" to DEF and so on. 
    /// Given any sequence of integers, find all the (matching) combinations in your phone book
    /// </summary>
    class PhoneKeyPad
    {
        static void Find(string input, int index, string[] list,char[] output)
        {
            if (index == input.Length)
            {
                Console.WriteLine(output);
                return;
            }
            int p = input[index] - '0';
            for (int i = 0; i < list[p].Length; i++)
            {
                output[index]= list[p][i];
                Find(input,index+1,list,output);
                output.Initialize() ;
            }
        }
        //output cant be string because overwriting has to be done in several cases not just appending.
        static void Main(string[] args)
        {
            string[] list = { "_",".","ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
            string input = "21304";
            char[] output=new char[5];
            Find(input,0,list,output);
            Console.ReadLine();
        }
    }
}