The following problems are the ones I came across through web/friends/books etc. Their presence here is not an indication of their difficulty. I have put them here mostly because the solution to most of them appeared beautiful when they first struck me. If you are looking for job interview questions, then probably this is not the place for you. Better resources exist, such as this one, that will help you better. In case you find a better solution to any of the problems below (or one that is really beautiful), please write to me so that I can make this page more interesting.

Stacks, Queues, Lists

1. Implementing a Queue using Stacks

Since a stack has only one accessible end and a queue needs access to two ends, it is fairly obvious that you need two stacks to implement a queue. The trickier part is to ensure that each operation on the queue takes constant time per element on average (if not for every operations. Naming the two stacks E and D the following implementation of queue operations meet this criterion:

	enqueue(x)
		E.push(x)

	dequeue()
		if( D is empty )
			while (E is not empty)
				D.push(E.pop())
		if( D is empty )
			error queue is empty
		else return D.pop() 	
		

2. Supporting push, pop and find_min in constant time

I remember quite a few people saying "Can this really be done? I mean, if it can be, then I can push n elements, find the minimum repeatedly and thus sort the input in linear time". It is easy to see what is wrong with the argument. The solution again uses two stacks : S and M. Now the operations are implemented as follows :

	pop()
		M.pop()
		return S.pop()
	
	find_min()
		return M.top()

	push(x)
		S.push(x)
		M.push( min(x, M.top()) )	

3. Splitting a singly linked list in to two halves

Given the nature of linked lists, splitting is trivial. The real challenge is to know where to split. First the obvious way : go down the list while keeping count of the number of nodes and the reach the halfway location in another pass. A tricky way to do this in one pass uses two pointers slow and fast. The former moves forward one link at a time and the latte r two links at a time. A number of other problems can be solved efficiently using this trick. In languages like C, the implementation gets some more beauty with the use of references (actually pointers to pointers). Hence, the real code instead of pseudocode. When there are odd number of elements the code places an extra element on the first half.

	void split( struct node * src, struct node **first_half, struct node ** second_half)
	{
	        struct node ** slow_ref ,*fast;
	        slow_ref = &src;
	        fast = src;
	        while( fast && fast->next)
	        {
	                fast = fast->next->next;
	                slow_ref =  &((*slow_ref)->next);
	        }
	
	        //if fast is not NULL then fast->next is i.e odd number of elements
	        if(fast)
	                slow_ref = &(*slow_ref)->next;
	
	        *first_half = src;
	        *second_half = *slow_ref;
	        *slow_ref = NULL;
	} 

Addition : Removing a loop in a linked list

This is an addition to the previous one. I have seen the question related to detection of a loop in a linked list umpteen number of times (by loop what I mean is that the list looks something like this : --O ). Obviously, one would want to set the list right after the detection. The detection can be done using two pointers moving different speeds along the list. Coming to setting the loop right, the challenge is to find something the special node which has two pointers pointing to it. One way many people suggested to me is to count the number of nodes in the loop and then use two pointers with a fixed lag beween them. However, upon fiddling with some math I found that the counting part is unnecessary. Say the faster pointer used for detection was twice as fast as the slower one. Assume the loop has n nodes and the straiht chain m nodes and that the pointers met a location r nodes (call this Q) away from the node of interest (the node with two incoming pointers, call this P and starting node of the list S). The slower pointer must have traversed n + mi + r nodes (where i is an integer). so the faster one must have gone 2n + 2mi + 2r nodes. Now there must an integer j such that

	2n + 2mi + 2r = n + mj + r 	(rhs is simply an expression for the faster pointers traversal)
	=> n + r = mk			(k is another integer)

1. Checking if two trees are isomorphic

Tree isomorphism refers to structural equivalence of trees. A variant of the problem appeared in the 2002/03 Asian Regional ACM-ICPC. You can read the description here. Here I describe only the case of rooted trees. It is easy to see the recursive structure : The trees are isomorphic i) if the both the roots have same number of children and ii) there is a one to one correspondence between the children of the two roots such that each pair of subtrees rooted at the corresponding child nodes are isomorphic. An expensive recursive solution is fairly easy to code. However, the beauty of the solution is in the way it builds up sets of structurally equivalent subtrees in a bottom-up manner. The key is to store the structure of each tree rooted at a node in a canonical form so that comparison become easier. The algorithm below starts with the lowest level of the trees, makes sets of structurally equivalent trees at each level (using the information from the previously processed level). Each node keeps record of equivalence labels of its children along with its own label.

	are_isomorphic( node  a, node  b)

		store nodes (actually pointers to them) at level i (from both trees) in list L[i] //(hint : use a queue)
		for all nodes c in L
			c.label = 0
			c.child_labels = []
		
		Let h be the lowest level
		
		for i = h-1 down to 0

			//get the structure information from children
			for each node v in L[i+1]
				v.parent.child_labels.insert(v.label)
		
			//represent the structure of subtree at v in canonical form
			for each node v in L[i]
				sort(v.child_labels)

			//find equivalence classes at level i
			sort the list L[i] using lexical order of child_labels of the nodes in L[i]
			for all nodes in L[i] containing the same child_labels assign the same label //using label 0 for []

		if(a.label is same as b.label)
			return  true
		else
			return  false

1. Finding if two elements in an array sum to a given number

The straightforward method of testing all pairs of numbers is too slow for this. Besides, query with a new number again takes the same cost. Sorting the array ensures that each such query can be processed in linear time. The key is to use the ordering acheived by sorting. Assuming that the array has unique elements the following pseudocode describes a way to see if two numbers add to a given number x: (array indexing starts with 0 since I code mostly in such languages)

	is_sum_of_two(a, x)

		 i = 0;
		 j = length(a)-1;
		 while(i <= j)
			s = a[i] + a[j]
			if( s > x)
				j = j-1;
			else if (s < x)
				i = i+1;
			else
				return true;
		return false;

1. Generating lexial predecessor of a k-subset of n elements

I faced this thing while trying to select k-best features for task using brute force method. Even in this case, genrating the subsets in an order is quite useful. We can index the n elements using the numbers from 1 to n and store k-subset in its canonical form (i.e the elements are arranged in ascending or descending order of their index) in an array. Assuming ascending order the following pseudo code replaces a by its lexial predecessor (if there is one). Again, array indexing starts with 0.

	prev_subset(a, n, k)

        	if(n <= 1)
			"no predecessor"
	
       	 	i = k-1;
        	while(i > 0  and (a[i] == a[i-1] + 1))
                	i = i - 1;

	        if(a[i] == i+1)
        	        "no predecessor"

	       	a[i] = a[i]-1;
        	for(int j=i+1; j < k; ++j)
                	a[j] = n-k+j+1;