Leaf to root path sum up to given number

Given a binary tree and a sum , return true if the tree has a "root to leaf" path such that adding up all the values along the path equals the given sum.
Return false if there is no path.

Successor integer with all unique digits.

Given a positive integer having all unique digits. Find the immediate next greater number having the same digits.

Pair of numbers which sum up to zero

Given an array of positive and negative integers. Find the pair of number whose sum is closer to zero.

Program to convert numbers into roman literals

Write a program to convert a number into roman numerals.

Decreasing order of integers from a stream of infinite numbers.

Given stream of infinite no of integers and a function named getnext() which gives the next integer from stream continuously.U have to store the numbers in decreasing order and remove duplicate also in efficient manner.

All duplicates and their counts in a string

Write an efficient C program to print all the duplicates and their counts in the input string

Here is the information for this problem

http://geeksforgeeks.org/?p=16

Given sum is consecutive integer or not

Given a number determine wether the number is sum of consecutive positive integers,if it is not return false else return true. conscutive integers can be from 2 to n

boggle solver problem

Here is the information of the boggle solver problem

http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver

highest frequency element in an array

Find the number with highest frequency in an array.

smallest window of an array

Given two arrays A [1..n] and B[1..m], find the smallest window in A that co
ntains all elements of B. That is, find a pair such that A[l..k] conta
ins B[1..m]

For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is
[3,5].

any efficient way to do that?

Random number from given range

Given a range 0-N, generate 'M' random numbers from the range without any duplication. The space complexity is O(1).

Sorted order linked list in a tree

Binary Search Tree Node has left, right and next pointers. Populate next pointers such that all nodes are connected in sorted order through next pointer.

Return all negative numbers in a matrix

2D Matrix(n * n) of positive and negative numbers is given. Matrix is sorted rowwise and columnwise. You have to return the count of -ve numbers in most optimal way.

k th smallest element in two sorted arrays.

Given two sorted integer arrays A and B of size n and m respectively, find the kth smallest element in the union of A and B in O(lg(n)+lg(m)) time

Top k elements in an array

Find top-k element in an integer array of size n.

All bit related quesions.

All bit related hacks and questions are in the following web link

http://graphics.stanford.edu/~seander/bithacks.html

permutation and comibnation

Write a program for printing all the permutations and combinations of given elements in an array.

Scheduling algorithm

Given a set of tasks with a duration and a deadline, how do you define a scheduling algorithm to minimize total lateness? and how to minimize # of late tasks?

Thoughts

Least laxity first scheduling algorithm

Median in a BST

Given a BST how do you find a median.

Matrix multiplication

Write a program for rising a given matrix to its kth power.

Queue with Max efficient MAX operation

Given a queue perform following operations.

1. Enqueue

2. Dequeue

3. MAX

constraints:- all the above operations should be implemented in such a way that they are of O(1) complexity

Here is the thought.

1.) Doubly linked list for queue.
2.) Keep max along with each node till that node.

Let say the queue is
2 ->8 ->6 ->9

struct{
int data
int max
struct * next
struct *prev
}

when 2 inserted, queue will be
(2,2)
when 8 inserted, queue will be
(2,2) -> (8,8)
when 6 inserted, queue will be
(2,2) -> (8,8) -> (6, 8)
when 9 inserted, queue will be
(2,2) -> (8,8) -> (6, 8) -> (9,9)

But in this implementation dequeue is not O(1).

Other thought is building max-heap for the queue.

Balanced binary tree from a linked list

Write a program to create a balanced binary tree from a linked list.

Multiple white spaces in a string to single whitespace

Given a string which may contain one or multiple white spaces in between the word characters. Replace all multiple whitespaces with a single white space .

Binary Indexed Tree (BIT)

In this post we will discuss the Binary Indexed Trees structure. According to Peter M. Fenwick, this structure was first used for data compression. Let’s define the following problem: We have n boxes. Possible queries are

1. Add marble to box i
2. Return sum of marbles from box k to box l

The naive solution has time complexity of O(1) for query 1 and O(n) for query 2. Suppose we make m queries. The worst case (when all queries are 2) has time complexity O(n * m). Binary Indexed Trees are easy to code and have worst time complexity O(m log n).

The two major functions are

• update (idx,val) : increases the frequency of index idx with the value val
• read (idx) : reads the cumulative frequency of index idx

