The "Verifying an Alien Dictionary" interview question presents a scenario where an alien language uses the same lowercase letters as English, but in a different alphabetical order. You are given a sequence of words and the order of the alien alphabet. You must determine if the words are sorted lexicographically according to this new order.
This "Verifying an Alien Dictionary" coding problem is extremely popular at companies like Meta, Uber, and Amazon. it tests your ability to handle custom sorting logic and string comparisons. It evaluates whether you can correctly implement the rules of lexicographical order (e.g., "apple" comes before "apply", and "app" comes before "apple").
The core pattern is the "Hash Table" combined with "String Comparison." First, you create a mapping (hash table or array) where each letter is assigned its index (rank) in the alien order. Then, you compare adjacent words in the list one by one. For each pair of words, you find the first character where they differ and check their relative ranks.
Order: "hlabc...", Words: ["hello", "habit"]
h:0, l:1, a:2, b:3, i:4, t:5...A common mistake is only comparing the first letters of each word. Another frequent error is not handling the case where one word is a prefix of the next (e.g., ["apple", "app"] is always invalid regardless of the order). Candidates also sometimes forget to break out of the inner loop as soon as the first differing character is found.
When solving the "Verifying an Alien Dictionary" coding problem, using an array of size 26 for the mapping is more efficient than a hash map. It’s also helpful to write a dedicated isSorted(word1, word2, orderMap) function to keep your main loop clean and readable.