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.

Advertisements

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

Longest Substring Without Repeating Characters

Problem description:

Given a string, find the length of the longest substring without repeating characters, for example, s = “abcabc”, the longest substring without repeating characters is “abc” so the length is 3.

First Approach:

Like always, there is a non optimal solution, actually a quadratic solution, just loop the array and for each element loop the array again by keeping track of the elements that we have visited and stop when you find a repeating character, this will give us the longest substring without repeating characters. This solutions works but is too slow, can we do it better? yes.

A better approach:

We just need to look at it a little bit closer to realize that at each time we find a repeating character we don’t need to start again at position i + 1, because we know that all the remaining elements except the element at position i are unique. Let’s clarify this idea with an example:

s = “abcab”

1.- Lets start looping through our array, at first we have “a”, do we have already an “a”?, No. So let’s store “a” and continue with the next element.

2.- Now we have “b”, do we have already a “b” ?, Nope, so we store the “b” and continue.

3.- We get a “c” , we don’t have any “c” already stored, so store it and continue.

4.- Now we get an “a”, do we have already an “a”?, Yes we have. So now we know that so far all the elements are different but the “a” at position 0 and the “a” at position 3, with our first approach we just would start again at position 1, but it’s not necessary because we know that all the remaining elements from index 1 to 3 are different, so we just ignore the “a” at position 0 and continue with the next character. By doing this we are gonna avoid a bunch of operations and now we have a much more efficient algorithm.

Here the working code in Java:


public int lengthOfLongestSubstring(String s) {

    int max = 0;
    int count = 0;
    int a[] = new int[26];
    Arrays.fill(a, -1);

    for(int i = 0; i < s.length(); ++i)
    {

        if(a[s.charAt(i) - 'a'] >= 0) {
            int from = a[s.charAt(i) - 'a'];
            count = i - a[s.charAt(i) - 'a'];
            a = new int[26];
            Arrays.fill(a, -1);

            for(int j = from + 1; j <= i; ++j)
                a[s.charAt(j) - 'a'] = j;
        }
        else {
            count++;
            a[s.charAt(i) - 'a'] = i;
        }

        max = Math.max(max, count);
    }

    return max;
 }

Two Sum Problem

Problem description:

Given an array of integers, find two numbers such that they add up to a specific target number.

Your function should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

There exist a very obvious quadratic solution, you would just need to loop through the array and for each i element loop from i +1 to n to look for the number which gives you a sum so that array[i] + array[j] = target. This approach works just fine but the problem is that it’s too slow, it runs in quadratic time O(n^2), could we do it better? Yes.

An optimized solution is to use an additional data structure which allows us to keep track of each number that we have and also its index, for this task we could use a HashMap which offers a constant time look-up operation, so we just need to loop the array once to store the elements and their corresponding indices in our HashMap and then loop through the array again and for each element i just check if hashmap.containsKey(target – array[ i ]). Here is the working solution implemented in Java:


public int[] twoSum(int[] numbers, int target) {
        
    HashMap<Integer, Integer> indexes = new HashMap<Integer, Integer>();
        
    for(int i = 0; i < numbers.length; ++i) {
        indexes.put(numbers[i], i);
    }
            
    for(int i = 0; i < numbers.length; ++i) {
        if(indexes.containsKey(target - numbers[i])) {
            return new int[]{i + 1, indexes.get(target - numbers[i]) + 1};
        }
     }
    return null;
}

This solution is much faster than the first approach, this runs in linear time (considering that HashMap look-up operation runs in constant time).

Check if a string has all unique characters without using extra space

Given a string, check if all its elements are unique, it means, there are no repeated characters.

example:

HELLO -> not all its characters are unique since character ‘l’ appears twice.

WORLD -> has all unique characters

This problem has many possible solutions, and to make it more interesting let’s suppose we are not allowed to use any extra data structure (a few extra variables are allowed but an entire copy of the array is not).

Solution.

Approach 1: Quadratic solution

The idea is to loop through the string an compare each element to the ones that we know they are unique so far, it could be done with the code below:

static boolean checkUniqueCuadratic(char arr[])
{
    int point = 0; //all elements before this point are unique for sure

    for(int i = 0; i < arr.length; ++i) // for each element, we are gonna compare to each unique element
    {
        char c = arr[i];

        for(int j = 0; j < point; ++j)
        {
            if(c == arr[j]) {
                return false;
            }
        }
        ++point; // at this time we now have a new unique element
    }
    return true;
}

Note that the solution above runs in quadratic time O(n^2) since it has two nested loops. We could probably just keep a data structure that allows us to keep of which elements we have visited and then just check if the ith element is within our helper data structure in just one loop, but remember we are not allowed to use any additional data structure.

Approach 2: “linearithmic” solution (n log n in time complexity)

Another good approach and actually faster is to sort the string by using any in place sorting algorithm which guarantees n log n in time complexity (like quicksort) and then just loop through the string and check if the next element equals the current element. The code below shows the implementation of this approach:


import java.util.*;