Note : tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx where r is a position in idx of the last digit 1 (from left to right) in binary notation, f is frequency of index, c is cumulative frequency of index, tree is value stored in tree data structure.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f	1	0	2	1	1	3	0	4	2	5	2	2	3	1	0	2
c	1	1	3	4	5	8	8	12	14	19	21	23	26	27	27	29
tree	1	1	2	4	1	4	0	12	2	7	2	11	3	4	0	29

Table 1.1

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
tree	1	1..2	3	1..4	5	5..6	7	1..8	9	9..10	11	9..12	13	13..14	15	1..16

Table 1.2 – table of responsibility

Here’s a C++ template code :

#include 
using namespace std;  
template class BIT 
{       
	T *tree;       
	int maxVal;       
public:  BIT(int N)       
	{ 
               tree = new T[N+1];
               memset(tree,0,sizeof(tree)*(N+1));
               maxVal = N;       
	}       
	void update(int idx, T val)       
	{           
		 while (idx <= maxVal)
	          {
	                  tree[idx] += val;
	                  idx += (idx & -idx);
	            }
        }       
//Returns the cumulative frequency of index idx
       T read(int idx)
       {
 	        T sum=0;
	         while (idx>0)
	         {
	               sum += tree[idx];
	               idx -= (idx & -idx);
	         }
         return sum;
       }
 };
  int main() {     
	int a[100],cur=1,mul=2,add=19,MAX=65536,x,i;     
	//Initialize the size by the
     	//maximum value the tree can have
     BIT B(MAX);
     for (i=0;i<50;i++)
     {
        a[i] = cur;
         B.update(a[i],1);
         cur = ((cur * mul + add) % MAX);
     }
     while (cin>>x)
     {
           cout ,B.read(x), endl;
     }
  }

Number of binary trees for n nodes

• Question : What is the number of rooted plane binary trees with n nodes and height h?

Solution :
Let t_n,h denote the number of binary trees with n nodes and height h.

Lets take a binary search tree of n nodes with height equal to h. Let the number written at its root be the m^thnumber in sorted order, 1 ≤ m ≤ n. Therefore, the left subtree is a binary search tree on m-1 nodes, and the right subtree is a binary search tree on n-m nodes. The maximum height of the left and the right subtrees must be equal to h-1. Now there are two cases :

1. The height of left subtree is h-1 and the height of right subtree is less than equal to h-1 i.e from 0 to h-1.
2. The height of right subtree is h-1 and the height of left subtree is less than equal to h-2 i.e from 0 to h-2, since we have considered the case when the left and right subtrees have the same height h-1 in case 1.

Therefore t_n,h is equal to the sum of number of trees in case 1 and case 2. Let’s find the number of trees in case 1 and case 2.

1. The height of the left subtree is equal to h-1. There are t_m-1,h-1 such trees. The right subtree can have any height from 0 to h-1, so there are such trees. Therefore the total number of such tress are .
2. The height of the right subtree is equal to h-1. There are t_n-m,h-1 such trees. The left subtree can have any height from 0 to h-2, so there are such trees. Therefore the total number of such tress are .

Hence we get the recurrent relation

or

where t_0,0=1 and t_0,i=t_i,0=0 for i>0.
Here’s a sample C++ code.

#include

using namespace std;

#define MAXN 35

int main()

