The first medium level question in my HackerRank journey! And yes, it was pretty hard for me. But the logic was easy to think of. Just hard to implement.
This was a higher level version of Jim and the Orders (whose solution is available here: https://teamresurgence.blogspot.com/2020/05/new-concept-jim-and-orders.html).
Here too, the Hashmap came in handy. Ultimately we have to sort the strings by their keys. But here we have to set it up to make the sorting "stable" (read the question). So here is what I came up with:
1. Accept the string, and it's key. Search for the key in an array called "takenKeys", which stores all the unique keys so far. If the key is found (meaning it is a duplicate), we will modify it to ensure stable sorting. Here they have put loophole of replacing the first half of strings by '-'. While accepting the strings itself, check if the the index of the loop which is accepting the strings is smaller than floor(n / 2) and simply append '-' instead of the accepted string in that case. A literal loophole!
2. This "modification" is simple. For each unique key, I have a "factor" (all these factors for each key are stored in a different array) The factor for each key is initialized to 0.1. Whenever a duplicate key is detected, say 4, I add the factor to it. (4 -> 4.1) and then factor = factor + factor/10000. Why 10000? I actually tried, 2, 10, 100, 1000, 10000. 10000 managed to pass all the testcases. This happens because lower values can "overflow". Meaning the sums of factors can add up to a value larger than 1. If 4 becomes 5 or more, instead of 4 < x < 5, then our sorting will mess up.
So if our keys were originally like this:
1, 3, 0, 1, 0, 1
they now become (if factor = factor + factor / 10, for simplicity):
1, 3, 0, 1.1, 0.1, 1.11
After sorting:
0, 0.1, 1, 1.1, 1.11, 3
Now it should be clear why the sorting is stable.
3. Now send this dictionary, with keys being the modified keys and the values being associated strings. Sort the dictionary by keys (unlike Jim, where we sorted by values). And now, print the values!
This was a higher level version of Jim and the Orders (whose solution is available here: https://teamresurgence.blogspot.com/2020/05/new-concept-jim-and-orders.html).
Here too, the Hashmap came in handy. Ultimately we have to sort the strings by their keys. But here we have to set it up to make the sorting "stable" (read the question). So here is what I came up with:
1. Accept the string, and it's key. Search for the key in an array called "takenKeys", which stores all the unique keys so far. If the key is found (meaning it is a duplicate), we will modify it to ensure stable sorting. Here they have put loophole of replacing the first half of strings by '-'. While accepting the strings itself, check if the the index of the loop which is accepting the strings is smaller than floor(n / 2) and simply append '-' instead of the accepted string in that case. A literal loophole!
2. This "modification" is simple. For each unique key, I have a "factor" (all these factors for each key are stored in a different array) The factor for each key is initialized to 0.1. Whenever a duplicate key is detected, say 4, I add the factor to it. (4 -> 4.1) and then factor = factor + factor/10000. Why 10000? I actually tried, 2, 10, 100, 1000, 10000. 10000 managed to pass all the testcases. This happens because lower values can "overflow". Meaning the sums of factors can add up to a value larger than 1. If 4 becomes 5 or more, instead of 4 < x < 5, then our sorting will mess up.
So if our keys were originally like this:
1, 3, 0, 1, 0, 1
they now become (if factor = factor + factor / 10, for simplicity):
1, 3, 0, 1.1, 0.1, 1.11
After sorting:
0, 0.1, 1, 1.1, 1.11, 3
Now it should be clear why the sorting is stable.
3. Now send this dictionary, with keys being the modified keys and the values being associated strings. Sort the dictionary by keys (unlike Jim, where we sorted by values). And now, print the values!
No comments:
Post a Comment