CareerCup

I was asked this question at Amazon. Only difference was to solve this with existing Java APIs. With some difficulty I could solve. Nevertheless they did not hire me :(
I am making an assumptions here. There will not be any hash collisions i.e. hash buckets are large enough.

RandomMap will contain a List and a HashMap. List will contain every element that is inserted. So get random is easy from a list as said in above points.
HashMap can be used to retrieve elements with a get(key) and put(key,value). Problem - value duplication in list and HashMap. Instead value can be index of array element Then List.get(value) will give the real element.
What if there ARE DUPLICATES?? Now there will be hash collosions for sure. get will now have to iterate over the list of collisioned objects. Not O(1)!
So another redirection is used. Instead of the index value in the HashMap we will store another HashMap<Integer,Integer>. First Integer - a running count which is incremented with value addition. Second Integer - Array Index.

public class RandomMap<K, V> 
{
  private List<V> _entryList = new ArrayList<>();
  private Map<K, HashMap<Integer,Integer>> _entryMap = new HashMap<>();
  
  public int size()
  {
    return _entryList.size();
  }
  
  public V get(Object key)
  {
    HashMap<Integer, Integer> randomMap = _entryMap.get(key);
    return _entryList.get( randomMap.get(0) );
  }

  public void put(K key, V value)
  {
    _entryList.add(value);
    HashMap<Integer, Integer> randomMap = _entryMap.get(key);
    if(randomMap == null)
    {
      randomMap = new HashMap<>(); 
    }
    randomMap.put(randomMap.size(), _entryList.size() - 1);
  }

  public void remove(Object key)
  {
    HashMap<Integer, Integer> randomMap = _entryMap.get(key);
    Integer indexToBeRemoved = randomMap.get(0);
    
    int lastIndex = _entryList.size() - 1;
    _entryList.add(indexToBeRemoved, _entryList.get(lastIndex));
    _entryList.remove(lastIndex);
  }

  public V getRandom()
  {
    return _entryList.get(new Random().nextInt(_entryList.size()));
  }
}

This could be further improved if we use one more change. Why? I will leave it to your imagination :)

private Map<K, RandomMap<Integer,Integer>> _entryMap = new HashMap<>();

If I get the question right, the following would work.
1. Sort the characters in both the string O(n log n).
2. Use two pointers(strPtr1 and strPtr2) pointing to start of the string, in a loop of 1..N. Store the windows in an array. And later find the greatest from windows array. O(n)
If string1 char is > string2 char
if(window>0){windows[arr++] = window; window = 0 }; str2ptr++; continue;
If string1 char == string2 char window++
strPtr1++;str2ptr++; continue;
if string1 char < string2 char
if(window>0){windows[arr++] = window; window = 0 }; strPtr1++; continue;

n log n + n

Good point. Forgot to add, assume one word occurs only once.
There could be n number of words that could form a longer word.

Eg.
the
there
after
thereafterheran
reaf
he
ran

ans.
thereafterheran

Approach 2, bucket sort should be sufficient with O(n)(with a bit of space complexity), since k is much smaller to N. So entire solution becomes O(n).

You might have misinterpreted the question. There could be write happening, and when it does happen, nobody should be able to read.

Print left and right separately. The ones that doesn;'t have any children also contributo to boundary.

public static void main(String[] args) {
		printingBoundary = "left";
		System.out.println(root.data);
		print(root.left, "left");
		printingBoundary = "right";
		print(root.right, "right");
	}

	static void print(BinaryTreeNode root, String boundary) {
		
		if (root.left != null)
			print(root.left, "left");

		if (root.left == null && root.right == null)
			System.out.println(root.data);
		else if(boundary.equals(printingBoundary))
			System.out.println(root.data);

		if (root.right != null)
			print(root.right, "right");
	}

static ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
	public void readMethod()
	{
		lock.readLock().lock();
		//read something
		lock.writeLock().unlock();
	}

	public void writeMethod()
	{
		lock.writeLock().lock();
		//read something
		lock.writeLock().unlock();
	}

In Order traversal will do, with a slight twist.

public static void traversal(BinaryTreeNode root)
	{
		while(root.right != null && root.right.data > max )
		{
			//discard right nodes since they are greater than right anyways. 
			//and right is now greater than max. 
			root.right = root.right.left;
		}
		while(root.left != null && root.left.data < min)
		{
			//discard left nodes since they are smaller than left anyways. 
			//and left is now smaller than min. 
			root.left = root.left.right;
		}
		
		if(root.left != null)
			traversal(root.left);
		
		if(root.right != null)
			traversal(root.right);
	}

Maintain two chars, When a new char is encountered, move back the pointer as far as possible such that there are only two strings in the string. And then expand the string to the front as well.

public class LongestSubstring {

