Microsoft Data Science INTERN | 2027 Summer | OA Questions

MSFT OA (Job 200041778): Balance Chemical Equation (SymPy) + Min Operations for Beautiful String

I got these two questions in my Microsoft online assessment. Posting the problems, my intuition, code, and the gotchas I noticed so we can discuss. If you solved either one differently, please share.

---

Q1: Balance a Chemical Equation Using SymPy

Problem

Write a Python program using SymPy that balances a chemical equation. An equation is balanced when the number of atoms of each element is the same on both sides. Given an unbalanced equation, return the list of coefficients of the balanced equation, in the order the compounds appear.

Input format:

• Reactants and products are separated by " - " (space, hyphen, space).
• Multiple reactants or products are separated by " + ".
• Each element starts with a capital letter.
• A number after an element is its count in the compound. No number means 1.
• Elements can repeat within a compound.
• No brackets in the input.

The coefficients must be integers and their sum must be minimal.

Function: balanceEquation(chemicalEquation: str) -> list[int]

Example 1

Input:  HCl + NaOH - H2O + NaCl
Output: [1, 1, 1, 1]

Element	Reactant	Product
H	2	2
Cl	1	1
Na	1	1
O	1	1

Example 2 (sample case)

Input:  NH4ClO4 + Al - Al2O3 + HCl + H2O + N2
Output: 6 10 5 6 9 3

Intuition

Give every compound an unknown coefficient. For each element, atoms on the reactant side must equal atoms on the product side. That is a homogeneous linear system:

A x = 0

• Each row is an element.
• Each column is a compound.
• Reactant columns hold positive atom counts, product columns hold negative atom counts.
• x is the vector of unknown coefficients.

Any nonzero vector in the nullspace of A balances the equation. SymPy does exact rational arithmetic, so there are no floating‑point rounding problems. To get integers, multiply the vector by the LCM of the denominators, then divide by the GCD to get the smallest integer ratio.

Code

import re
from sympy import Matrix, lcm
from functools import reduce
from math import gcd

def balanceEquation(s):
    a, b = s.split(" - ")
    n = len(a.split(" + "))
    c = a.split(" + ") + b.split(" + ")
    d, e = [], []

    for x in c:
        t = {}
        for k, v in re.findall(r'([A-Z][a-z]?)(\d*)', x):
            t[k] = t.get(k, 0) + int(v or 1)
        d.append(t)
        for k in t:
            if k not in e:
                e.append(k)

    m = Matrix([
        [(1 if i < n else -1) * t.get(k, 0) for i, t in enumerate(d)]
        for k in e
    ])

    v = m.nullspace()[0]
    z = lcm([x.q for x in v])
    r = [int(x * z) for x in v]

    if min(r) < 0:
        r = [-x for x in r]

    g = reduce(gcd, r)
    return [x // g for x in r]

Explanation

1. Split the equation into reactants and products on " - ", and remember how many reactants there are (n).
2. Parse each compound with the regex ([A-Z][a-z]?)(\d*). It captures an element symbol (one or two letters) and an optional count. A missing count means 1, and repeated elements are summed.
3. Collect elements in the order they are first seen. These become the matrix rows.
4. Build the matrix. Entry (element, compound) is the atom count, positive for reactants and negative for products.
5. Nullspace: m.nullspace()[0] gives a nonzero coefficient vector satisfying every balance equation.
6. Make integers. Multiply by the LCM of the denominators (x.q).
7. Normalize. Flip the signs if needed so everything is positive, then divide by the GCD.

Complexity

Let E be the number of distinct elements and C the number of compounds.

• Parsing and building the matrix: about O(E * C).
• Nullspace: depends on SymPy's exact linear algebra and is the expensive part, but the matrices here are tiny.
• Space: O(E * C).

Limitations

• I take only nullspace()[0], which assumes the nullspace is one‑dimensional. Some equations have several independent balancing solutions, and the first basis vector might not give all‑positive coefficients. A general solver would need to handle that explicitly. The tests I saw did not trigger it.
• No support for brackets, hydrates, charges, or isotopes. The problem says brackets won't appear.

---

Q2: Minimum Operations to Make a String Beautiful

Problem

A string is beautiful if no two adjacent characters are either the same or adjacent in the alphabet. For example, bcb is not beautiful because b and c are adjacent in the alphabet.

One operation lets you pick any index i and change s[i] to any lowercase English letter. Return the minimum number of operations needed to make the string beautiful.

Function: int getMinimumOperationCount(string s)

Example

Input:  bddje
Output: 1

dd is the only bad pair. Changing the second d to f gives bdfje:

• b, d: difference 2
• d, f: difference 2
• f, j: difference 4
• j, e: difference 5

Intuition

Two neighbors a and b are valid exactly when:

abs(a - b) > 1

The alphabet is linear, so a and z are not consecutive.

My first thought was greedy: scan left to right and fix any bad pair. That is not safe. Changing a character to satisfy its left neighbor can break it against its right neighbor, and there is no obvious "best" replacement without looking ahead. So instead I used DP and let it consider every letter at every position.

Approach: DP over the last letter

Let dp[c] be the minimum number of replacements for the prefix processed so far, given that its last character is letter c.

For each position i:

1. Try every letter cur from a to z as the character at i.
2. Try every previous letter prev.
3. Allow the transition only if abs(cur - prev) > 1.
4. Cost is 0 if s[i] == cur, otherwise 1.
5. next[cur] = min(next[cur], dp[prev] + cost).

The answer is the minimum over all 26 final letters.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int getMinimumOperationCount(string s) {
    const int ALPHABET = 26;
    const int INF = 1e9;

    vector<int> dp(ALPHABET), nextDp(ALPHABET);

    // First character
    for (int c = 0; c < ALPHABET; ++c) {
        dp[c] = (s[0] - 'a' == c) ? 0 : 1;
    }

    // Remaining characters
    for (int i = 1; i < (int)s.size(); ++i) {
        fill(nextDp.begin(), nextDp.end(), INF);

        for (int current = 0; current < ALPHABET; ++current) {
            int changeCost = (s[i] - 'a' == current) ? 0 : 1;

            for (int previous = 0; previous < ALPHABET; ++previous) {
                if (abs(current - previous) > 1) {
                    nextDp[current] = min(
                        nextDp[current],
                        dp[previous] + changeCost
                    );
                }
            }
        }

        dp.swap(nextDp);
    }

    return *min_element(dp.begin(), dp.end());
}

Why it's correct

Every valid final string ends in some letter, and its previous letter must satisfy the adjacency rule. The DP enumerates all such transitions and adds exactly the cost of keeping or replacing the current character, so it never discards a better valid solution. Taking the minimum over final letters gives the global optimum.

Complexity

Let n be the string length.

• Time: O(n * 26^2), which is O(n) since the alphabet is fixed.
• Space: O(26) = O(1), using two rolling arrays.

Edge cases

• Length 1: answer is 0.
• aa: equal neighbors, must change.
• ab or yx: consecutive letters, must change.
• ac: valid.
• az: valid, since a and z are not consecutive.

---

Discussion

• For Q1, how would you handle equations with a multi‑dimensional nullspace? I'd look for a positive integer combination of the basis vectors, but I didn't need it for the tests.
• For Q2, is there a cleaner greedy that works? I couldn't find one that handles both neighbors, so I went with DP.

Happy to hear other approaches.