Thursday, November 29, 2012

Wednesday, November 28, 2012

Serialize and deserialize a generic tree

File * serialize (node * n); node * deserialize (File * f);

Monday, November 26, 2012

Isomorphic trees

Two trees can be called isomorphic if they have similar structure and the only difference amongst them can be is, that their child nodes may or may not be swaped. Write a function to detect whether two trees are isomorphic
int isIsomorphic(Node root1,Node root2) {
   if(root1==null && root2==null)
       return 1;
         
   if((root1 ==  null && root2 != null) || (root1 !=null && root2 == null ))
     return 0;
             
    if(root1.val == root2.val){
             
       if(isIsomorphic(root1.left, root2.left) == 1){
            return (isIsomorphic(root1.right, root2.right));
       } else if(isIsomorphic(root1.left, root2.right) == 1){
            return (isIsomorphic(root1.right, root2.left));
       }
             
    }
         
return 0;
}

Sunday, November 25, 2012

Pascal’s triangle is a triangular array of the binomial coefficients

Method 1 -
Each line n is the binomial coefficient C(n, k) where k is the row. This has complexity n^3. because in this case k has the same order of n

Method 2
Complexity n^2, with space n^2

Method 3
complexity n^2, with space O(1) -- this is more difficult because you need to move in the triangle storing just a constant number of locations. Can you express C(n, k) as function of C(n, k-1)?

Saturday, November 24, 2012

Compute the binomial coefficient in efficient way


C(n, k) = n ! / (n-k) ! k! = n (n-1) ... (n-k+1) / 1. 2. ... (k-1)k

C(n,k) = C(n, n-k) = n! / (n-n +k)! (n-k)!  so we can change r to r-p is r > p-r and keep the operation smaller


for (i = 0; i < k; i++)
{
    res *= (n - i);
    res /= (i+1);
}

O(k) time and (1) space

Thursday, November 22, 2012

Wednesday, November 21, 2012

BST, kth

 Find the Kth largest integer in a Binary Search Tree. 

Tuesday, November 20, 2012

Monday, November 19, 2012

Sunday, November 18, 2012

Gas stations

You have a certain number of gas stations in a circle and a car running on the circle. The car has a certain amount of gas available at the beginning. Find the right station to start for not running out of gas

This is a version of max subarray

Saturday, November 17, 2012

Creating a generic graph

Here the code based on C++, template, and boost::unordered_map and boost::unordered_multimap

Friday, November 16, 2012

Thursday, November 15, 2012

Construct BST from given preorder traversal

Construct BST from given preorder traversal (recursive solution)

Wednesday, November 14, 2012

Linked list

Given an unidirectional linked list, return the last but k element. No recursion

Tuesday, November 13, 2012

Deep copy

A random link list is a linked list where every node contains 2 links, one like a normal node which points to the next node. The other link points to a random node in the list, even itself. You are to write a function to perform a deep copy of this random link list.

Monday, November 12, 2012

Transormations

Given a number n and another number m, which is a permutation of n find the number of moves needed to transform m into n.

Sunday, November 11, 2012

Shortest path

Given a binary square matrix of size n*n. 1 means there is a path, 0 means no path. Find the shortest path and print it from (0,0) to (n-1, n-1)

Friday, November 9, 2012

Matrix of 0/1

Find all the islands and return them. An island is a sub-matrix of contiguous 1s.

Thursday, November 8, 2012

Select a number from a stream with uniform probability

Here the code. the tricky part is the uniform probablity and the stream, which should be ideally processsed with O(1) memory

Tuesday, November 6, 2012

Compute the longest path in a binary tree

Given a binary tree, compute the longest length path

Here the code

Monday, November 5, 2012

Data structures in Boost

I like boost for the rich collection of data structures, which are very handful now and then.


  • Tuples, for tuples in mathematical sense
  • Any, when you have a collection of objects with different types 
  • Variant, when you have a collection of objects with different types, a modern version of union
  • Dynamic bitset, when you need to create a bitset whose dimension is unknown at compile time

Sunday, November 4, 2012

how many unique symbols in a file

Given a file of 1 petabyte containing unicode strings, compute the number of unique symbols contained in the file. Suppose that you have no more than 100Mb of available RAM.

Write some C++ code

Friday, November 2, 2012

Template typedef

In C++ you can have the first definition of a template class. However you cannot have a template typedef. In  C++0x this will be supported but for now the only thing that you can do is to have a typedef within a template struct, which will add a bit of un-necessary redundancy to the code


template <typename T>;
class C {...};
template <typename T>;
typedef T ;

Thursday, November 1, 2012

Back to basic: all the nodes in a level

Given a binary tree create create a list of nodes which are at the same level.

here the code