How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Parse chemical formula with multipliers

Quick Overview

Parse chemical formula with multipliers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a string representing a chemical formula, parse it and return the total count of each element. The formula may include element symbols (uppercase letter followed by lowercase letters), integers for counts, nested parentheses with multipliers, and multi-digit numbers. Return a canonical output by concatenating element names in lexicographic order followed by their counts (omit the count when it equals 1). For example, input "K4(ON(SO 3)2)3" should output "K4N3O14S6". Implement an algorithm that runs in O(n) time using a stack or equivalent and handles inputs up to length 1e5.

Quick Answer: Parse chemical formula with multipliers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a string `formula` representing a chemical formula, parse it and return the total count of each element as a canonical string. The formula consists of: - **Element symbols**: an uppercase letter optionally followed by lowercase letters (e.g. `H`, `Mg`, `Be`). - **Counts**: an optional integer immediately following an element or a closing parenthesis (e.g. `O2`, `(...)3`). An absent count means 1. Counts may be multi-digit. - **Groups**: balanced parentheses, which may be nested, optionally followed by a multiplier that scales every element inside the group. Return the result by concatenating each element name in **lexicographic (sorted) order**, followed by its total count. **Omit the count when it equals 1.** Example: `"K4(ON(SO3)2)3"` -> `"K4N3O21S6"`. Solve in O(n) time using a stack of counters, supporting inputs up to length 1e5.

Constraints

1 <= formula.length <= 1e5
formula consists of English letters, digits, '(' and ')'
formula is always a valid, balanced chemical formula
Element subscripts and group multipliers may be multi-digit

Examples

Input: ("K4(ON(SO3)2)3",)

Expected Output: "K4N3O21S6"

Explanation: SO3 -> S1O3; (SO3)2 -> S2O6; ON(SO3)2 -> N1O7S2; group *3 -> N3O21S6; plus K4 -> K4N3O21S6 (sorted K,N,O,S).

Input: ("H2O",)

Expected Output: "H2O"

Explanation: Two hydrogen, one oxygen; oxygen's count of 1 is omitted.

Hints

Maintain a stack of dictionaries; push a fresh counter on '(' and pop-and-merge on ')'.
When merging a popped group, read the trailing multiplier (default 1) and scale every element count before adding it to the parent counter.
An element symbol is one uppercase letter followed by zero or more lowercase letters; the optional digits that follow are its count (default 1).
At the end, sort the element keys lexicographically and append the count only when it is greater than 1.