Skip to content

Instantly share code, notes, and snippets.

@eugenp
Created March 5, 2012 11:30
Show Gist options
  • Save eugenp/1977943 to your computer and use it in GitHub Desktop.
Save eugenp/1977943 to your computer and use it in GitHub Desktop.
Interview Question:
package com.macys.rest.common;
import java.util.HashSet;
import java.util.Set;
/**
* - link: http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/ <br>
* Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible.
* For example, if the input string is "applepie" and dictionary contains a
* standard set of English words, then we would return the string "apple pie" as output.
* You don't need to implement the dictionary. Just assume access to a reasonable implementation.
*/
public class Q {
private static Set<String> dictionary = new HashSet<String>();
static {
dictionary.add("this");
dictionary.add("text");
dictionary.add("is");
dictionary.add("short");
dictionary.add("shorter");
}
//
public static void main(final String[] args) {
final String arg0 = "thistextisshorter"; //
System.out.println(sol1(arg0));
System.out.println(sol2(arg0));
System.out.println(sol3(arg0));
System.out.println(sol4(arg0));
}
//
/**
* - not fully working
*/
public static String sol1(final String input) {
StringBuilder result = new StringBuilder();
StringBuilder b = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
b.append(input.charAt(i));
if (dictionary.contains(b.toString())) {
result.append(b);
result.append(" ");
b = new StringBuilder();
}
}
return result.toString();
}
/**
* - note: not working
*/
public static String sol2(final String input) {
int len = input.length();
for (int i = 0; i < len; i++) {
String prefix = input.substring(0, i);
if (dictionary.contains(prefix)) {
String suffix = input.substring(i, len);
if (dictionary.contains(suffix)) {
return prefix + " " + suffix;
}
}
}
return null;
}
/**
* - note: recursive
*/
public static String sol3(final String input) {
if (dictionary.contains(input)) {
return input;
}
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dictionary.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = sol3(suffix);
if (segSuffix != null) {
return prefix + " " + segSuffix;
}
}
}
return null;
}
/**
* - note: recursive
*/
public static String sol4(final String input) {
if (dictionary.contains(input)) {
return input;
}
final int len = input.length();
for (int i = 1; i < len; i++) {
// System.out.println( "Outer; i=" + i );
final String prefix = input.substring(0, i);
if (dictionary.contains(prefix)) {
// System.out.println( "In" );
final String result = prefix + " " + sol4(input.substring(i, len));
// System.out.println( "Out" );
return result;
}
}
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment