Math Interview Problems for Embedded Engineers

Key Insight: Sparse vectors are mostly zeros, so storing only non-zero entries in a hash map and iterating through the sparser map skips all zero multiplications entirely.

Thought Process:

1. Brute force: iterate through all n elements, multiply pairwise, sum — O(n) regardless of sparsity.
2. Store only non-zero entries as (index, value) pairs — reduces storage from O(n) to O(k) where k is the number of non-zero entries.
3. For the dot product, iterate through the smaller map and check if each index exists in the other — O(min(k1, k2)) with O(1) hash lookups.
4. Optimization: always iterate through the sparser vector to minimize the number of lookups.

Approach: Store only non-zero entries in a hash map as (index -> value) pairs. For the dot product, iterate through the sparser map and check if each index exists in the other. This skips all zero entries entirely, making it efficient for vectors with thousands of elements but only a few non-zero values.

class SparseVector {
public:
    unordered_map<int, int> umap;

    SparseVector(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0)
                umap[i] = nums[i];
        }
    }

    int dotProduct(SparseVector& vec) {
        int sum = 0;

        if (vec.umap.size() < this->umap.size()) {
            for (auto it : vec.umap) {
                if (umap.find(it.first) != umap.end())
                    sum += umap[it.first] * it.second;
            }
        } else {
            for (auto it : umap) {
                if (vec.umap.find(it.first) != vec.umap.end())
                    sum += vec.umap[it.first] * it.second;
            }
        }

        return sum;
    }
};

Time Complexity: O(min(k1, k2)) where k1 and k2 are the number of non-zero entries in each vector — we iterate through the sparser map and do O(1) hash lookups in the other.

Space Complexity: O(k1 + k2) — each vector stores only its non-zero entries in a hash map, rather than the full n-element array.

Embedded relevance: Sparse representations are used in embedded ML inference (sparse weight matrices), sensor fusion (most accelerometer/gyroscope channels are near-zero), and efficient memory usage for large calibration tables.

Key Insight: You must check for overflow BEFORE the multiply-and-add step — comparing the accumulated result against INT_MAX/10 and INT_MIN/10 prevents undefined behavior without needing a larger integer type.

Thought Process:

1. Converting to string, reversing, and converting back works but is wasteful and still requires overflow handling.
2. Extract digits with x % 10 and build the reversed number with y = y * 10 + digit — straightforward but overflows silently.
3. Using long long to detect overflow after the fact works but the problem explicitly forbids it.
4. The key: check y > INT_MAX/10 or y < INT_MIN/10 BEFORE multiplying — this catches overflow without ever triggering it.

Approach: Extract digits from the right using x % 10, build the reversed number by multiplying by 10 and adding each digit. The key: check for overflow BEFORE the multiply by comparing the accumulated result against INT_MAX/10 and INT_MIN/10. This avoids undefined behavior from integer overflow.

class Solution {
public:
    int reverse(int x) {
        int y = 0;
        while (x) {
            if (y > INT_MAX / 10 || y < INT_MIN / 10) {
                return 0;
            } else {
                y = y * 10 + x % 10;
                x = x / 10;
            }
        }
        return y;
    }
};

Time Complexity: O(log n) where n is the input value — there are floor(log10(n)) + 1 digits to process, and each iteration extracts one digit.

Space Complexity: O(1) — only a fixed number of integer variables are used regardless of input size.

Embedded relevance: Overflow checking before arithmetic is a critical embedded skill — MISRA C requires it for safety-critical code, and getting it wrong causes subtle bugs in sensor data processing and protocol field packing.

Key Insight: Reverse the entire integer digit-by-digit and compare with the original — negative numbers are never palindromes, and using a wider type for the reversed value avoids overflow concerns.

Thought Process:

1. Converting to string and comparing with its reverse is O(log n) time and O(log n) space — works but uses extra memory.
2. Reversing the integer in-place and comparing avoids the string allocation.
3. Edge cases: negative numbers always return false (the minus sign breaks symmetry).
4. Use a long long for the reversed number to avoid overflow during reversal of values near INT_MAX.

Approach: Reverse the integer digit-by-digit and compare with the original. Negative numbers are never palindromes. Use a long long for the reversed number to avoid overflow during reversal.

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;

        long long temp = x, dummy = 0;

        while (temp) {
            dummy *= 10;
            dummy += temp % 10;
            temp /= 10;
        }

        return (long long)x == dummy;
    }
};

Time Complexity: O(log n) — processes each digit once, and a number n has floor(log10(n)) + 1 digits.

Space Complexity: O(1) — only a constant number of variables are used.

Key Insight: Binary exponentiation (square-and-multiply) reduces O(n) multiplications to O(log n) by squaring the base at each step and only multiplying into the result when the corresponding exponent bit is set.

Thought Process:

1. Naive: multiply x by itself n times — O(n), too slow for large exponents.
2. Recursive divide-and-conquer: pow(x, n) = pow(x, n/2)^2 — O(log n) but uses O(log n) stack space.
3. Iterative binary exponentiation: iterate through bits of n, square x each step, multiply into result when bit is set — O(log n) time AND O(1) space.
4. Handle negative exponents by inverting x and negating n; use long long for n to handle INT_MIN safely.

Approach: Square-and-multiply: iterate through the bits of the exponent. If the current bit is set, multiply the result by the current power of x. Square x at each step. This reduces O(n) multiplications to O(log n). Handle negative exponents by inverting x and negating n.

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;
        for (long long i = N; i; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        return ans;
    }
};

Time Complexity: O(log n) — each iteration processes one bit of the exponent, and a 32-bit integer has at most 31 significant bits.

Space Complexity: O(1) — only a fixed number of variables are used regardless of n.

Embedded relevance: Binary exponentiation (square-and-multiply) is the foundation of modular exponentiation used in embedded cryptography — RSA, Diffie-Hellman, and digital signature algorithms all rely on this O(log n) technique.

Key Insight: Repeatedly dividing by 2, 3, and 5 strips away all allowed prime factors — if the result is 1, no other primes were present.

Thought Process:

1. Full prime factorization with trial division up to sqrt(n) works but is overkill — O(sqrt(n)).
2. Since we only care about three specific primes (2, 3, 5), just divide by each repeatedly.
3. If after removing all factors of 2, 3, and 5 the result is 1, the number is ugly. If not, it has other prime factors.
4. Edge case: non-positive numbers are never ugly by definition.

Approach: Repeatedly divide by 2, 3, and 5 as long as each is a factor. If the result is 1, the number is ugly (its only prime factors were 2, 3, and 5). If not, it has other prime factors. Non-positive numbers are never ugly.

class Solution {
public:
    vector<int> primes = {2, 3, 5};
    bool isUgly(int n) {
        if (n < 1) return false;
        for (int p : primes) while (n % p == 0) n /= p;
        return n == 1;
    }
};

Time Complexity: O(log n) — each division by 2, 3, or 5 reduces n by at least half, so the total number of divisions is bounded by log2(n).

Space Complexity: O(1) — only the input variable and a small constant array are used.