{

long long t[MAXN+1][MAXN+1]={0},n,h,m,i;

t[0][0]=1;

for (n=1;n<=MAXN;n++)

for (h=1;h<=n;h++)

for (m=1;m<=n;m++)

{

for (i=0;i < class="line alt1"> t[n][h]+=t[m-1][h-1]*t[n-m][i];

for (i=0;i < class="line alt1"> t[n][h]+=t[n-m][h-1]*t[m-1][i];

}

while (scanf("%lld%lld",&n,&h))

printf("%lld\n",t[n][h]);

}

Note :

1. The total number of binary trees with n nodes is , also known as Catalan numbers or Segner numbers.
2. t_n,n = 2^n-1.
3. The number of trees with height not lower than h is .
4. There are other recurrence relation as well such as
   .

Multiply number by 7

Efficient way of multiplying number by 7

Maximum word made of other words.

write a program to find the longest word made of other
words. For instance, If my file has the following words (sorted):
test
tester
testertest
testing
testingtester

The longest word should be testingtester.

Maximum sum of matrix.

Given a matrix M x N, find the maximum sum of a matrix.

Three numbers summing up to zero

Given three lists, A, B and C of length n each. Write a function which returns true if any 3 numbers sum up , one from each list, sum up to zero. Otherwise return false if there is no combination.

Largest matrix with 0's and 1's

Given a M x N matrix, find the largest square matrix with all 1's. Similarly find the largest rectangular matrix with all 1's

Dynamic arrays

Implement dynamic arrays.

Three integers in an array whose sum is closest to S

Given an array of integers, A₁, A₂, ..., A_n, including negatives and positives, and another integer S. Now we need to find three different integers in the array, whose sum is closest to the given integer S.

we can solve this in O(n²) time! First, consider that your problem P can be phrased equivalently in a slightly different way that eliminates the need for a "target value":

original problem P: Given an array A of n integers and a target value S, does there exist a 3-tuple from A that sums to S?

modified problem P': Given an array A of n integers, does there exist a 3-tuple from A that sums to zero?

Notice that you can go from this version of the problem P' from P by subtracting your target value from each element in A, but now you don't need the target value anymore.

Clearly, if we simply test all possible 3-tuples, we'd solve the problem in O(n³) -- that's the brute-force baseline. Is it possible to do better? What if we pick the tuples in a somewhat smarter way?

First, we invest some time to sort the array, which costs us an initial penalty of O(n log n). Now we execute this algorithm:

for (i in 1..n-2) {
  j = i  // Start where i is.
  k = n  // Start at the end of the array.

  while (k >= j) {
    // We got a match! All done.
    return (A[i], A[j], A[k]) if (A[i] + A[j] + A[k] == 0)

    // We didn't match. Let's try to get a little closer:
    //   If the sum was too big, decrement k.
    //   If the sum was too small, increment j.
    (A[i] + A[j] + A[k] > 0) ? k-- : j++
  }
  // When the while-loop finishes, j and k have passed each other and there's
  // no more useful combinations that we can try with this i.
}

This algorithm works by placing three pointers, i, j, and k at various points in the array. i starts off at the beginning and slowly works its way to the end. k points to the very last element. j points to where i has started at. We iteratively try to sum the elements at their respective indices, and each time one of the following happens:

• The sum is exactly right! We've found the answer.
• The sum was too small. Move j closer to the end to select the next biggest number.
• The sum was too big. Move k closer to the beginning to select the next smallest number.

For each i, the pointers of j and k will gradually get closer to each other. Eventually they will pass each other, and at that point we don't need to try anything else for that i, since we'd be summing the same elements, just in a different order. After that point, we try the next i and repeat.

Eventually, we'll either exhaust the useful possibilities, or we'll find the solution. You can see that this is O(n²) since we execute the outer loop O(n) times and we execute the inner loop O(n) times. It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

Subset sum problem

write an algorithm for subset sum problem

patience sort

Implementation of patience sorting algorithm.

/**

* Patience sort algorithm as per Aldous and Diaconis,

* using binary search to select the leftmost heap for a new card.

* Compares cards using operator<

*

* TableType requirements

* -# whatever lower_bound needs

* -# begin(), end(): ForwardIterator of piles

*

* PileType requirements

* -# default constructible

* -# constructible from a single card const reference

* typedef typename PileType::value_type card_type;

* -# push_back(const card_type&)

* -# assignable, lightweight on a singleton pile

* -# whatever lower_bound needs

* -# back() implemented or an

appropriate pile_less specialization

*/

template <>

void patience_sort

(TableType& table, InputIterator first,

InputIterator last)

{

typedef PileType pile_type;

typedef typename PileType::value_type card_type;

typedef TableType table_type;

typedef typename table_type::iterator iterator;

while (first != last) {

pile_type new_pile(*first); // read *first only once! (input iterator)

// find the leftmost heap with the top card greater

// than *first , to push *first on it

iterator pile_p = std::lower_bound(

table.begin(), table.end(), new_pile,

pile_less() );

if (pile_p != table.end()) {

pile_p->push_back(new_pile.back());

}

// ...or allocate a new heap on the

right with *first

else {

table.push_back(new_pile);

}

first++;

}

}

Implement strstr function

Write a program to search str2 in str1 and return the starting index of the occurence of str2 in str1

find sum of numbers equal to constant k

Given an array of numbers, find if sum of any two elements is equal to K (constant).

find the nth string in a file

Given a series A,B,C .......Z, AA, AB,AC,AD....AZ,BA,BB...BZ,CA....(Open excel sheet. The names of column represent the series). Given input as number 'n'. Output the 'n' th string of the series.

Simply convert 'n' to a base-26 number. Each digit maps to a letter.

void f(int n)
{
if(n == 0)
return;
f((n-1)/26);
printf("%c", ((n-1)%26+'A'));
}

Continuos sequence having the maximum sum

Given an array of integers (both positive and negative), find the continious sequence having the maximum sum.

Random element from a linked list.

Return a random element from list such that each element has equal probability of selection. This needs to be done given that you dont know the size of the linked list. And also in only one scan it should be performed.

Iterate through list from beginning
- Start by choosing between N1 and N2 with a 1/2 chance of picking either one.
- Then pick between ResultOf(N1,N2) and N3 with a 1/3 chance of picking N3 and 2/3 chance of picking ResultOf(N1,N2)
- Then pick between ResultOf(N1,N2,N3) and N4 with a 1/4 chance of picking N4 and 3/4 chance of picking ResultOf(N1,N2,N3)

Solution:
- Keep choosing between previousChoice and NewChoice with a 1/N chance of picking NewChoice and (N-1)/N chance of picking previousChoice where N is the Node number

Proof: If you go thorough the above example, N1 was chosen with a chance of (3/4)(2/3)(1/2)=(1/4)

binary search on a circularly shifted array

A sorted array is shifted circularly (i.e m elements from start are removed from start and added to the end). Now write an algorithm to search for an element.

public static int bS(int[] a, int left, int right, int key) {

while (left <= right) {

int mid = left + (right - left) / 2;

if (a[mid] == key)

return mid;

if (a[left] > a[mid]) {

// switching has happened in left partition

// if key is less than the mid, sure it is in left partition

if (key > a[mid] && key <>

// then RP

left = mid + 1;

else

// LP

right = mid - 1; // for 2 cases, one is : if key <>

} else if (a[right] <>

// partition

if (key <> a[right])

// then LP

right = mid - 1;

else

// RP

left = mid + 1; // 2 cases, one is : if key > a[mid]just

} else

// following 2 are cases where there is no switching at all

if (key <>

// LP

right = mid - 1;

else

// RP

left = mid + 1;

}

return -1;

}

Implement Queue using Stack.

Write a program to implement a Queue using Stack.

pairwise swap

Given a singly linked list, swap every two elements (e.g. a->b->c->d->e->f->null should become b->a->d->c->f->e->null). Code it such that memory position is swapped and not the node value.

Here is the program for the generic version of the above problem

http://crackinterviewtoday.wordpress.com/2010/03/28/k-reverse-linked-list/

find the diameter of a tree

Here is the program to find the diameter of a binary tree.

int diameter = 0;
int findDiameter(struct tree * node)
{
 int dim ,l_len,r_len;
 /* If null node came then return 0 */
 if(node == 0)
  return 0;
 /* Initialize all the temp length variables by 0 */
 dim = l_len = r_len = 0;
 /* Recursive call for left & right subtree */
 l_len = findDiameter(node->left);
 r_len = findDiameter(node->right);
 /* Calculate the depth at this level */ 
 dim = r_len + l_len + 1;
 /* If the current level diameter is bigger then previous */
 /* Then save the current diameter as biggest one */
 if(dim > diameter)
  diameter = dim;
 /* Return the depth, till current node */
 return (MAX(l_len,r_len) + 1);
}

Good programming problem

Given a log file which has customer id and corresponding to that id it has a page id visited by that customer. Given such log files for 3 consecutive days, design an algo to find those customers which visited the site on exactly 2 out of 3 days and visited at least 3 distinct pages. Discuss the design and space complexity. Optimize (question is not about using unix tricks)

find all anagrams in a file

Given a file containing approx 10 million words, Design a data structure for finding all the anagrams in that set

smallest number of multiplications

A calculator with only ":=" and "x". Given a and n, find the smallest number of multiplications to compute b=a^n

1. first compute N1 and N2 defined as:
N1 = floor(log2(n))
N2 = n - 2 ** N1

2. the number of multiplications needed is,
m = N1 + (# of bits set to 1 in N2)

(example)
the following is the example when n = 14:
N1 = floor(log2(14)) = 3
N2 = n - 2 ** N1 = 14 - 8 = 6
m = 3 + 2 = 5

a ** 14 is computed as follows using 5 multiplications.
a2 = a * a
a4 = a2 * a2
a8 = a4 * a4
a12 = a8 * a4
a14 = a12 * a2

Intersection of rectangles

Given n rectangles in a plane find whether two rectangles intersect or not.

Find cycles in directed graph

As far as I know, the best way to solve this would be with Tarjans(or Gabows or Kosaraju's --see Wikipedia link below) algorithm for finding strongly connected components of a graph. Strongly connected components and cycles are synonymous (not exactly).

To get a better idea, please see the following links:

1. Great explanation http://www.pointy-stick.com/blog/2009/02/04/finding-connectedness-directed-graphs/

2. Wikipedia on Tarjans algorithm:http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

3. A rigorous explanation: http://www.ics.uci.edu/~eppstein/161/960220.html

4. Other interesting links:
   http://discuss.joelonsoftware.com/default.asp?design.4.249152.10
   http://forums.sun.com/thread.jspa?threadID=597673
   http://coding.derkeiler.com/Archive/General/comp.theory/2004-02/0468.html

5. Similar question on SO: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

Now, that I've given the links, let me proceed to explain (after all its good answers and not links that really make stackoverflow such a great place).

Some points to remember (Taken from link 1):
1.Two vertices, A and B, are strongly connected if there's a path from A to B and a path from B to A.

2.The set of all vertices that are strongly connected to a given vertex forms a strongly connected component of a graph.

3.Any strongly connected component with more than one vertex in it is a cycle.

4.We want to somehow collapse all the vertices in a cycle into a single node in a 'tree' (See links). Any future cycle involving vertices we've already visited gets folded into the same node. What we end up with is a tree where each node is a strongly connected component.

5.To do this is to store two extra bits of information on each node. The number of steps the depth-first search takes to reach that node and the minimum number of steps the depth-first search takes to reach any node in that node's strongly connected component (from the nodes we've seen so far).

6.As we perform a depth-first search on the main graph, we use the secondary data structure to help with the testing of whether two nodes are "the same" (in the same strongly connected component, as it turns out) and add the current node to that secondary structure correctly.

Algorithm
The question you have isn't trivial to solve. Here's how Tarjans algorithm works-

1.The first thing to know is that you have to do a DFS. I am assuming that a stack is used to implement it. The DFS has to cover all vertices in the graph.

2.Each vertex v, has to be labeled with two values, the index and the lowval. The index is simply the order in which DFS visits the node. The lowval is the minimum of the v's index and the index of the vertex that is nearest to v in the DFS. This vertex is then pushed onto the stack.

3.For each vertex accessible from v, recurse if it isn't already in the stack.

4.For a vertex v, whose lowval == index, pop off all elements on the stack upto v itself and print them as

Here are few thoughts

1) A graph can be tree if the edges of the graph are |V| - 1 where |v| is number of vertices

2) Graph should be connected.

3) Graph should not have any cycle.

Facility location problems

Write algorithm for solving facility location problems.

k largest elements in an array

given an array of numbers, write a program to return the k largest numbers.
For eg: if the array of numbers is 2,9,6,4,3,8,56,39,5 and k=3 then return 56,39,9.

This can be solved in myriad ways.

1). if k is really small then one can use selection sort.

2) A variant of a quick sort can also be used for this problem.

