Obscure Word Sorting on Whiteboard | Dataford Interview Questions

Oscar Health member search uses a specialized ordering for labels displayed in search results. Given a list of lowercase words and a custom alphabet, sort the words lexicographically, but rotate the alphabet by one position for every character depth.

At depth d, characters are ordered as alphabet[d:] + alphabet[:d], where d is zero-based. A word that is a prefix of another word comes first. Duplicate words must remain duplicated, and their input order must be preserved.

Return the sorted list. Design the algorithm to avoid comparing every pair of words directly.

Formal Specification

Implement sort_rotated_words(words, alphabet).

words is a list of strings containing only characters from alphabet.
alphabet is a permutation of between 2 and 26 distinct lowercase letters.
Return a new list containing all words in the required order.

Constraints

1 <= len(words) <= 200,000
0 <= len(words[i]) <= 1,000
The total number of characters across all words is at most 1,000,000
2 <= len(alphabet) <= 26
alphabet contains distinct lowercase letters
Every word character appears in alphabet

Function Signature

def sort_rotated_words(words, alphabet):

Your question is Obscure Word Sorting on Whiteboard. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem