Solving Amazon's 2020 Most Asked Interview Question

? Join the community Discord: https://discord.gg/aVWsAaaCtT
? Support me on Patreon: https://www.patreon.com/michaelmuinos
?Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos
?Follow me on Github: https://github.com/MichaelMuinos

Check out my interview prep platform for learning the patterns!
? Interview Prep Platform: https://algoswithmichael.com

Amazon's most asked coding question for 2020 according to the LeetCode platform was "Reorder Data in Log Files". This problem is a string based problem which in just the past 6 months has been asked at Amazon over 330 times.

For this problem, we must sort log strings based on a variety of rules. There are two types of log strings: letter logs and digit logs. Letter logs contain a unique id separated with a space to the rest of the log portion. The log portion contains only lowercase letters; however, a digit log contains only digits. The rules we must implement our comparator class by are as follows:
letter logs always come before digit logs, letter logs are sorted lexicographically, if letter logs are equal we must sort by the id lexicographically, and digit logs should maintain their order.

The time complexity for our algorithm is big oh O(N*log(N)) where N is the number of elements we have in our array. Under the hood, the array sort uses a dual pivot quick sort algorithm which is due to the use of sorting primitives. If we were not sorting primitives, the sort function would use TimSort. The space complexity is big oh O(log(N)) since quick sort must utilize recursive calls to apply sorting.

----------------------------------------------------
LAKEY INSPIRED - Blue Boi
https://soundcloud.com/lakeyinspired
https://www.youtube.com/channel/UCOmy8wuTpC95lefU5d1dt2Q