3) construct min heap with k elements and then remove minimum element and insert an element from remaining array elements. After this process the larges elements will be left over in a heap.

Element which has no duplicate entries

Given an array of numbers where each number has a duplicate in the array except one number, write a program to return the lone number.

For eg: if the array is 1,8,5,8,1,3,5 then your program should return 3.

This can be achieved by XORing all the elements in the array. The final value in the variable after XORing is the result

Maximum collinear points.

Given n points of a plane, write an algorithm for finding maximum number of collinear points the plane.

Towers of hanoi

Psuedo code for towers of hanoi algorithm.

def Hanoi(n, A, C, B):

    if n != 0:

        // Transfer n-1 plates from A to B.

        Hanoi(n - 1, A, B, C)

        print 'Move the plate ', n, ' from ', A, ' to ', C

        // Now transfer n-1 plates from B to C.

        Hanoi(n - 1, B, C, A) 

Design patterns.

2). Decorator design pattern.

As an example, consider a window in a windowing system. To allow scrolling of the window's contents, we may wish to add horizontal or vertical scrollbars to it, as appropriate. Assume windows are represented by instances of the Window class, and assume this class has no functionality for adding scrollbars. We could create a subclass ScrollingWindow that provides them, or we could create a ScrollingWindowDecorator that adds this functionality to existing Window objects. At this point, either solution would be fine.

