Sorting a string using another sorting order string?

Here's a nice easy to understand algorithm that has decent algorithmic complexity.

Here's a nice easy to understand algorithm that has decent algorithmic complexity. For each character in the sort order string scan string to be sorted, starting at first non-ordered character (you can keep track of this character with an index or pointer) when you find an occurrence of the specified character, swap it with the first non-ordered character increment the index for the first non-ordered character This is O(n*m), where n is the length of the string to be sorted and m is the length of the sort order string. We're able to beat the lower bound on comparison based sorting because this algorithm doesn't really use comparisons.

Like Counting Sort it relies on the fact that you have a predefined finite external ordering set. Here's some psuedocode: int head = 0; foreach(char c in sortOrder) { for(int I = head; I.

In Python, you can just create an index and use that in a comparison expression: order = 'dfbcae' input = 'abcdeeabc' index = dict( (y,x) for (x,y) in enumerate(order) ) output = sorted(input, cmp=lambda x,y: indexx - indexy) print 'input=',''. Join(input) print 'output=',''. Join(output) gives this output: input= abcdeeabc output= dbbccaaee.

Use binary search to find all the "split points" between different letters, then use the length of each segment directly. This will be asymptotically faster then naive counting sort, but will be harder to implement: Use an array of size 26*2 to store the begin and end of each letter; Inspect the middle element, see if it is different from the element left to it. If so, then this is the begin for the middle element and end for the element before it; Throw away the segment with identical begin and end (if there are any), recursively apply this algorithm.

Since there are at most 25 "split"s, you won't have to do the search for more than 25 segemnts, and for each segment it is O(logn). Since this is constant * O(logn), the algorithm is O(nlogn). And of course, just use counting sort will be easier to implement: Use an array of size 26 to record the number of different letters; Scan the input string; Output the string in the given sorting order.

This is O(n), n being the length of the string.

Interview questions are generally about thought process and don't usually care too much about language features, but I couldn't resist posting a VB. Net 4.0 version anyway. "Efficient" can mean two different things.

The first is "what's the fastest way to make a computer execute a task" and the second is "what's the fastest that we can get a task done". They might sound the same but the first can mean micro-optimizations like int vs short, running timers to compare execution times and spending a week tweaking every millisecond out of an algorithm. The second definition is about how much human time would it take to create the code that does the task (hopefully in a reasonable amount of time).

If code A runs 20 times faster than code B but code B took 1/20th of the time to write, depending on the granularity of the timer (1ms vs 20ms, 1 week vs 20 weeks), each version could be considered "efficient". Dim input = "abcdeeabc" Dim sort = "dfbcae" Dim SortChars = sort.ToList() Dim output = New String((From c In input.ToList() Select c Order By SortChars. IndexOf(c)).ToArray()) Trace.

WriteLine(output).

The Counting Sort option is pretty cool, and fast when the string to be sorted is long compared to the sort order string. Create an array where each index corresponds to a letter in the alphabet, this is the count array for each letter in the sort target, increment the index in the count array which corresponds to that letter for each letter in the sort order string add that letter to the end of the output string a number of times equal to it's count in the count array Algorithmic complexity is O(n) where n is the length of the string to be sorted. As the Wikipedia article explains we're able to beat the lower bound on standard comparison based sorting because this isn't a comparison based sort.

Here's some pseudocode. Char26 countArray; foreach(char c in sortTarget) { countArrayc - 'a'++; } int head = 0; foreach(char c in sortOrder) { while(countArrayc - 'a' > 0) { sortTargethead = c; head++; countArrayc - 'a'--; } } Note: this implementation requires that both strings contain only lowercase characters.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.