Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Meta SWE coding round, one question on custom string sorting. Pretty standard stuff but the edge cases can sneak up on you if you're not careful.

Questions Asked (1)

Given a string s and a string order that defines a custom character ordering, rearrange the characters of s to match the relative order defined by order. Characters not present in order can go anywhere. Return the result.

Algorithms & Data Structures

Author's notes

My first instinct was to just sort with a custom comparator keyed on the index of each character in order.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that characters not in order can be placed anywhere, so we can append them at the end. Use a frequency map to count characters in s, then iterate through order to build the result by repeating each character according to its count. Finally, append any remaining characters not in order.

Pro tip: Mention that this approach is O(n + m) time and O(1) space (since alphabet size is constant), and that it avoids sorting which would be O(n log n). This shows you consider efficiency and scalability.

1. Clarify constraints and edge cases

Ask about the character set (e.g., ASCII, Unicode), whether order contains duplicates, and if s can be empty. Confirm that characters not in order can be placed anywhere.

2. Count frequencies

Create a hash map or array to count the occurrences of each character in s. This allows O(1) lookup when building the result.

3. Build result in order

Iterate through each character in order. If it exists in the frequency map, append it to the result the number of times equal to its count, then remove it from the map.

4. Append remaining characters

After processing order, iterate over the remaining characters in the frequency map and append them to the result. The order among them doesn't matter.

5. Analyze complexity and test

State time complexity O(n + m) where n is length of s and m is length of order, and space O(k) where k is unique characters. Walk through an example to verify.

Key Points to Mention

Use a frequency map to count characters in s for O(1) lookups.
Iterate through order to place characters in the correct relative order.
Append characters not in order at the end (or anywhere) as they have no constraints.
Time complexity O(n + m) and space O(k) where k is unique characters, which is optimal.
Avoid sorting s with a custom comparator because it would be O(n log n) and unnecessary.
Handle edge cases: empty s, empty order, characters in order not present in s, and duplicate characters in order.

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