CareerCup

This sounds like a type of bucketsort.
Create a hashtable mapping characters in O to a number counting its occurences in t
append characters that don't exist in o to the beginning of the output string.
Finally go through and add the number of a character corresponding to o

public String reorder(String t, String o) {
	
	HashMap<String, Integer> H = new HashMap();

	for (int i = 0; i < o.length; i++) {

		h.put(o.charAt(i), 0);//put o chars in hashmnap
	}

	StringBuffer output = new StringBuffer();

	for (int i = 0; i < t.length; i++) {

		if (h.keyExists(t.charAt(i))) {

			h.put(t.charAt(i), h.get(t.charAt(i)) + 1);//increment the value here
		}

		else {

			output.append(t.charAt(i));
		}
	}


	int copyNum = 0;

	for (int i = 0; i < o.length; i++) {

		copyNum = h.get(o.charAt(i));//get number of times this character occured

		for (int j = 0; j < copyNum; j++) {

			output.append(o.charAt(i));
		}
	}

	returnt output.toString()

}

The solution to this question is a decorate-sort-undecorate algorithm. The characters of the string T are supposed to be decorated with values which are indices of those characters in the string O or value -1 if they are absent in string O. Since the order of the characters decorated with -1 is not important we are free to use any sorting algorithm (i.e. not necessarily a stable one).

def reorder(t, o):
    # Build a decorating hash table
    lut = {}
    for i in range(len(o)):
        lut[o[i]] = i
    # Reorder
    return ''.join(sorted(t, key=lambda character: lut[character] if lut.has_key(character) else -1))

print reorder('hello world', 'wrled')

public class Solution {

	public static void main(String[] args) {

		String t = "water";
		String o = "zealot";
		System.out.println(orderStringByRef(t, o));
	}

	public static String orderStringByRef(String t, String o) {

		StringBuilder sb = new StringBuilder();
		char c;
		int indexOfChar = -1;
		List<CharSeq> list = new ArrayList<>();

		for (int i = 0; i < t.length(); i++) {
			c = t.charAt(i);
			indexOfChar = o.indexOf(c);
			if (indexOfChar >= 0) {
				CharSeq cs = new CharSeq();
				cs.c = c;
				cs.i = indexOfChar;
				list.add(cs);
			} else {
				sb.append(c);
			}
		}

		list.sort(new CharSeqComparator());

		for (CharSeq cs : list) {
			sb.append(cs.c);
		}

		return sb.toString();
	}

}

class CharSeq {
	char c;
	int i;
}

class CharSeqComparator implements Comparator<CharSeq> {

	@Override
	public int compare(CharSeq a, CharSeq b) {
		if (a.i < b.i) {
			return -1;
		} else if (a.i == b.i) {
			return 0;
		} else if (a.i > b.i) {
			return 1;
		}
		return -1;
	}
}

I think best solution is using quicksort. I am reordering string in place in my solution

public class StringReorder {
    public static void main(String[] args) {

        char[] string = {'f', 'f', 'c', 'b', 'a', 'c'};
        String order = "abcf";
        reorderString(string, order);
        System.out.println("Reordered " + new String(string));
    }

    public static void reorderString(char[] string, String order) {
        quickSort(string, 0, string.length - 1, order);
    }

    public static void quickSort(char[] string, int startIdx, int endIdx, String order) {
        if(endIdx <= startIdx) return;
        System.out.println("StartIdx "+ startIdx + "EndIdx "+ endIdx);
        int randomIndex = (int) Math.floor(Math.random()*(endIdx - startIdx + 1));
        char pivot = string[randomIndex];
        int pivotOrder = order.indexOf(pivot);

        int lIdx = startIdx, rIdx = endIdx;
        while (lIdx < rIdx) {
            int lIdxOrder = order.indexOf(string[lIdx]);
            if(lIdxOrder > pivotOrder) {
                swap(string, lIdx, rIdx);
                rIdx--;
            } else if (lIdxOrder < pivotOrder){
                lIdx++;
            } else {
                lIdx++;
                rIdx--;
            }
        }
        quickSort(string, startIdx, rIdx -1, order);
        quickSort(string, lIdx+1, endIdx, order);
    }                          

    public static void swap(char[] string, int idx1, int idx2) {
        char temp = string[idx2];
        string[idx2] = string[idx1];
        string[idx1] = temp;
    }   
}

how about modifying the cmp function in standard sorting routines to achieve the outcome? Something like this --

class Precedences:
	def __init__(self, _prec):
		self.precedences = {}
		for idx, ch in enumerate(_prec):
			self.precedences[ch] = idx;
	def cmp(self, ch):
		if ch in self.precedences.keys():
			return self.precedences[ch]
		return len(self.precendeces)+1

if __name__ == '__main__':
	prec = "729354618"
	inp = "876570"
	precendeces = Precedences(prec)
	out = sorted(inp, key=precedences.cmp)
	print(prec)
	print(inp)
	print(out)

how about modifying the cmp function in standard sorting routines to achieve the outcome? Something like this --

class Precedences:
	def __init__(self, _prec):
		self.precedences = {}
		for idx, ch in enumerate(_prec):
			self.precedences[ch] = idx;
	def cmp(self, ch):
		if ch in self.precedences.keys():
			return self.precedences[ch]
		return len(self.precendeces)+1

if __name__ == '__main__':
	prec = "729354618"
	inp = "876570"
	precendeces = Precedences(prec)
	out = sorted(inp, key=precedences.cmp)
	print(prec)
	print(inp)
	print(out)

Good Question, here is my answer.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class CustomSorter {

	public static String sortString(String input, String alphabetSource) {
		
		Map<Character, Integer> alphabetMap = new HashMap<Character, Integer>();
		Map<Integer, Character> alphabetMapRev = new HashMap<Integer, Character>();
		
		char[] alphabetSourceChars = alphabetSource.toCharArray();
		
		for (int i = 0; i < alphabetSourceChars.length; ++i) {
			alphabetMap.put(alphabetSourceChars[i], i);
			alphabetMapRev.put(i, alphabetSourceChars[i]);
		}
		
		char[] inputChars = input.toCharArray();
		List<Integer> inputCharIndexs = new ArrayList<Integer>();
		int missingIndex = -1;
		
		for (int i = 0; i < inputChars.length; ++i) {
			Integer charIndex = alphabetMap.get(inputChars[i]);
			
			if (charIndex == null) {
				inputCharIndexs.add(missingIndex);
				alphabetMap.put(inputChars[i], missingIndex);
				alphabetMapRev.put(missingIndex, inputChars[i]);
				--missingIndex;
			} else {
				inputCharIndexs.add(charIndex);
			}
		}
		
		Collections.sort(inputCharIndexs);
		String sortedString = "";
		
		for (Integer index : inputCharIndexs) {
			sortedString += alphabetMapRev.get(index) + "";
		}
		
		return sortedString;
	}
	
	
	public static void main(String[] args) {
		System.out.println(sortString("ababcdddaab", "dcba"));
		System.out.println(sortString("ababcdzxxzddaab", "dcba"));		
	}
}