Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Friday, November 30, 2012
Thursday, November 29, 2012
Find the lowest common ancestor
For a binary tree
for a binary search tree
Wednesday, November 28, 2012
Serialize and deserialize a generic tree
File * serialize (node * n);
node * deserialize (File * f);
Tuesday, November 27, 2012
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)?
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
Friday, November 23, 2012
Thursday, November 22, 2012
Identify all the pythagorian triplets in the given array.
2 , 4 -> 4 + 16 = 20
1, 3 -> 1 + 9 = 10
In efficient way
1, 3 -> 1 + 9 = 10
In efficient way
Wednesday, November 21, 2012
BST, kth
Find the Kth largest integer in a Binary Search Tree.
Tuesday, November 20, 2012
Find non-unique characters in a given string
Optimal complexity in time and space
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
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
Huge file of parenthesis ( .. ) . Find if they are balanced
The file is huge and you don't want to run out of memory.
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)
Saturday, November 10, 2012
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
Wednesday, November 7, 2012
Given an array of integers compute the subsequence of max sum
Here the code.
Tuesday, November 6, 2012
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
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
Subscribe to:
Posts (Atom)