A playful approach to tackle programming questions ("Phone words using dialpad" problem)

Programming questions are always tricky. It often makes you dazed and confused. Any software engineer interview for a programming position involves a couple of programming questions. After listening to a question from the interviewer, when you try to answer back and that's when you go erratic. That's pretty normal for everyone and there is no need to be worried and concerned. The objective of this post is to show a way to tackle such programming questions. It will illustrate a planned approach that you might want to tread on for easily arriving at solutions. I have taken a famous problem called "Phone words" to explain this approach.

“Phone words” is a programming question that features in many interviews to test the analytic skills of a programmer. The problem statement goes like this: You are given a 7 or 10 digit phone number. In every telephone or a cell phone, we have numbers ranging from 0 to 9 in the dial pad. Every digit in the dial pad has either 0 or 3 or 4 letters mapped for every digit. For the given phone number you need to find out all combinations of words that is possible using the letters of every digit of the phone number.

I couldn’t find a clean solution for this question anywhere and so wanted to post my solution along with the approach taken. Be it any programming question, if you work to find a solution without doing any ground work, it is not going to help at all. A step by step systematic approach is what will help you find a solution. It’s a skill to learn and acquire but an art to conquer!!

Programming problems can be addressed in the same way you prepare yourself to play a new computer game. Say, suppose you heard about a new game from a game-maniac friend of yours. He is in all praises for this game. And now, after listening to all those good stories from him, you are very desperate to play this game. You are restless. You wait with no patience for the day to arrive so that you can play this wonderful game. Imagine how you prepare yourself to play a computer game, a game that you have never played in the past. Imagine how excited you will be, sitting right before the screen waiting for the game to load. Once your game starts, your curious playful mind will begin to find out answers for the following questions

1. What exactly is the objective or mission of this game?
2. What are the aids and powers that I’m provided with as a player? Do I carry health tabs, armory, high-tech weapons?
3. Is there any specific learning or understanding that I need to do about my given aids and powers?
4. Can I play this game for the first few times just to familiarize myself without being mindful about my mission, without worrying about whether I’m winning or losing?
5. After I get a sense that I’m comfortable playing this new game, I have to think and plan a little bit around those deadly traps and devilishly humongous demons with whom I want to deal carefully. What is the appropriate time to use my powers so that they can be put to best use?
6. And finally, I will try to frame a strategy to tackle all my enemies so that I can effectively accomplish the mission of the game

That’s how you plan before playing a game, isn’t it? This exactly is the thought process that is needed to solve a programming problem. Once we are able to figure out answers for the above questions, it is going to be much easier to solve the actual problem. Let us follow the above steps and figure out how helpful they are in solving our “Phone words” problem.

What is the mission of this game?
The objective of the problem is to find out all possible words that could be created out of the given numbers. This is a classic example of a permutation and combination problem.

What are the aids and powers that I’m provided with as a player?
I’m given a set of numbers that represents a phone number and a phone dial pad that has numbers running through 0 to 9. Every number is mapped to a set of characters. Any one of those characters from every digit will be considered every time I try to create a possible word

Is there any specific learning that I need to perform about the aids and powers that I’m given with?
As a player, I’m provided with a phone dial pad and a set of numbers for which I need to create possible words. When I look at the dial pad, I see that not all numbers have the same 3 characters associated with them. It appears that there can be zero or more letters for a number. Digits like 0 and 1 don’t have any letters while digits 7 and 9 are mapped to 4 characters each. Wow, that’s a good point to understand before trying to solve the problem!

Can I play this game for the first few times just to familiarize myself without being mindful about my mission and without worrying about whether I’m winning or losing?
I want to play this game for a couple of times so that I can familiarize myself. I will be happy to choose the least difficult level so that it buys me more time on stage. Likewise, when a programming problem is given, it’s important to run through the problem with a couple of easy experiments. In this case, say for example, running through the problem using an imaginary phone number “23” will make me understand that the possible words are “AD”, “AE”, “AF”, “BD”, “BE”, “BF”, “CD”, “CE”, “CF”. Running through this exercise and illustrating the samples increases the confidence.

Can I think and plan a little bit around those deadly traps and devilishly humongous demons with whom I want to deal carefully?
When i'm playing a game, as soon as I spot some deadly traps, I want to think and plan a bit about them. I want to understand so that i can better tackle those traps. Likewise, there are a couple of traps in this problem. The numbers 0 or 1 do not have any characters associated with them. And there are numbers 7 and 9 that are mapped to 4 characters each, which is 1 character more than the typical 3 characters per number. This in turn means that a pure iterative solution might fail if it goes by the assumption that it is always 3 mapped characters per digit across board. I have to be careful about it. In case of 0 or 1, it will be the digits 0 and 1 used for creating a word and when it is 7 or 9, I must be careful to use all the 4 characters to create words. To re-familiarize myself, I need to run through those traps a couple of times to improve my understanding. Say, I’m now given with an imaginary number “702”. Then the possible word combinations will be “P0A”, “P0B”, “P0C”, “Q0A”, “Q0B”, “Q0C”, “R0A”, “R0B”, “R0C”, “S0A”, “S0B”, “S0C”.