public class UniqueChars
{
    public static void main(String... args)
    {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNextLine())
        {
            char line[] = sc.nextLine().toCharArray();
            quicksort(line, 0, line.length - 1);// sort the string by using quicksort
            System.out.println(checkUnique(line));
        }
    }

    static boolean checkUnique(char arr[])
    {
        for(int i = 0; i < arr.length - 1; ++i)
            if(arr[i] == arr[i + 1])
                return false;

        return true;
    }

    /*
       Basic quicksort implementation
    */
    static void quicksort(char array[], int a, int b)
    {
        if(b - a < 1)
            return;

        int pivot = a;
        int i = a + 1;
        int j = b;

        while(i < j)
        {
            while(array[i] < array[pivot] && i < b) i++;
            while(array[j] > array[pivot] && j > a) j--;

            if(i < j)
                interchange(array, i, j);
        }
        interchange(array, pivot, j);

        quicksort(array, a, j - 1);
        quicksort(array, j + 1, b);
    }

    static void interchange(char arr[], int a, int b)
    {
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

You have any comment/suggestion/question? please let us know!!

Rotate a matrix by 90 degrees

Problem description: Given an N X N integer matrix, rotate it bye 90 degrees in place.
eg.

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

Solution:

The key is to solve this problem in “layers” from outer ones to inner ones as follows:

In our example we have two layers:

OUTER LAYER          INNER LAYER
1 2 3 4
9       6                               8 5
6       7                               5 3
9 2 6 8

The idea is to do a “four-way” swap variable, we need to move the values from top -> right, right -> bottom, bottom -> left and left -> top, can we do it by using only one extra variable? Yes, we can.

At each layer we are gonna loop through the elements and swap them as follows:
1.- Save the ith element in the top array in a temporary variable (in our example the top array is [1 2 3 4] ).
2.- Move the ith element from left to top.
3.- Move the ith element from bottom to left.
4.- Move the ith element from right to bottom.
5.- Save the value of our temporary variable in the ith position in the right array.

Here is the code in Python:

#!/usr/bin/python -tt

import sys

#create a N X N matrix
def getMatrix(n):
    matrix = []
    for i in range(n):
        inside = []
        for j in range(n):
            inside.append(j + i + 2)
        matrix.append(inside)
    return matrix

#print the matrix
def printMatrix(m):
    for row in m:
        print row
    print

#rotate the matrix by 90 degrees (clockwise) in place
def rotate90Degrees(m):
    layers = len(m) / 2
    length = len(m) - 1

    for layer in range(layers): #for each layer
        for i in range(layer, length - layer): # loop through the elements we need to change at each layer
            temp = m[layer][i] #save the top element, it takes just one variable as extra memory
            #Left -> Top
            m[layer][i] = m[length - i][layer]
            #Bottom -> left
            m[length - i][layer] = m[length - layer][length - i]
            #Right -> bottom
            m[length - layer][length - i] = m[i][length - layer]
            #Top -> Right
            m[i][length - layer] = temp

#main function
def main():
    #it takes values from stdin
    for line in sys.stdin:
        n = int(line)
        print "N = "+ str(n)
        matrix = getMatrix(n)
        print "Original matrix:\n"
        printMatrix(matrix)
        rotate90Degrees(matrix)
        print "Rotate matrix by 90 degrees:\n"
        printMatrix(matrix)

if __name__ == '__main__':
    main()

Some input/output samples:

N = 4
Original matrix:

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

Rotate matrix by 90 degrees:

[5, 4, 3, 2]
[6, 5, 4, 3]
[7, 6, 5, 4]
[8, 7, 6, 5]
************************************
N = 2
Original matrix:

[2, 3]
[3, 4]

Rotate matrix by 90 degrees:

[3, 2]
[4, 3]
*************************************
N = 5
Original matrix:

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

Rotate matrix by 90 degrees:

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

Square root of a number without using any built-in function

Problem description:

Given a number N, compute the square root.

Solution:

Alright, I know that every programming language has a built-in function to compute the square root of a number and of course that’s what you’re gonna use in a normal situation. But what if you are asked to solve this problem in a programming interview and you are not allowed to use any built-in function?

Well, to solve this problem we need to find a number which multiplied by itself becomes our given N, the simplest way to do it would be to loop from zero to N multiplying each number by itself and verifying if it equals N, but if we think about it for a while we  realize we can do it much faster, how?… Binary Search!.

Let’s explain this algorithm with a basic example, let’s say we want to compute the square root of 9.

We have our range of possible square roots: 0 to 9

1.- The idea is to get the middle element in our range: 9 + 0 / 2 = 4.5

2.- multiply it by itself: 4.5 * 4.5 let’s call this new value P = 20.25

3.- verify if P equals N, if it does then we have found the square root of N, if not…

4.- Now we have two possibilities:

– P is greater than N: in this case we are gonna modify our range of possibilities because we know all numbers greater than 4.5 are not the square root, so now our range of possible square roots are between 0 and 4.5

– P is less than N: This is the opposite, so we would modify our lower bound instead of the upper bound.

We are going to repeat these steps until we find the square root of N.

Below you can find the code for this solution in Python.

#!/usr/bin/python -tt

import sys

def sqrt(n):
    start = 0
    end = n
    m = 0
    min_range = 0.0000000001;
    
    while end - start > min_range:
        m = (start + end) / 2.0;
        pow2 = m * m
        if abs(pow2 - n) <= min_range:
            return m
        elif pow2 < n:
            start = m
        else:
            end = m
            
    return m

def main():
    for line in sys.stdin:
        n = int(line)
        print sqrt(n)

if __name__ == '__main__':
    main()