String Interview Problems for Embedded Engineers

String manipulation is central to embedded engineering — from parsing AT commands and NMEA sentences to implementing atoi/strtol for configuration data. These problems test your ability to work with character arrays in-place, a must when heap allocation is off-limits.

Problems

#	Problem	Difficulty	Frequency
1	Valid Palindrome	Easy	★★★★★
2	strstr (first occurrence of str2 in str1)	Easy	★★★★★
3	Valid Palindrome II	Easy	★★★★★
4	Decode String	Medium	★★★★★
5	Find All Anagrams in a String	Medium	★★★★★
6	Reverse words in a sentence	Medium	★★★★★
7	First non-recurring character in a string	Easy	★★★★★
8	String to integer (atoi / strtol)	Medium	★★★★★

Pattern Cheat Sheet

Pattern	Technique	Problems
Two pointers	Converge from both ends	Valid Palindrome, Valid Palindrome II
Sliding window	Fixed-size window + hash map	Find All Anagrams
Stack	Nested structure processing	Decode String
Brute force scan	Character-by-character matching	strstr

Implementation

Valid Palindrome Easy ★★★★★

Problem: Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring cases.

QSolution — O(n) time, O(1) space — Two Pointers

Approach: Use two pointers converging from both ends. Skip non-alphanumeric characters, then compare lowercase versions of the characters at each pointer. This is the classic in-place string technique that avoids creating a filtered copy.

cpp

class Solution {
public:
    bool isPalindrome(string s) {
        int st = 0;
        int end = s.size() - 1;

        while (st < end) {
            if (!isalnum(s[st]) || !isalnum(s[end])) {
                while (st < end && !isalnum(s[st])) st++;
                while (st < end && !isalnum(s[end])) end--;
            } else {
                if (tolower(s[st]) != tolower(s[end]))
                    return false;
                st++;
                end--;
            }
        }

        return true;
    }
};

strstr (Implement strStr) Easy ★★★★★

Problem: Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1.

QSolution — O((N−M)×M) time, O(1) space — Brute Force

Approach: For each position in the source string, check if the target matches starting there. This brute force approach is O((N−M)×M) but is perfectly acceptable for embedded — it uses zero extra memory, requires no preprocessing, and the constant factor is tiny. KMP or Rabin-Karp would be O(N+M) but are rarely expected in interviews for this problem.

cpp

class Solution {
public:
    int strStr(string& source, string& target) {
        if (source.size() < target.size()) return -1;
        if (target.size() == 0) return 0;

        for (int ret = 0; ret < source.size() - target.size() + 1; ret++) {
            if (source[ret] == target[0]) {
                for (int i = 0; i < target.size(); i++) {
                    if (source[ret + i] != target[i])
                        break;
                    else if (i == target.size() - 1)
                        return ret;
                }
            }
        }
        return -1;
    }
};

Embedded relevance: This is essentially what strstr() from <string.h> does — a function you use constantly when parsing command responses, log messages, and protocol headers in firmware.

Valid Palindrome II Easy ★★★★★

Problem: Given a string, determine if it can be a palindrome after deleting at most one character.

QSolution — O(n) time, O(1) space — Two Pointers + Helper

Approach: Use two pointers converging from both ends. When a mismatch is found, you have one chance to skip either the left or right character. Check if the remaining substring (skipping left OR skipping right) is a palindrome. If either works, the original string is a valid palindrome with one deletion.

cpp

class Solution {
public:
    bool isPalin(string& s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) return false;
            ++start;
            --end;
        }
        return true;
    }

    bool validPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return (isPalin(s, i, j - 1) || isPalin(s, i + 1, j));
            }
        }
        return true;
    }
};

Decode String Medium ★★★★★

Problem: Given an encoded string in the format k[encoded_string], return the decoded string repeated k times.

QSolution — O(maxK × n) time, O(m + n) space — Stack

Approach: Use a stack of (count, string) pairs. When encountering [, push the current count and start a new string context. When encountering ], pop the top, repeat the accumulated string by the count, and append it to the previous context (or to the result if the stack is empty). Digits build the count; letters accumulate into the current string.

cpp

class Solution {
public:
    string decodeString(string s) {
        stack<pair<int, string>> decode_stk;
        string ret = "";
        int number = 0;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '[') {
                string encode_str = "";
                decode_stk.push(make_pair(number, encode_str));
                number = 0;
            } else if (s[i] == ']') {
                pair<int, string> tmp = decode_stk.top();
                decode_stk.pop();
                string copy = tmp.second;
                while (--tmp.first) copy += tmp.second;

                if (decode_stk.empty()) {
                    ret += copy;
                } else {
                    auto& top = decode_stk.top();
                    top.second += copy;
                }
            } else if (isalpha(s[i])) {
                if (decode_stk.empty()) {
                    ret += s[i];
                } else {
                    decode_stk.top().second += s[i];
                }
            } else if (isdigit(s[i])) {
                number = number * 10 + s[i] - '0';
            }
        }

        return ret;
    }
};

Find All Anagrams in a String Medium ★★★★★

Problem: Given two strings s and p, find all start indices of p's anagrams in s.

QSolution — O(Ns + Np) time, O(1) space — Sliding Window + Hash Map

Approach: Build a frequency map for the pattern p. Slide a window of size |p| across s, maintaining a frequency map of the current window. When the two maps match, the window is an anagram. By adding/removing one character per slide, each step is O(1) amortized. The space is O(1) because there are at most 26 distinct characters.

cpp

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> p_umap, s_umap;
        vector<int> ret;

        if (s.size() < p.size()) return ret;

        for (auto c : p) p_umap[c]++;

        int st = 0, end = 0;

        while (end < s.size()) {
            if (end - st + 1 < p.size()) {
                if (p_umap.find(s[end]) != p_umap.end()) {
                    s_umap[s[end]]++;
                    end++;
                } else {
                    s_umap.clear();
                    end++;
                    st = end;
                }
            } else if (end - st + 1 > p.size()) {
                if (s_umap[s[st]] == 1)
                    s_umap.erase(s[st]);
                else
                    s_umap[s[st]]--;
                st++;
            } else {
                s_umap[s[end]]++;
                if (s_umap == p_umap) ret.push_back(st);
                end++;
            }
        }

        return ret;
    }
};

Embedded relevance: Sliding window with frequency counting is the same pattern used for detecting byte sequences in serial protocol streams — matching known command patterns within a continuous data flow.