Interview Question:

Q1.java

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;
  }

}