Now let's assume we also desire the ability to add borders to our windows. Again, our original Window class has no support. The ScrollingWindow subclass now poses a problem, because it has effectively created a new kind of window. If we wish to add border support to all windows, we must create subclasses WindowWithBorder and ScrollingWindowWithBorder. Obviously, this problem gets worse with every new feature to be added. For the decorator solution, we simply create a new BorderedWindowDecorator—at runtime, we can decorate existing windows with the ScrollingWindowDecorator or the BorderedWindowDecorator or both, as we see fit.

Another good example of where a decorator can be desired is when there is a need to restrict access to an object's properties or methods according to some set of rules or perhaps several parallel sets of rules (different user credentials, etc.) In this case instead of implementing the access control in the original object it is left unchanged and unaware of any restrictions on its use, and it is wrapped in an access control decorator object, which can then serve only the permitted subset of the original object's interface.

Design patterns.

1). Strategy design pattern.

According to Strategy pattern, the behaviors of a class should not be inherited, instead they should be encapsulated using interfaces. As an example, consider a car class. Two possible behaviors of car are brake and accelerate.

Since accelerate and brake behaviors change frequently between models, a common approach is to implement these behaviors in subclasses. This approach has significant drawbacks: accelerate and brake behaviors must be declared in each new Car model. This may not be a concern when there are only a small number of models, but the work of managing these behaviors increases greatly as the number of models increases, and requires code to be duplicated across models. Additionally, it is not easy to determine the exact nature of the behavior for each model without investigating the code in each.

