The meaning of life

Someone in my team pointed out that now I have an answer to the meaning of the life http://www.bing.com/search?q=42

Facebook Graph Search and Bing Web Search suggestions

You have probably seen the new Facebook Graph Search for searching Facebook internal data. Anytime you search something from the public Web, then you will use the suggestions coming from Bing Web Search. This is a feature run by my team. Congratulation to all of them for driving the amazing team who shipped the core web suggestions feature from London

Calculate the span on a stock

You are given the value of a stock during different days. For each day d, we want to know how many preceding and consecutive day the stock had a value less or equal to the one observed on d.

finding the longest substring with at least k occurrence

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)