CareerCup

Java solution with O(N) run time and O(1) space complexity.

package careercup;

public class MaxSubstring {
	public static String find(String input) {
		char[] str = input.toCharArray();
		boolean[] charsSoFar = new boolean[26];
		int startIndex = 0;
		int bestStartIndex = 0;
		int bestEndIndex = 0;

		for (int i=0; i < str.length; i++) {
			int charIndex = getCharIndex(str[i]);
			if (!charsSoFar[charIndex]) {
				// keep checking off characters as used
				charsSoFar[charIndex] = true;
			}
			else {
				// this character has already been used in the current substring
				// if current substring is bigger than the current best, update current best
				if (getLength(startIndex, i) > getLength(bestStartIndex, bestEndIndex)) {
					bestStartIndex = startIndex;
					bestEndIndex = i;
				}
				// now scan forwards removing characters from the substring
				//  until this character is free to be used again
				while(charsSoFar[charIndex]) {
					int startCharIndex = getCharIndex(str[startIndex]);
					charsSoFar[startCharIndex] = false;
					startIndex++;
				}
				// the character is now free, mark it as used since the new substring is now using it
				charsSoFar[charIndex] = true;
			}
		}
		return input.substring(bestStartIndex, bestEndIndex);
	}

	private static int getLength(int startIndex, int endIndex) {
		return endIndex - startIndex + 1;
	}

	private static int getCharIndex(char c) {
		return (int)(c - 'a');
	}
}

Node<Integer> temp - this is an extra pointer.

Surely the search space for this problem will always be exponential no matter what you do? There are 3^(N-1) combinations for applying the operators, even if you were only solving the problem for those that factorise to a single prime so F runs in exponential time not polynomial time?

I know I didn't realise use the domain restrictions to simplify the solution, but I can't really see how since there is no restriction on brackets (right?) for instance how can you parse some crazy complex brackets as tokens? Something like:
((4*(5-X+X*(4/5))+1)*6)*(7*(X/(6+1)))+5X=0

The actual code for this seems beyond the scope of an interview but the solution I've sketched out is:
1. Parse the input string into a tree structure with = at the root and each node either an operator (+-/*) or a value. The tree is structured with lower order operators higher in the tree. Take care to respect brackets when creating the tree.
2. Evaluate each side of the tree root. Each node evaluates to a composite value of x^2's, x's and a constant. Take care when multiplying two sub-nodes that have x^2 and x values. If you ever hit an x^3 value or higher order x, throw exception.
3. Subtract the right hand side values from the left hand side values to get something in the form ax^2 + bx + c = 0. Use the quadratic formulae to solve it.

Method 1:
The class that provides the GPS coordinates from the phone's sensor should be behind an interface and the concrete class not referenced directly by the code being tested. It should be passed into the constructor or created via dependency injection.
Create a test object that implements the interface and use dependency injection/pass it in to the code being tested. The test object returns pre-determined test coordinates allowing you to test the location services logic.

Method 2:
Instead of using an interface, you could use a mocking framework and do the same thing.

If we are taking N to mean the number of total elements, let's call the dimensions X so N = X*X.
This can be beaten by using a heap to store the current set of minimum elements per array (rather than searching for the minimum each step which costs X steps). Removing minimum from heap costs log X, inserting next value costs log X.
So total complexity is O(N log(sqrt(N))

Won't LinkedHashMap degrade to a linked list though? (all hashes are the same) Which will be O(N) for remove.

Is removeCache just supposed to remove the last recently used item or a specific item? Is the cache supposed to hold a finite number of elements? Is it OK to have a really poor space complexity, reducing the number of elements the cache can hold?

What do you mean by WAP?
Here's my attempt for printing the longest bitonic sequence, it has a small bug when the longest bitonic sequence is preceded by many equal integers.

public class Bitonic {
	private enum ParseState {
		Ascending,
		Descending
	}

	public static String PrintLongest(int[] input) {
		String result = "";
		String candidate = "";
		
		ParseState state = ParseState.Ascending;

		// we need at least 3 integers to satisfy bitonic criteria
		assert input.length >= 3;
		candidate += String.valueOf(input[0]);

		for (int i = 1; i < input.length; i++) {
			if ((input[i-1] <= input[i] && state == ParseState.Ascending) ||
				(input[i-1] >= input[i] && state == ParseState.Descending))
				candidate += "," + input[i];
			else if (input[i-1] > input[i] && state == ParseState.Ascending)
			{
				candidate += "," + input[i];
				state = ParseState.Descending;
			}
			else if (input[i-1] < input[i] && state == ParseState.Descending)
			{
				// is this candidate longer than the current best?
				if (candidate.length() > result.length())
					result = candidate;

				// now start building the next one
				candidate = input[i-1] + "," + input[i];
				state = ParseState.Ascending;
			}
		}

		// if we aren't currently descending then the current candidate doesn't work
		if (state == ParseState.Descending) {
			if (candidate.length() > result.length())
				result = candidate;
		}

		return result;
	}
}