Math Interview Problems for Embedded Engineers

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;
    }
};

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.

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;
    }
};

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.

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;
    }
};

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;
    }
};

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.

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;
    }
};