Can i frame a strategy to tackle all the enemies so that i can accomplish the mission of the game?
Now comes the big part. I know quite a bit about the game now. I know about the powers that I’m given with, I know where to hunt for gold and I’m aware of the exact place and point at which those devils will show up. Now, it’s time for me to craft a plan, a plan that will defend me and defy all my enemies. Thinking at a very high level, there are two ways I can solve this problem.

Iterative Solution:
Let’s say I’m given with an imaginary phone number 234 ({abc}, {def}, {ghi}). Then as a first step, i have to think about the number of possible words that can be created out of that phone number. It will be 3x3x3 = 27 words.

Let me run through this solution in my mind. As the first digit of the given phone number is 2, I can have the letters - a, b and c stashed separately. Once I see the second digit 3, I can append every mapped character of 3 to the previously stashed words. Now the stashed words become ad, bd, cd and ae, be, ce and af, bf, cf. The next digit is 4 and so the stashed words will now become – adg, bdg, cdg, aeg, beg, ceg, afg, bfg, cfg, adh, bdh, cdh, aeh, beh, ceh, afh, bfh, cfh, adi, bdi, cdi, aei, bei, cei, afi, bfi, cfi. Running through this gives me a clue that this is an iterative solution. Additionally I need two lists, one with the stashed words and the other list for retaining the new words that are created by appending the stashed words with the letter that I’m iterating with. After appending all letters mapped for a digit with the stashed words, the new list becomes the stashed list after which the new list is emptied to ready for the next iteration. Simple, isn’t it?

/**
 * Returns the list of words created using phone dial pad and the given phone number
 * @param digits the phone number
 * @return list of combination of words
 */
public static ArrayList<String> getWordFromDialPad(String digits) {
  ArrayList<String> res = new ArrayList<String>();
  ArrayList<String> preres = new ArrayList<String>();
  res.add("");

  for (int i = 0; i < digits.length(); i++) {
   for (String str : res) {
    String letters = map.get(digits.charAt(i));
    for (int j = 0; j < letters.length(); j++)
     preres.add(str + letters.charAt(j));
   }
   res = preres;
   preres = new ArrayList<String>();
  }
  return res;
 }

This iterative solution looks simple but the only drawback is it needs more space to stash the list of words for every iteration. The complete implementation can be accessed from my GitHub repository - Phone words iterative solution.

Recursive Solution:
This is another solution for the same problem. In fact, this solution is a blend of recursive and iterative. The best part of this solution is that it just needs a single array equal to the size of the phone number!! Awesome isn’t it? No more extra space is needed!! Recursive solutions are interesting to understand and efficient most of the times. Instead of thinking iteratively, recursion will make you think differently. It wants you to go deep down and loop through all possible combinations in the lowest possible levels and then slowly climb upper levels to repeat the same. And that’s exactly this recursive method does

/**
 * Recursive helper method to create a word from dial pad
 * @param word character array
 * @param numbers given input numbers as string
 * @param start the index of input digit that is being processed
 */
private static void getWordFromDialPad(char[] word, String numbers, int start) {
  // base case -> start is the index value of the position from the word
  if (start > (numbers.length() - 1)) {
    System.out.println(++counter + " ==> " + new String(word));
    // look up dictionary to find whether the word is meaningful or not
    return;
  }

  // Identify the number of iterations based on the digit
  Integer number = numbers.charAt(start) - '0';
  int iterations = getSizeOfFirstDimension(number);


  // Iteration in a recursive method is equal to number of possible chars a digit can take
  // for eg. digit 2 can take 3 possible chars - A, B and C where as digit 7 can take 4 different chars
  for (int j = 0; j < iterations; j++) {
    // store a possible character for the digit and move on to the next position by 
    // calling the recursive method again
    word[start] = getCharacterFromDialPad(number, j);
    getWordFromDialPad(word, numbers, start + 1);
  }
}

That’s the core part of this recursive solution. The rest of the implementation has helper methods to support the above recursion. The complete implementation can be accessed from my GitHub repository - Phone words recursive solution.

A preface of any book will brief and summarize about what the book is about. Likewise it is very important to understand the preface of a programming problem by asking the above questions. It is very similar to the set of questions that you ask yourselves when you get ready to play a new game. Running through a couple of simple experiments will give deeper understanding and confidence. It will stand as a stepping stone to craft the final solution!!