Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

## Friday, November 30, 2012

### Find all the permutations of an array A

## 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

### Given an array randomize it

## 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

### Generic graph with weights

## 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

### Merge sort a linked list

## 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

### Compute the longest path in a binary tree

## 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

### Back to basic: all the nodes in a level

Subscribe to:
Posts (Atom)