Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Meta SWE coding round with a formula parsing problem. The question looks like a string manipulation task but the nested parentheses make it way more involved than it first appears.

Questions Asked (1)

Given a chemical formula string like 'H2O', 'Mg(OH)2', or 'K4(ON(SO3)2)2', write a function that parses it and returns the count of each atom in lexicographical order.

Algorithms & Data Structures

Author's notes

The basic cases are fine but the nested parentheses are where things get messy.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to handle nested parentheses, parsing the formula from left to right. When encountering an uppercase letter, start a new element; when encountering a digit, multiply the count; when encountering '(', push the current counts onto the stack; when encountering ')', pop and merge with the multiplier after the parenthesis. Finally, sort the element counts lexicographically and return them as a string.

Pro tip: Clarify with the interviewer whether the output should be a string like 'H2O' or a map, and discuss edge cases like nested parentheses and multi-digit counts. Also, mention that you'll handle the parsing in a single pass with O(n) time and O(n) space.

1. Understand the problem and clarify requirements

Ask about input constraints (e.g., valid formula, max length), output format (string vs. map), and whether elements are case-sensitive. Confirm that counts should be in lexicographical order.

2. Design the parsing strategy

Propose using a stack to manage nested parentheses. Explain that you'll parse the string character by character, maintaining a current element and count, and use the stack to handle groups.

3. Implement the parser

Write code that iterates through the string: for uppercase letters, start a new element; for lowercase letters, complete the element name; for digits, parse the full number; for '(', push current counts; for ')', pop and merge with the multiplier after the parenthesis.

4. Handle edge cases and test

Test with simple formulas (H2O), nested parentheses (K4(ON(SO3)2)2), and multi-digit counts (C12H22O11). Verify that the stack correctly manages nested groups and that counts are multiplied appropriately.

5. Format and return the result

Sort the elements lexicographically, then build the output string by concatenating each element with its count (omitting count if it's 1). Return the result.

Key Points to Mention

Use a stack to handle nested parentheses and maintain counts for each group.
Parse element names by recognizing uppercase letters followed by optional lowercase letters.
Parse multi-digit numbers correctly (e.g., '12' in C12H22O11).
When encountering ')', multiply the counts inside the parentheses by the number following it.
Sort the final element counts lexicographically before formatting the output.
Time complexity is O(n) where n is the length of the formula, and space complexity is O(n) for the stack and output.

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