The strategy pattern uses composition instead of inheritance. In the strategy pattern behaviors are defined as separate interfaces and specific classes that implement these interfaces. Specific classes encapsulate these interfaces. This allows better decoupling between the behavior and the class that uses the behavior. The behavior can be changed without breaking the classes that use it, and the classes can switch between behaviors by changing the specific implementation used without requiring any significant code changes. Behaviors can also be changed at run-time as well as at design-time. For instance, a car object’s brake behavior can be changed from BrakeWithABS() to Brake() by changing the brakeBehavior member to:

brakeBehavior = new Brake(); 

This gives greater flexibility in design and is in harmony with the Open/closed principle (OCP) that states classes should be open for extension but closed for modification.

If you are given two traversal sequences, can you construct the binary tree?

It all depends on what tree traversals are given.

Following tree traversals in conjunction can be used to create the binary tree.

Inorder and preorder

Inorder and postorder

Inorder and level order

All the combinations of tree traversals other than the above will not be able to used to generate the exact tree.

Here is the program given Inorder and preorder. In the similar lines one can write a program for Inorder and postorder also.

node* BST::buildTree(int *in, int inStrt, int inEnd, int len, int *pre)

{

if(preIndex >= len || inStrt > inEnd)

return NULL;

node *retNode = makeNode(pre[preIn dex++]);

if(inStrt == inEnd)

return retNode;

int inIndex = findNodeIn(in, inStrt, inEnd, retNode->data);

retNode->left = buildTree(in, inStrt, inIndex - 1, len, pre);

retNode->right = buildTree(in, inIndex+1, inEnd, len,pre);

return retNode;

}

int BST::findNodeIn(int* in, int inStrt, int inEnd, int value)

