Interview Question for Software Engineer at Google:

package com.google;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class MergeString {

    public static List<Character> merge(List<String> words){
            List<Character> list = new LinkedList<Character>();
            ArrayList<ArrayList<Character>> chWords = new ArrayList<ArrayList<Character>> ();
            for (String str : words){
                List<Character> chars = new ArrayList<Character>();
                for (char c : str.toCharArray()){
                    chars.add(c);
                }
                chWords.add((ArrayList<Character>) chars);
            }

            while (true){
                int loc = findMin (chWords);
                if (loc != -1 ){
                        list.add(chWords.get(loc).get(0));
                        List<Character> remove = chWords.get(loc);
                        remove.remove(0);
                        chWords.set(loc,(ArrayList<Character>) remove);
                 }
                else{
                    break;
                }

            }
            return list;
        }

        public static int findMin(ArrayList<ArrayList<Character>> words){
            int min = -1;
            boolean firstTime = true;
            for (int i=0; i<words.size(); ++i){
                if (words.get(i) != null && !words.get(i).isEmpty() && firstTime){
                    min = i;
                    firstTime = false;
                }

               else if (words.get(i) != null && !words.get(i).isEmpty() && words.get(i).get(0) < words.get(min).get(0)){
                        min = i;
                }

            }
            return min ;
        }

    public static void main(String[] args) {
        List<String> list = new LinkedList<String>();
        list.add("aelpp");
        list.add("aaabnn");
        list.add("act");
        List<Character> list2 = merge(list);
        for (Character c : list2){
            System.out.println(c);
        }
    }

}

1) Create a min/max heap and an empty result list
2) Pop the highest value from each chunk and store it in the heap along with the chunk index.
3) call findMin on the heap to get the node with the smallest key and it's chunk index
4) insert the key string in the empty result list
5) pop the next value from the chunk where the key string came from using the chunk index, insert it into the heap and repeat step 5. If there are no items left in the chunk just go to step 5.
When all chunks are exhausted, you are done.

6)