Interview Question for Software Engineer at eBay:

Sep 2, 2012

This is a permutation problem. Each number maps to 3 or 4 letters, except zero, which does not map to anything.
Create map of each number to an array of characters: ncMap.get(1) returns {A,B,C}
Let int[] input be the phone number.

int print(int[] input, int inputStartPos, HashMap<Integer,Character[]> ncMap, List<Character> accumulator){
  if(input == null || inputStartPos < 0 || inputStartPos > input.length-1) return -1;
  Character[] chars = ncMap.get(input[inputStartPos]);
  if(inputStartPos == input.length-1){
    for(int i = 0; i < chars.length; i++){
      printAccumulator(accumulator); // print all chars we have so far.
      print(chars[i]);
    }
    return 0; // success
  }
  else {
    for(int i = 0; i < chars.length; i++){
      accumulator.append(chars[i]);
      print(input, inputStartPos++, ncMap, accumulator);
    }
  }
}