Custom Sort String
Updated
Problem statement
AWS is developing a language-processing helper that sorts strings using a custom alphabet.
You are given order, a string containing k distinct characters in increasing custom-alphabet order, and an array arr containing n strings. Every character used by a string in arr appears in order.
Compare two strings from left to right using the character ranks in order. At the first position where they differ, the string whose character has the smaller rank comes first. If one string is a prefix of the other, the shorter string comes first.
Return the strings in ascending order under this comparison.
Function
customSortString(order: String, arr: String[]) → String[]Examples
Example 1
order = "9AacB"arr = ["BBBBa", "BBBB9", "B9ca", "Aa999", "B9A", "B", "B9A"]return = ["Aa999", "B", "B9A", "B9A", "B9ca", "BBBB9", "BBBBa"]Using the ranks in order = "9AacB", the strings sort as ["Aa999", "B", "B9A", "B9A", "B9ca", "BBBB9", "BBBBa"].
Example 2
order = "yYaAbB1"arr = ["Yay", "yaY", "1yaB", "1yab", "b", "bay"]return = ["yaY", "Yay", "b", "bay", "1yab", "1yaB"]The custom order is y < Y < a < A < b < B < 1. Applying that order character by character gives ["yaY", "Yay", "b", "bay", "1yab", "1yaB"].
Example 3
order = "7BbAz"arr = ["Abb", "A7z", "z7AAAA", "BbbABB"]return = ["BbbABB", "A7z", "Abb", "z7AAAA"]
The first characters have ranks B < A < z. Between the two strings beginning with A, the second characters have ranks 7 < b. The result is ["BbbABB", "A7z", "Abb", "z7AAAA"].
Constraints
1 <= order.length <= 621 <= arr.length <= 100000- The total length of all strings in
arris at most1000000. - Every character in
arrappears inorder. - Characters in
orderare distinct and are digits or English letters.
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Count User Mentions in Chat MessagesRamp · OARamp interview questions
- Blood Type Inheritance: Possible Parent GenotypesAbridge · OAAbridge interview questions
- Count Repeated Request IDs (Data Science OA)McKinsey & Company · OAMcKinsey & Company interview questions
- Minimum Magic Stones After MergesElevenLabs · OAElevenLabs interview questions
- Flat JSON Value DifferencesChubb · OAChubb interview questions
- Items SortAkuna Capital · OAAkuna Capital interview questions
- Count Cross-Array Target-Sum PairsVisa · OAVisa interview questions
- Get Search ResultsJP Morgan Chase · OAJP Morgan Chase interview questions
- Lexicographic Word FrequenciesUpstart · OAUpstart interview questions
- Array Rank TransformTata Consultancy Services · OATata Consultancy Services interview questions