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()

Optimized Fibonacci sequence

Hi everyone,

Today I’m gonna share the solution for one of the most famous programming interview problems, given a number n, write a program to get the nth element of the Fibonacci sequence.

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, … where the first two numbers are 0 and 1, and each subsequent number is the sum of the previous two.

Here there’s an obvious recursive solution:

int fibo(n)
{
    if n<=2:
        return 1;
    else:
        return fibo(n-1) + fibo(n-2);
}

it works fine for a very small n ( <= 30), but what if we need to compute the 10,000th element of the sequence?

Solution:

First of all I want to explain why the above algorithm doesn’t work for a big n, let’s illustrate how it works as a recursion tree:

let’s say we need to get the 5th element of the sequence, so we have:

fib_5

As you can see, there are a bunch of overlapping calls to fibo, actually this algorithm is O(2^n) in time complexity because to get the nth element of the sequence we need to compute all the n-1 elements and for each one we have two recursive calls… it’s just too slow!

Now, with a very small modification we can improve the efficiency of this program, it’s basically adding a “cache” table for our “already known” results, let’s take a look at the code (in Python):

#!/usr/bin/python -tt

memo = {}

def main():
    f = open("data.in","r")
    for line in f:
        print fibo(int(line))

def fibo(n):
    if n <= 2:
        return 1
    if n in memo:
        return memo.get(n)

    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]

if __name__ == '__main__':
  main()

memo is a hashtable where we store the results for each fibo function call, so if we compute fibo(5), we don’t need to re-compute fibo(5) in the future because we already have the result in our memo table 🙂 so now we can compute fibo(10000) in just fractions of millisecond and this is because now our program runs in O(n).