CareerCup

Look similar to oj.leetcode.com/problems/subsets/

See also oj.leetcode.com/problems/validate-binary-search-tree/

My solution:

private int max = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
    	if (root == null) return true;
        boolean isLeftValid = isValidBST(root.left);
        if (!isLeftValid) return false;
        if (root.val <= max) return false;
        max = root.val;
        return isValidBST(root.right);
    }

Sort all words and compare - n*k*logk
Using hashing that always works will make the sort redundant - n*k (I don't know how to do a hash that always works)

public void anagramBuckets(List<String> input) {
	HashsMap<Integer, List<String>> map = new ...;
	for(String string : input) {
		int hash = string.hashCode();
		List<String> bucket = map.get(hash);
		if (bucket == null) {
			bucket = new ArrayList<...>();
			map.put(hash, bucket);
		}
		bucket.add(string);
	}
	// Contains the sorted string as key and the original as value
	HashMap<String, List<String>> sorted = new ...;
	for(List<String> hashedBucket : map.values) {
		if (hashBucket.size() == 1) {
			List<String> bucket = new ArrayList<String>();
			sorted.put(sortedString, bucket);
			bucket.add(string);
			continue;
		}
		for(String string : hashBucket) {
			String sortedString = sort(string);
			List<String> bucket = sorted.get(sortedString);
			if (bucket == null) {
				bucket = new ArrayList<String>();
				sorted.put(sortedString, bucket);
			}
			bucket.add(string);
		}
	}
	for(List<String> bucket : sorted.values) {
		print(bucket);
	}
}

It's not stated whether the words are in english only. They perhaps can be in Chinese as well. Thus, the sorting in O(n) might require a very big array.

I was thinking whether using hashing before sorting will result in N*K complexity instead of N*K*logK (if the hashing is good enough).
Thinking about it further, the sorting still needs to be done, so my assumption is wrong :(

Why check isHeadWithAsterisk(s2) - on s2?
I think there was a confusion here - s2 has only a-z chars.

Run over the chars in the regexp and try find matches in the string itself.

Pseudo code:

boolean match (String regexp, String s) {
  if (regexp.equals("") && s.eqauls("")) return true;
  if (regexp.equals("") && !s.eqauls("")) return false;
  if (regexp.size() > 1 && regexp.getChar(1) == '*') { // Astrix
    boolean match = match(regexp.substring(2), s);
    if (match) return true;
    boolean match = match(regexp.getChar(0), s);
    if (!match) return false;
    return match(regexp.substring(2), s.substring(1));
  }
  boolean match = match(regexp.getChar(0), s);
  if (!match) return false;
  return match(regexp.substring(1), s.substring(1))
}

boolean match(char regexpChar, String s) {
  if (s.equals("")) return false;
  char c = s.getChar(0);
  if (c == '.') return true;
  if (c == regexpChar) return true;
  return false;
}

Though the 'selection algorithm' wiki page states "There are O(n) (worst-case linear time) selection algorithms", it doesn't give any examples of such.
One example it provides is the 'quick select', which is O(n^2) (worse case) - bad.

I couldn't find those linear time selection algorithms :(

Use TreeMap to put the points, compared by their distance from origin. Then iterate over the first k.
Complexity: O(nlogn) - n because running over all the elements and logn because the depth of the tree logn.

This is the partition problem (wikipedia.org/wiki/Partition_(number_theory)).

Does the following help someone?
1111111 (n=1)
=======
111112 (n=2)
======
11113 (n=3)
=====
11122
1114 (n=4)
====
1123
115 (n=5)
===
1222
124
133
16 (n=6)
==
223
25
34
7 (n=7)

The number of lines is the number of possible partitions and the list of partitions for each n.
So the algorithm is recursive, computing the partitions for n-1, running over them and adding 1 to the left of the of each partition. In addition, we add all partitions that have incremental values starting with 2.
I'm stuck with calculation the incremental final part :(

BTW, my email is kilaka at gmail.com :)