	public static void main(String[] args) {
		char[] str = "abbbbbbaddeeffff".toCharArray();
		char char1 = ' ';
		char char2 = ' ';
		
		//Maintain a buffer and a live string where operations are done. 
		StringBuffer longestString = new StringBuffer();
		StringBuffer longestStringBuffer = new StringBuffer();
		
		//iterate through the arr. 
		for(int index=0; index<str.length; index++)
		{
			char newChar = str[index];
			if(char1 == ' ' || newChar == char1)
			{
				char1 = newChar;
				longestString.append(char1);
				continue;
			}
			if(char2 == ' ' || newChar == char2)
			{
				char2 = newChar;
				longestString.append(char2);
				continue;
			}
			
			//Encountered a new char, say 'c'
			if(longestString.length() > longestStringBuffer.length())
				longestStringBuffer = longestString;
			longestString = new StringBuffer();
			
			//Note the prev Character and go back as far as possible so that the characters are only of type prev char, say 'b' 
			char prevChar = str[index-1];
			int j = 0;
			for( j = index-2; j>=0; j-- )
			{
				if(prevChar == str[j])
					continue; 
				break;
			}
			//Append to the longest string from the farthest possible point.  
			for(int k=++j; k<index; k++)
			{
				longestString.append(str[k]);
			}
			char1 = prevChar; 
			char2 = str[index];
			//Append the current char too. 
			longestString.append(str[index]);
		}
		//Just in case we found a long string in the end. 
		if(longestString.length() > longestStringBuffer.length())
			longestStringBuffer = longestString;
		System.out.println(longestStringBuffer);
	}

}

Here is an intelligent algo I have seen somewhere in the net.
As you navigate down the tree, narrow the min and max conditions based on current node. Left should be always less than current node. And right should be greater.

public static boolean isBinaryTree(BinaryTreeNode node, int min, int max)
	{
		boolean returnBool = false;
		
		if(node.data >= min || node.data <= max)
			returnBool = true;
		
		if(node.left != null)
			returnBool = returnBool && isBinaryTree(node.left, min, node.data - 1);
		
		if(node.right != null)
			returnBool = returnBool && isBinaryTree(node.right, node.data + 1, max);
		
		return returnBool; 
	}

showell I agree with you. With a slight modification in the code, I could achieve this. Basically doing recursion, but repeating for a negated value and a positive value

public class SumTarget {

	static int target_total = 12;
	static boolean[] used = { false, false, false, false, false, false, false, false};
	static boolean[] usedNegative = { false, false, false, false, false, false, false, false};
	static int arr[] = {-5, 1, 2, 3, 4, 6, 7, 8 };

	public static void main(String[] args) {
		for (int i = 0; i < arr.length; i++) {
			sumIt(i, target_total, true);
			sumIt(i, target_total, false);
		}
	}

	public static void sumIt(int index, int target, boolean sign) {
		//Mark Used
		used[index] = true;
		int current = 0;
		if(sign)
		{
			usedNegative[index] = true;
			current = -arr[index];
		}
		else
		{
			current = arr[index];
		}
		target = target - current;

		if (target == 0) {
			// We are at zero already
			for (int j = 0; j < used.length; j++) {
				if (used[j])
				{
					if(usedNegative[j])
					{
						System.out.print("-" + arr[j] + " , ");
					}
					else
					{
						System.out.print(arr[j] + " , ");
					}
				}
			}
			System.out.println();
			return;
		}
		for (int i = index + 1; i < arr.length; i++) {
			sumIt(i, target, true);
			sumIt(i, target, false);
		}
		
		usedNegative[index] = false;
		used[index] = false;
	}

}

Copying the idea above from zyfo2 on March 16, 2013, add the negative of the original array into a new array to look like this will solve the problem.

static int arr[] = {-8, -7, -6, -4, -3, -2, 1, 2, 3, 4, 6, 7, 8 };

I get it!! I am only adding up and not subtracting. Let me see whether I can modify the code.

Not sure I understood your concern correctly.
I assume the list the sorted in the first place. As long as the sum of negative and positive number == 0, it is going to print out correctly.
I put in the following in the above program

static boolean[] used = { false, false, false, false, false, false, false, false };
	static int arr[] = {-2, 1, 2, 3, 4, 6, 7, 8 };

,
It gives me
-2 , 1 , 2 , 3 , 8 ,
-2 , 1 , 2 , 4 , 7 ,
-2 , 1 , 3 , 4 , 6 ,
-2 , 1 , 6 , 7 ,
-2 , 2 , 4 , 8 ,
-2 , 3 , 4 , 7 ,
-2 , 6 , 8 ,
1 , 2 , 3 , 6 ,
1 , 3 , 8 ,
1 , 4 , 7 ,
2 , 3 , 7 ,
2 , 4 , 6 , 7 ,
4 , 8 ,
as output.

Here is a java version. Use and subtract the digit from the target and recursively call the
array for rest of items that adds upto target - digit.

public class SumTarget {

	static int target_total = 12;
	static boolean[] used = { false, false, false, false, false, false, false };
	static int arr[] = { 1, 2, 3, 4, 6, 7, 8 };

	public static void main(String[] args) {
		for (int i = 0; i < arr.length; i++) {
			sumIt(i, target_total);
		}
	}

	public static void sumIt(int index, int target) {
		
		//Mark Used
		used[index] = true;
		target = target - arr[index];

		if (target == 0) {
			// We are at zero already
			for (int j = 0; j < used.length; j++) {
				if (used[j])
					System.out.print(arr[j] + " , ");
			}
			System.out.println();
			return;
		}
		for (int i = index + 1; i < arr.length; i++) {
			sumIt(i, target);
		}
		used[index] = false;
	}
}