Algorithms Q in Python- sort strings of chars in O(n)
So Im working on a problem that involves sorting a list of strings comprised of letters ordered from aaa to zzz. We were given a hint to encode the letters as a=01, b=02, etc. So my logic was using a dictionary where i encoded the keys and values. Then iterating through the list and then iterating through each character in the string in each list. I used get to encode each character to a number and then got it back to a list of integers encoded to the dictionary values. I sorted it by creating an empty list of the maximum length (zzz which is 262627 to account for 0) and then iterating over the list of encoded values and adding one to each value of the maximum length list. Then I iterated over the enumerated values of the max length list of 1’s with a nested while loop with the condition that for all values that do not equal zero, append the value of the index to a new list. So now I have the sorted values of the encoded strings but I cant think of a way of encoding those values back to thier keys without using an O(n^2) loop. I also cant help to think Im making this way harder than it should be. advice? TC: 90k
I don’t even understand the solution you are trying to explain. Could you do it a bit slower for a dumb fellow.
Basically convert letters to integers so “aaa” is 010101, “cab” is 030102 and something that is one letter like “k” is “110000”. It’s basically turning the letter into its place in the alphabet. The maximum value we were given is “zzz” which would convert to 262626. So Id create an empty string with length 262627 (that extra empty value is to account for the zero index) and create a loop for the numerically equivalent strings that adds a 1 to the empty string for that value. Then I create another loop that stores the index of the items in that list that have a one in it so now the items are sorted. Then I have take those values in that sorted list and then use my dictionary to convert them back to letters. So that let’s say “110101” converts back to “kaa”. It’s ridiculously shitty but I couldn’t think of a better way to sort a list of letters using O(n).
Maybe what you want to do is to create an array of booleans with M entries, corresponding to each possible encoded string. You don't need to encode that many positions, just 26*26*26. For each word in the input, calculate the index based on the characters (which is O(1)) and set the position in the array to true (which is O(1)). Iterate through the N strings (which is O(N)). Then iterate over the resulting array (which is O(N)) and output the strings calculated from the index (which is O(1)) for the positions that are true. The beauty of this type of question is that it's a useless skill, it only evaluates your capacity to memorize a solution. I never solved this problem before, but memorized what someone once told me. Never used this technique for anything practical in my whole professional life.
Wrong
What is wrong?
Bucket sort?
You need to clarify some things, like what’s the max length of the strings? If small, Radix sort should be the most efficient. Note that bucket sort is O(n) “on average”, and therefore performance is input dependent.
Heard of ASCII?
Yikes. I feel like an idiot now. That would make this a ton easier.