CareerCup

int main()
{
            char str[] = {'a','b','d','c','d','f','s','\0'}, *sortOrder = "dacg", ch; 
	int i=0, j=0, k=0, count[256]; 
	
	printf("\n %s", str);

             for(; i<256;i++)
	{
		count[i] = 0;
	}
	for(i=0; (ch = str[i])!= '\0'; i++)
		count[ch] +=1;
	for( i=0; (ch= sortOrder[i])!= '\0'; i++)
	{
		for(j=0; j < count[ch]; j++)
			str[k++] = ch;
		count[ch] = 0;
	}
	for(i=0; i<256; i++)
	{
		if( count[i] != 0 )
		{			
			for(j=0; j < count[i]; j++)
				str[k++] = i;
			count[i] = 0;
		}
	}
	str[k] = '\0';
	printf("\n %s", str);
	return 0;
}

Let sorting string`s length is n, order string`s length is m.

1st way: simple traversal the sorting string. We take 1st elemenet of order string ('d') and look for all entries this char in sorting string. Char found -> copy it to the end of resulting string -> remove it from sorting string. And to do to the rest of order string`s chars. End of sorting string just add to result string. Time: O(m*n), spce: O(n)

2nd. We arrange a priority to each char in order string, i.e. 'd' has 4, 'a' has 3, 'c' has 2, 'g' has 1 and rest of 22 chars (or more, if extra chars as space, comma, etc. are included) has 0. This takes O(m) time. Than we can sort the sorting string using counting sort by priorities (if we now exactly how many different chars can be there) - that takes O(n) or we can use some sorting which time complexity is O(nlogn).

Here's the solution. It does something weird if some characters are repeated in the order string, but behavior in this case wasn't specified...

(defn srt[string order]
  (let [order-set (into #{} order)
        [cc remainder]
          (reduce 
            (fn [[cc remainder] c]
              (if (order-set c)
                [(assoc cc c (inc (or (get cc c) 0))) remainder]
                [cc (conj remainder c)]))
            [{} []]
            string)]
    (apply str 
      (concat
        (apply concat (map (fn [key] (repeat (or (get cc key) 0) key)) order))
        remainder))))

we can do a simple modified version of count sort...
O(n+m)...n is length of input string and m is length of order string

Reorder(char* I, char* R)
{
       int Count[MAX_ASCII];
       memset(Count,0,MAX_ASCII);

       // Normal count sort
       for(int i=0;i<strlen(I);i++)
       {
            Count[I[i]]++;
       }
      
       k = 0;
       //Output according to order array first
       for(int i=0;i<strlen(R);i++)
       {
           while(Count[R[i]]-- > 0)
              I[k++] = R[i]
       }
       
       // Append all remaining characters
       for(int i=0;i<MAX_ASCII;i++)
       {
            while(Count[i]-- > 0)
                  I[k++] = i
       }

}

appreciate solution given by "v".

additional data structure required will be a hash map and the o/p string

create the hash map<char,int> for all the char in the order string and value as zero

then we linearly scan the input string if there is a hit we increment the value of that key if not then we append it to the output string

after scanning the input string we get the values for each key in the hashmap by reverse order by scanning the o/p string from back and depending on the value we copy that char that many times in front of the output string

time complexity O(n+m) where n is the size of input and m is the size of the output
space complexity o(m) for the hash map

<pre lang="" line="1" title="CodeMonkey30190" class="run-this">import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

/**
* @author JK
* Sort an input string according to the given order string.
* There might be characters in input string that are not present in the order string and vice-versa.
* The characters of input string that are not present in the order string should come
* at the end of the output string in any order. Write code...
* Example: Sort("abdcdfs","dacg");
*
*
*/
class G16StringSorting {

/**
* @param s1 - 1st string
* @param s2 - 2nd string
* @returns the sorted string
* Solution is a three main steps
* 1) builds a hash map for each letter with the importance (1st position = 0; second position = 1,,,, letter not in second importance = Integer.MAX_VALUE)
* 2) will implement a comparator based on the hash map build on step1
* 3) Sort the first string (Caharcter array) based on the comparator from step2
*/
public static String sortFirstStringBasedOnSecond(String s1, String s2){
if(s1== null || s2==null || s1.length()< 1 || s2.length() < 1) throw new IllegalArgumentException("Invaldi input Parameters");
// We assume that all the characters are in lower case and we have the English alphabet
final HashMap<Character, Integer> sortBy = new HashMap<Character, Integer>();
int v = s2.length();
for(int i=0; i< v; i++){
sortBy.put(s2.charAt(i), i);
}
for(char c='a'; c <='z'; c++){
if(!sortBy.containsKey(c)){
sortBy.put(c, Integer.MAX_VALUE);
}
}
Comparator<Character> comp= new Comparator<Character>(){

public int compare(Character o1, Character o2) {
return sortBy.get(o1)-sortBy.get(o2);
}

};
Character[] sc1 = new Character[s1.length()];
for (int i = 0; i < s1.length(); i++) {
sc1[i] = s1.charAt(i);
}
Arrays.sort(sc1, comp);
StringBuilder sb = new StringBuilder();
for (Character ch : sc1) {
sb.append(ch);
}
return sb.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
String s = sortFirstStringBasedOnSecond("abdcdfs", "dacg");
System.out.printf("Sorted string = %s", s);

}

}

</pre><pre title="CodeMonkey30190" input="yes">
</pre>

java working code. O(n+m). w/o max ascii

String Sort(String a, String b) {

		//count each letter
		char[] letters = new char[255];
		for (int i=0; i<a.length(); i++) {
			letters[a.charAt(i)]++;
		}
		StringBuffer sb = new StringBuffer();
		for (int i=0; i<b.length(); i++) {
			for (int j=0; j<letters[b.charAt(i)]; j++) {
				sb.append(b.charAt(i));
				letters[a.charAt(i)] = 0; //mark as we already took it
			}
		}
		//now append all unsorted letters
		for (int i=0; i<a.length(); i++) {
			if (letters[a.charAt(i)]!=0) {
				sb.append(a.charAt(i));
			}
		}
		return sb.toString();
	}

public static String sortBasedOnOrderedStr(String str, String order) {
		Map<Character, Integer> hash = new HashMap<Character, Integer>();
				
		for(Character c: str.toCharArray()) {
			if(hash.get(c) == null)
				hash.put(c, 1);
			else  {
				int count = hash.get(c);
				hash.put(c, count + 1);
			}
				
		}
		
		StringBuilder sortedString = new StringBuilder();		
		
		for(Character ch : order.toCharArray()) {
			if(hash.get(ch) != null) {				
				for(int i=0; i< hash.get(ch); i++) {
					sortedString.append(ch);
				}
				hash.remove(ch);
			}
		}
		
		for(Character ch : hash.keySet()) {
			sortedString.append(ch);
		}
		
		
		return sortedString.toString();
	}

this may be good approach:
1) assign each alphabet integers in increasing order.
2) scan the input string and assign them integers using above assignment (use some mapping DS like map<char,int>) and assign 0 to all those that are not in order string.
3) Do counting sort. complexity O(n). This works well here since the input string could be very long and we have integers with max range from 1-26 only to sort.

I think complexity of overall algorithm will be O(n) where n is number of characters in input string.