{

int i = inStrt;

for(;i<=inEnd;i++

if(in[i] == value)

return i;

}

int preIndex;

int main()

{

preIndex = 0;

int in[] = {1,2,3,4,5,7,8};

int pre[] = {4,2,1,3,7,5,8};

root = buildTree(in,0,6,7,pre);

}

nearest neighbor problem

You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.

First 3 horses among 25 horses

There are 25 horses among which you need to find out the fastest 3 horses. You can conduct race among at most 5 to find out their relative speed. At no point you can find out the actual speed of the horse in a race. Find out how many races are required to get the top 3 horses.

Strongly connected components.

Given below is the strongly connected components algorithm.

Input: Graph G = (V, E)

index = 0                    // DFS node number counter 

S = empty                   // An empty stack of nodes

forall v in V do

  if (v.index is undefined)     // Start a DFS at each node

    tarjan(v)                    // we haven't visited yet

 procedure tarjan(v)

  v.index = index               // Set the depth index for v

  v.lowlink = index

  index = index + 1

  S.push(v)                    // Push v on the stack

  forall (v, v') in E do       // Consider successors of v

    if (v'.index is undefined) // Was successor v' visited?

        tarjan(v')                     // Recurse

        v.lowlink = min(v.lowlink, v'.lowlink)

    else if (v' is in S)       // Was successor v' in stack S? 

        v.lowlink = min(v.lowlink, v'.index )

  if (v.lowlink == v.index)     // Is v the root of an SCC?

    print "SCC:"

    repeat

      v' = S.pop

      print v'

    until (v' == v)

In the above algorithm the graph is traversed using DFS traversal. All the vertices are pushed into the stack as they are visited. Initially v.index and v.lowlink are assigned same values. But v.lowlink is updated for each and every vertex with minimum of the v.lowlink of itself and v.lowlink of the child vertex. If the child vertex can reach the current vertex then the v.lowlink can have least value of v.lowlink. See that as the current vertex is already traversed and therefore present in stack then v.lowlink is updated to its v.index. Hence at the last if the current vertex's index is equal to its lowlink then the current vertex is root of the connected component. 

Depth first search notes.

Depth first search is done on tree, tree structure or graph. It starts by selecting a node as a root of a graph and explores one branch before backtracking.

In this process it creates a depth first search tree. The edges in this depth first search tree are classified into three categories.

FORWARD EDGES:

These edges point from parent node to its descendents.

BACK EDGES:

These edges point from descendants to ancestors.

CROSS EDGES:

All the edges that doesn't fit in above two categories fits here.

To start the depth first search any node can be chosen as a root whereas in directed graph we dont have that luxury. I we need to randomly pick a vertex as a root and then further the depth first search. If it happens that all the vertices are not visited with this approach then pick another randomly and do the depth first search until all the vertices are visited. (I am not sure about the above implementation of DFS for directed graphs. It is just my own version of writing it).

Important applications of Depth first search include.

1) Finding connected components.

2) Topological sorting.

3) Finding strongly connected components.

4) Solving puzzles like mazes through backtracking.

5) Finding 2-(edge or vertex)-connected components.

Two different ways to to topological sorting over a graph

The way to do topological sort is

1.Using DFS.

a) Do the DFS on the given graph and store the DFS tree.

b) Now on the DFS tree do postorder traversal and output the children.

c) Reverse the above output to get the Topological sort of the graph.

2. Removing the indegree zero nodes.

a) Start by printing the node which has indegree zero.

b) Now remove the node which is visited and also remove the edges from or to that node from other edges.

c) repeat the process.

Indegree is the number of edges that comeinto to the node.

Fractional and Discrete knapsack problem

here is the program for fractional and discrete knapsack problem.

// knapsack.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#include

void FractionalKnapsack();

void DiscreteKnapsack();

void RandomInit();

void RandomizedQuickSort(int i, int j);

int RandomPartition(int i, int j);

int Random(int i, int j);

int size;

int Weight[100];

int Profit[100];

float ProfitWeightRatio[100];

int NumItems;

int Permute[100],per=0;

int _tmain(int argc, _TCHAR* argv[])

