← Meta Interview Insights

Meta·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026

Summary

Meta software engineer screen covering a custom alphabet sorting problem with a follow-up that flipped the whole thing around. Two parts to one problem, which felt manageable until the second part hit.

Questions Asked (2)

Q1

Given a custom alphabet ordering and a list of strings, determine whether the strings are sorted in nondecreasing lexicographic order according to that alphabet.

Algorithms & Data Structures
Author's notes

Not too bad once you map each character to its position index and compare adjacent words character by character.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and edge cases, then propose a solution that compares adjacent strings using the custom alphabet order. Discuss the time complexity and potential optimizations, and be prepared to code the comparison logic.

Pro tip: Mention that you can precompute a rank map for O(1) character comparisons, and handle the tricky case where one string is a prefix of another (shorter string should come first).

1. Clarify the problem

Confirm the definition of nondecreasing lexicographic order with the custom alphabet, and ask about edge cases like empty strings, duplicate strings, and characters not in the alphabet.

2. Design the comparison function

Create a function that compares two strings character by character using the custom order, returning -1, 0, or 1. Use a hash map to store the rank of each character for O(1) lookups.

3. Check adjacent strings

Iterate through the list and compare each pair of adjacent strings using the comparison function. If any pair is out of order, return false; otherwise, return true.

4. Analyze complexity

Explain that the time complexity is O(N * L) where N is the number of strings and L is the average length, and space complexity is O(1) extra aside from the rank map.

5. Test and optimize

Walk through test cases including edge cases, and discuss potential optimizations like early termination or parallel comparison if needed.

Key Points to Mention

  • Custom alphabet order requires a rank mapping for O(1) character comparisons.
  • Lexicographic comparison: compare character by character until a difference is found.
  • Handle the case where one string is a prefix of another: the shorter string is considered smaller.
  • Time complexity: O(N * L) where N is number of strings and L is max length.
  • Space complexity: O(1) extra space if rank map is considered input, otherwise O(1) for alphabet size.
  • Edge cases: empty list, single string, empty strings, duplicate strings, characters not in alphabet.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Given a list of strings already sorted under some unknown custom alphabet, infer a valid alphabet ordering consistent with that list. Return any one valid ordering, or indicate it's impossible if none exists.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This is basically topological sort and I knew that, but I fumbled the graph construction phase more than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a directed graph where each character is a node and edges represent ordering constraints derived from adjacent words. Then perform a topological sort to find a valid alphabet order, detecting cycles to determine impossibility. Handle edge cases like invalid prefixes and duplicate words.

Pro tip: Emphasize that the graph approach is optimal (O(N) time) and discuss how to handle edge cases like when a shorter word appears after a longer word with the same prefix, which immediately makes the ordering impossible.

1. Extract ordering constraints

Iterate through adjacent word pairs and find the first differing character to create a directed edge from the earlier character to the later one. If no differing character exists and the first word is longer, return impossible.

2. Build the graph

Represent the graph using an adjacency list and track in-degrees for each character. Include all unique characters from the list as nodes.

3. Topological sort

Use Kahn's algorithm or DFS to generate a topological ordering. If the ordering doesn't include all characters, a cycle exists, so return impossible.

4. Return the ordering

Output the topological order as a string. If multiple valid orders exist, any one is acceptable.

Key Points to Mention

  • Graph representation: nodes are characters, edges are ordering constraints from adjacent words.
  • Topological sort algorithms: Kahn's (BFS) or DFS, with cycle detection.
  • Edge case: invalid prefix (e.g., ['abc', 'ab']) immediately returns impossible.
  • Time and space complexity: O(N + V + E) where N is total characters, V is unique characters, E is edges.
  • Handling duplicate words: they don't add constraints, but if a word repeats, it's fine.
  • Multiple valid orderings: any topological order is acceptable; no need to find all.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.