CareerCup

Java solution:

//You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
//Now we create a signature of this array by comparing every consecutive pair of elements. 
//If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". 
//The signature thus has a length of N-1. Now the question is given a signature, 
//compute the lexicographically smallest permutation of [1,2,....n].
import java.util.*;
public class SignatureBacktrack {

	/**
	 * @param args
	 */
	
	static Vector<Vector<Integer>> ansList;
	static Boolean finished;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int test[] = {1,2,3,4,5};
		Arrays.sort(test);
		finished = false;
		HashSet<Integer> set = new HashSet<Integer>();
		for(int i=0;i<test.length;i++) {
			set.add(test[i]);
		}
		
		ansList = new Vector<Vector<Integer>>();
		
		String signature = "DDDD";
		if(!(test == null || signature.length() != test.length-1))
		{
			for(int i=0;i<test.length;i++) {
				Vector<Integer> x = new Vector<Integer>();
				HashSet<Integer> setClone = (HashSet<Integer>) set.clone();
				
				setClone.remove(test[i]);
				x.add(test[i]);
				
				signMatch(x,1,setClone,signature);
			}
			for(Vector<Integer> a : ansList) {
				System.out.println(a);
			}
			//System.out.println(ansList.get(0));
			
		}
	}
	static void signMatch(Vector<Integer> vec, int pos, HashSet<Integer> s,String sign) {
		if(!finished) {
			if(s.isEmpty()) {
				ansList.add(vec);
				finished = true;
			} else {
				if((""+sign.charAt(pos-1)).compareToIgnoreCase("D") == 0) {
	
					for(Integer a : s) {
						Vector<Integer> vecClone = (Vector<Integer>) vec.clone();
						HashSet<Integer> setClone = (HashSet<Integer>) s.clone();					
						
						if(vec.get(pos-1) > a) {
							vecClone.add(a);
							setClone.remove(a);
							signMatch(vecClone,pos+1,setClone,sign);
						}
					}
				}else if((""+sign.charAt(pos-1)).compareToIgnoreCase("I") == 0) {
					for(Integer a : s) {
						Vector<Integer> vecClone = (Vector<Integer>) vec.clone();
						HashSet<Integer> setClone = (HashSet<Integer>) s.clone();
						
						if(vec.get(pos-1) < a) {
							vecClone.add(a);
							setClone.remove(a);
							signMatch(vecClone,pos+1,setClone,sign);
						}
					}
				}
			}
		}
	}
}

Im sorry. I found the solution on SO but i wasnt very clear on how to do. Here is izomorphius' solution to the problem:

int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));

int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
   if (greatest_value_so_far > a[i]) {
     greater_on_rigth[i] = greatest_index;
   } else {
     greatest_value_so_far = a[i];
     greatest_index = i;
   }
}

// Do the same on the left with smaller values


for (int i =0;i<n;++i) {
  if (greater_on_rigth[i] != -1 && smaller_on_left[i] != -1) {
    cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_rigth[i] << endl;
  }
}

Can you define with an example what right most node at maxDepth with a simple example?

You can do this in two iterations.
1. Iterate through the array once and make a note of the numbers which is lesser than the number on the right.
2. Iterate through the array again and make a note of the numbers which is greater than the number to its left.
Now the number (or numbers) are the numbers which are common to both these things.

Huffman coding is usually used when you need to transmit an alphabet (set of symbols, in this case the english alphabet) over a communication medium using binary numbers (usually) or a much smaller alphabet. Which is why i see doing huffman code as unnecessary, although its not wrong. And i was asked this question in a microsoft interview for the same position and they were looking for the same answer. :)

To compress string you can use something called run-length coding. This makes use of the redunduncies (like repetitions in string) and compresses it.
for example:
if you have aaaabbbcddeeeeffff
it can compressed as \4a\3bc\2d\4e\4f.
the backslash is used as an escape sequence to denote that its a compressing element. you escape backslash in the original text with another backslash just like how you would do in c/c++.
you can do this in n steps. its a straightforward algorithm

Stack stores instances and static allocated memory(like local variables, program instances during recursion). Heap is used to store objects and dynamically allocated memory. Generally the heap is much larger than stack.