Clone a graph

Problem Description

Given an undirected graph write a function that returns a CLONE of that graph, example of an undirected graph:

1  ———-  2

|            /

|      /

3

Each node has a label and a list of neighbors (represented as an ArrayList).

Solution code


map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); //This map is gonna be used to check if a node has been already created,

//we use the original node as a key and the clone node as the value.

UndirectedGraphNode clone(UndirectedGraphNode node)
{
    if(map.containsKey(node)) //if the current node has been already cloned then just return the cloned node
        return map.get(node);

    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);  // create the clone node
    map.put(node, newNode); // put the clone into the map

    ArrayList<UndirectedGraphNode> nei = new ArrayList<UndirectedGraphNode>(); //create a new arraylist of neighbors for the new node

// loop through the neighbors of the original node and call our function recursively to build the new list of neighbors
    for(UndirectedGraphNode n : node.neighbors)
        nei.add(clone(n));

    newNode.neighbors = nei;
    return newNode;
}

Explanation:

It is basically a DFS traversal (http://en.wikipedia.org/wiki/Depth-first_search),  the clone function is called for every node and it returns the new cloned node with it’s corresponding list of neighbors, the key part here is that we need to keep track of those nodes that we have already cloned to avoid infinite loops, this is done with the HasMap.

String break

Problem description:

Given a String and a dictionary of words, write a program that returns true if the given string can be formed by concatenating one or more of the words in the dictionary, eg.

Given the string S = “algorithmstuff”

and the dictionary dic = {“algorithm”, “stuff”}

Our function must return true since S can be formed by concatenating “algorithm” + “stuff”

but given S = “algorithmstuffisgood”

and dic = {“algorithms”, “good”, “stuff”} must return false since there’s no way to build S from the strings in the dictionary.

Solution

This is a very good problem for a programming interview since it has one “lazy solution” which is very inefficient but it can be converted to a very fast algorithm with just a simple modification, so you could think about the most obvious solution even if it’s slow and once you got a working solution you can think about how to improve it.

This problem is clearly a good candidate for a recursive solution, for each recursive call the idea is to start checking if the first character is in our dictionary, if so, we call the function recursively but now with string S starting with the next character, otherwise we check if the first two characters form a valid word and so on, for instance:

S = “hithere”

dic = { “there”, “hi”}

We start with the string “hithere” at index 0, so we check if the substring “h” is a valid word, since it’s not we continue now with the next character which is “i”, now we check if the substring “hi” is a valid word in the dictionary, it is so we know that “hi” can be formed by concatenating one or more words of the dictionary so we now call the function recursively but starting with the next index which is 2, so now we are gonna have the same function with the substring “there”, we are gonna stop when we reach the end of the string S.

This is basically a DFS algorithm (http://en.wikipedia.org/wiki/Depth-first_search) , here the code:


public boolean stringBreak(String s, Set<String> dict) {
    return dfs(s, 0, dict);
}
boolean dfs(String s, int i, Set<String> dict)
{
    if(dict.contains(s.substring(i)))
        return true;

    for(int j = i; j < s.length(); ++j)
        if(dict.contains(s.substring(i, j + 1)))
            if(dfs(s, j + 1, dict, set)) return true;

    return false;
}

The solution above works! but it’s too slow since there are many overlapping calls (it does the same thing many times), let me show you with an example:

let’s say we have the string S = “helloworld”

and dict = {“he”, “e”, “h”}

Our recursive function is gonna build a tree like this:


                       helloworld

                   /                \

           h-elloworld           he-lloworld

                |

           e-lloworld

As you can see the substring “lloworld” is gonna be computed two times and the result is gonna be the same, the problem here is that we could end up with too many overlapping calls which would be a waste of time. So, how can we avoid overlapping calls?

The solution is to have a record of which substrings we have already computed so that when our function is called again for the same substring we already know the answer, this technique is called MEMOIZATION (http://en.wikipedia.org/wiki/Memoization), Here is the code that shows this optimization.


public boolean stringBreak(String s, Set<String> dict) {
    HashSet<Integer> memo = new HashSet<Integer>(); // We just need to keep track of those indexes that we have already computed and the result is false
    return dfs(s, 0, dict, memo);
 }
 boolean dfs(String s, int i, Set<String> dict, HashSet<Integer> memo)
 {
     if(dict.contains(s.substring(i)))
         return true;
     if(memo.contains(i)) // if we have already computed the result for this substring we just return the answer
         return false;
     //otherwise, compute the answer for this substring
     for(int j = i; j < s.length(); ++j)
         if(dict.contains(s.substring(i, j + 1)))
             if(dfs(s, j + 1, dict, set)) return true;

     //we just store the results for substrings which result is false
     memo.add(i);
     return false;
 }

Letter Combinations of a Phone Number

Before iPhones, we had phones with keypads like this:

hci3-f6

Where each digit corresponds to a set of three or four letters.

Problem Description:

Write a program that, given a phone number, return all possible letter combinations that can be formed. Eg.

Given 23

The following letter combinations can be formed: “AD”, “AE”, “AF”, “BD”, “BE”, “BF”, “CD”, “CE”, “CF”.

Given 234

The following letter combinations can be formed:

“ADG”,”ADH”,”ADI”,”AEG”,”AEH”,”AEI”,”AFG”,

“AFH”,”AFI”,”BDG”,”BDH”,”BDI”,”BEG”,”BEH”,

“BEI”,”BFG”,”BFH”,”BFI”,”CDG”,”CDH”,”CDI”,

“CEG”,”CEH”,”CEI”,”CFG”,”CFH”,”CFI”.

Solution

This problem requires a complete search solution since we need to explore all possible letter combinations, more specifically we are gonna use a well known technique called BACKTRACKING (http://en.wikipedia.org/wiki/Backtracking), it is basically a recursive function that builds a tree “on the fly”, at each recursive call it gets the set of letters that corresponds to the current digit and calls itself recursively for every letter but now with the next digit as parameter.


 //Global variables
 StringBuilder tempSolution;
 ArrayList<String> result;
 String letters[];

 ArrayList<String> letterCombinations(String digits)
 {
     //Our map, we use the digit as an index to get the corresponding set of letters
     letters = new String[]{"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
     result = new ArrayList<String>();
     //tempSolution is used to build the solution on the fly
     tempSolution = new StringBuilder("");
     //here we call dfs function starting with digit at position zero
     backtracking(digits, 0);
     return result;
 }
 void backtracking(String digits, int i) // variable i points the current digit
 {
     //We get the set of corresponding letters for the current digit
     String setOfLetters = letters[digits.charAt(i) - 48];

     //Now we loop through the set of letters
     for(int a = 0; a < setOfLetters.length(); ++a)
     {
         //Append each one of the letters to our temporary solution
         tempSolution.append(setOfLetters.charAt(a));
         //have we finished?, if so, add this temporary combination to our resulting ArrayList
         if(i == digits.length() - 1)
             result.add(tempSolution.toString());
         else //otherwise call this function recursively but now with the next digit as current digit
             backtracking(digits, i + 1);

         //Here is where the magic of backtracking happens
         tempSolution.deleteCharAt(st.length() - 1);
     }
 }

It runs in O(3 ^ n), where n is the number of digits of the phone number.

Print a matrix in spiral order

Hi there,

Today I’m gonna share a solution for a very common problem for programming interviews, how to print a 2D matrix in spiral order.

Problem description:

Given an M x N matrix, print all the elements in spiral order, for instance:

       [[1, 2, 3, 4]
        [2, 4, 9, 5]
        [9, 8, 7, 6]]

print: 1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 4, 9

This is an easy problem which interviewers use to test how clean you are able to code and how good you are at manipulating indexes, you need to be very careful when you try to come up with a solution for this problem, remember the KISS principle: KEEP IT SIMPLE & SHORT. Talking about programming interviews, usually when your idea requires more than 30 – 40 lines of code it meas that it’s not a good solution.

Solution:

The idea is to have four indexes: top, down, left and right which are gonna be used to point where we are gonna start printing rows and columns, when top > down or left > right then we are done.

void spiralOrder(int[][] matrix)
{
     if(matrix.length == 0)
         return;
     // Initialize our four indexes
     int top = 0;
     int down = matrix.length - 1;
     int left = 0;
     int right = matrix[0].length - 1;

     while(true)
     {
         // Print top row
         for(int j = left; j <= right; ++j) System.out.print(matrix[top][j] + " ");
         top++;
         if(top > down || left > right) break;
         //Print the rightmost column
         for(int i = top; i <= down; ++i) System.out.print(matrix[i][right] + " ");
         right--;
         if(top > down || left > right) break;
         //Print the bottom row
         for(int j = right; j >= left; --j) System.out.print(matrix[down][j] + " ");
         down--;
         if(top > down || left > right) break;
         //Print the leftmost column
         for(int i = down; i >= top; --i) System.out.print(matrix[i][left] + " ");
         left++;
         if(top > down || left > right) break;
     }
 }

This solution works for any M x N matrix, time complexity: O(M * N) space complexity: Constant