CareerCup

What anonimous said its true to a certain point, but this problem is much easier that the pointed one. Can be done in O(n) time and O(n) space, given a dictionary of words.
Algorthm:
1. Split the input string in two parts between every characters.
2. check if both sides are present in dictionary, if so you have two words

public class SplitStrings {
	public static List<String[]> splitStr(Set<String> dictionary, String str) {
		List<String[]> options = new ArrayList<String[]>();
		for (int i=1; i<str.length();++i) {
			if (dictionary.contains(str.substring(0,i)) &&
				dictionary.contains(str.substring(i))) {
				options.add(new String[] {str.substring(0,i),
					str.substring(i)});
			}
		}
		return options;
	}
}

Use a Trie, backtracking may be needed.

same as : careercup.com/question?id=10060840

2 complete solutions (both based on DP) have been posted there.

Checkout the solution at avi-programming-blog.blogspot.com/2011/08/programming-challenge-ii-adding-spaces.html

I think the interviewer wanted to know if you can do something similar to Rabin-Karp algorithm. Basically keep building the first word by concatenating characters and compute hash (remember in R-K algo. the hash computation does not depend on the length of string). Similarly compute hash of the last word simultaneously (ok the first time it will be O(n-1) = O(n) but that's one time cost). If both hashes are present in dictionary only then do actual comparison, otherwise keep shifting a character from front of second word to the end of first word and repeat. Even if both words are present you must use other heuristics such as frequency of words and/or frequency of words occurring together to sort the list of words found as suggestions.

Use to prefix tree to get the sorted list of candidate breaking positions.
Use to suffix tree to get the sorted list of candidate breaking positions.
Find the common elements between two sorted lists.
Total time is O(N).