There is a list of strings and they ask if it is possible create a chain of string using all the strings in the given list.
A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. (this question is taken from careercup)
To give an example;
let’s say the given list is {aaszx, prtws, stuia} in this case the only posible chain is prtws–stuia–aaszx

At first sight the problem looks to be pretty easy, just put the first and last characters on two seperate hasmaps ;

 
List<String> stringList = ...
stringList.add ...
Map<Character, Integer> firstCharacterCountMap = ...;
for each string : str in the list
    increment firstCharacterCountMap(first character of str)
    decrement lastCharacterCountMap(last character of str)

in the pseudo code above the idea is finding the number of characters at start position and number of end characters at the end. after check if there final sum of the results is 0. A reasonable solution yet doesn’t provide the chain to be constructed.
the difficulty is that there might be some dead-ends. let say the list is {ab, bd, cb, bc} if we start with ab; ab->bd->? there is no solution even though there is one. (Btw the solution is; ab->bc->cb->bd). At this point one solution may come to mind is starting from a string whose first character doesn’t correspond to and end. Unfortunately this idea is not as good as it seems since there might all the first characters have a correspondence.

My solution is in O(n^2) 🙁 yet it works. Anyway topological sorting also has n^2 complexity.

I first create two separate hashmaps for both start and end characters. then I put the strings to these maps with corresponding characters. next I check for all possible combinations recursively;

You also can run the code from ideone

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: uerturk
 * Date: 08/10/13
 * Time: 17:04
 * To change this template use File | Settings | File Templates.
 */
class HasChain {

    Map<Character, List<String>> startsWithStringMap = new HashMap<Character, List<String>>();
    Map<Character, List<String>> endsWithStringMap = new HashMap<Character, List<String>>();

    private Character getFirstChar(String str) {
        return str.charAt(0);
    }

    private Character getLastChar(String str) {
        return str.charAt(str.length() - 1);
    }

    boolean hasChain(List<String> stringList) {
        // create relations between strings and their first 
        // and last characters using two hasmaps.  
        for (String str : stringList) {
            Character start = getFirstChar(str);
            Character end = getLastChar(str);
            List<String> startsWithList;
            List<String> endsWithList;

            if (startsWithStringMap.containsKey(start)) {
                startsWithList = startsWithStringMap.get(start);
            } else {
                startsWithList = new ArrayList<String>();
                startsWithStringMap.put(start, startsWithList);
            }

            if (endsWithStringMap.containsKey(end)) {
                endsWithList = endsWithStringMap.get(end);
            } else {
                endsWithList = new ArrayList<String>();
                endsWithStringMap.put(end, endsWithList);
            }
            startsWithList.add(str);
            endsWithList.add(str);
        }

        // this stack is the solution stack
        Stack<String> stringStack = new Stack<String>();
        for (String str : stringList) {
            if (hasChain(stringList.size(), str, stringStack)) {
                System.out.println(stringStack);

                return true;
            }
        }

        return false;
    }

    // recursively iterates through all possibilities
    private boolean hasChain(int size, String startString, Stack<String> stringStack) {
        if (size == stringStack.size()) return true; // if the stack is full of strings, we found it!
        Character last = getLastChar(startString);
        if (startsWithStringMap.containsKey(last)) {
            List<String> stringList = startsWithStringMap.get(last);
            for (int i = 0; i < stringList.size(); i++) {
                String candidate = stringList.remove(i--); // remove the candidate as it shouldn't be used in the next iterations
                stringStack.push(candidate); // as if it is the solution
                if (hasChain(size, candidate, stringStack)) {
                    return true; // no need to continue
                }
                stringStack.pop(); // candidate is not the solution
                stringList.add(++i, candidate); // put it back to the list, where it belongs
            }
        }

        return false;
    }

    public static void main(String[] args) {
        List<String> stringList = new ArrayList<String>();
        stringList.add("bd");
        stringList.add("fk");
        stringList.add("ab");
        stringList.add("kl");
        stringList.add("cf");
        stringList.add("ff");
        stringList.add("fa");
        stringList.add("ak");
        stringList.add("ka");
        stringList.add("lf");
        stringList.add("bc");

        System.out.println(new HasChain().hasChain(stringList)); // should return true as there is a solution

        stringList.remove("ka"); // we break the chain here

        System.out.println(new HasChain().hasChain(stringList));  // should return false as there is no solution after removing 'ka'

    }
}

hope that helped to someone 🙂