Find all the permutations of an array A

Find the lowest common ancestor

For a binary tree for a binary search tree

Serialize and deserialize a generic tree

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

Given an array randomize it

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;
}

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

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

Given an array of integers, populate another array with the product of the elements of the first array except for the current index element.

Identify all the pythagorian triplets in the given array.

2 , 4 -> 4 + 16 = 20
1, 3 -> 1 + 9 = 10

In efficient way

BST, kth

 Find the Kth largest integer in a Binary Search Tree. 

Find non-unique characters in a given string

Optimal complexity in time and space

Generic graph with weights

Here the code based on boost::unordered_map

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

Creating a generic graph

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

Huge file of parenthesis ( .. ) . Find if they are balanced

The file is huge and you don't want to run out of memory.

Construct BST from given preorder traversal

Construct BST from given preorder traversal (recursive solution)

Linked list

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

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.

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.

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)

Merge sort a linked list

Matrix of 0/1

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

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

Given an array of integers compute the subsequence of max sum

Here the code.

Compute the longest path in a binary tree

Given a binary tree, compute the longest length path

Here the code

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

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

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 ;

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