{

char ch;

printf("Enter the size of the Knapsack\n");

scanf("%d",&size);

printf("Enter the number of items to be put into knapsack\n");

scanf("%d",&NumItems);

fflush(stdin);

printf("Enter the weight of each item\n");

for(int i=0;i

scanf("%d",&Weight[i]);

fflush(stdin);

printf("Enter the profits of each Item\n");

for(int i=0;i

scanf("%d",&Profit[i]);

fflush(stdin);

printf("Are you looking for Fractional Knapsack problem

....If so press character F\n");

printf("Are you looking for Discrete Knapsack problem

... If so press Character D\n");

scanf("%c",&ch);

if (ch == 'F' || ch == 'f')

FractionalKnapsack();

else if (ch == 'D' || ch == 'd')

DiscreteKnapsack();

else

{

printf("You have entered wrong

knapsack problem identifier\n");

exit(0);

}

fflush(stdin);

printf("Finished\n");

scanf("%c",&ch);

return 0;

}

void FractionalKnapsack()

{

//calculate profit weight ratio for each and every item.

for(int i=0;i

{

ProfitWeightRatio[i] = ((float) Profit[i])/Weight[i];

Permute[i] = i;

}

RandomInit();

//Sort the ProfitWeightRatio array and also

update the order of items in permute array,

Weight array,Profit array after the sor.

RandomizedQuickSort(0,NumItems-1);

//After sorting it is just that inserting all the elements

until knapsack becomes full.

//Note that as this is fractional knapsack problem a

fraction of last item is inserted.

printf("After sort here are the values of various arrays\n");

printf("Weight Array ");

for(int i=0;i

printf("%d ",Weight[i]);

printf("\nProfit Array ");

for(int i=0;i

printf("%d ",Profit[i]);

printf("\nProfitWeightRatio Array");

for(int i=0;i

printf("%f ",ProfitWeightRatio[i]);

printf("\nPermute Array ");

for(int i=0;i

printf("%d ",Permute[i]);

int room = size;

printf("Items used to fill the knapsack are\n");

float profit=0,fraction=0;

int k=0,Item=0;

while(room &&

k<>

{

Item = Permute[k];

if(room > Weight[Item])

{

room = room - Weight[Item];

profit = profit + Profit[Item];

printf("Item: %d ",Item);

}

else

{

fraction = (float) room/ Weight[Item];

profit = profit + fraction * Profit[Item];

printf("Fractional Item: %d\n",Item);

room=0;

}

k++;

}

}

void RandomInit()

{

time_t sec;

time(&sec);

srand( (unsigned int) sec);

}

void RandomizedQuickSort(int i,int j)

{

int l =0;

if(i

{

l = RandomPartition(i,j);

RandomizedQuickSort(i,l-1);

RandomizedQuickSort(l+1,j);

}

}

int RandomPartition(int i, int j)

{

int l_rand = 0;

float swap_ele = 0;

int swap_permut=0;

l_rand = Random(i,j);

//swap the first element and l_rand element

in the ProfitWeightRatio error.

swap_ele = ProfitWeightRatio[i];

swap_permut = Permute[i];

ProfitWeightRatio[i] = ProfitWeightRatio[l_rand];

Permute[i] = Permute[l_rand];

ProfitWeightRatio[l_rand] = swap_ele;

Permute[l_rand] = swap_permut;

float pivot = ProfitWeightRatio[i];

int l=i+1;

int m=j;

do

{

while(ProfitWeightRatio[l] >= pivot)

l++;

while(ProfitWeightRatio[m] <>

m--;

if(l

{

swap_ele = ProfitWeightRatio[l];

swap_permut = Permute[l];

ProfitWeightRatio[l] = ProfitWeightRatio[m];

Permute[l] = Permute[m];

ProfitWeightRatio[m] = swap_ele;

Permute[m] = swap_permut;

}

}while(l

ProfitWeightRatio[i] = ProfitWeightRatio[m];

swap_permut=Permute[m];

Permute[m] = Permute[i];

Permute[i] = swap_permut;

ProfitWeightRatio[m] = pivot;

return m;

}

int Random(int i, int j)

{

return ((rand() % (j-i+1)) + i);

}

int knapsack(int size, int index);

void DiscreteKnapsack()

{

int max_profit=0;

max_profit = knapsack(size,0);

printf("Discrete Knapsack maximum profit %d", max_profit);

printf("Elements covered in discrete knapsack maximum profit is \n");

//for(int i=0;i

//printf("%d ",Permute[i]);

printf("\n");

}

int knapsack(int size, int index)

{

int p=0,l=0;

if(index >= NumItems ||

size <= 0)

return 0;

//select first

p = knapsack(size,index+1);

if(size >= Weight[index])

l = Profit[index] + knapsack(size-Weight[index],index+1);

if (p >= l)

{

return p;

}

else

{

//Permute[per++] = index;

return l;

}

}