Array and String Manipulation Questions

Comprehensive coverage of language level operations and algorithmic techniques for arrays and strings that are commonly evaluated in coding interviews. Candidates should understand common language methods for arrays and strings, including their parameters and return values, chaining of operations, and the implications of mutable versus immutable types for in place versus extra space solutions. Core algorithmic patterns include iteration and traversal, index based and pointer based approaches, two pointer strategies, sliding window, prefix and suffix sums, sorting and partitioning, and cumulative or running sums. Problem classes include traversal, insertion and deletion, reversing and rotating, merging and deduplicating, subarray and substring search, anagram detection, palindrome detection, longest substring and maximum subarray problems, and pointer based reordering and partitioning tasks. Pattern matching techniques include naive matching, Knuth Morris Pratt and rolling hash approaches, and hashing for frequency and membership checks. String transformation and comparison topics include edit distance, sequence transformation problems such as word ladder, and parsing and validation tasks. Candidates should be prepared to implement correct and efficient solutions in common programming languages, reason about time and space complexity, optimize for input size and memory constraints, handle edge cases such as empty inputs and boundary conditions, and address character level concerns such as encoding differences, multibyte characters, surrogate pairs and unicode normalization. Interviewers may probe language specific implementation details, in place mutation versus copying, fixed buffer strategies, streaming or incremental algorithms for large inputs, and trade offs between clarity and performance. Expect questions that require selecting the right algorithmic pattern, implementing a robust solution, and justifying complexity and memory decisions.

MediumSystem Design

48 practiced

You have a very large read-only text stored in external flash accessible only via a block-read API:

ssize_t read_block(off_t offset, void *buf, size_t size);

Design an algorithm to search for a pattern of length m (m <= 512) in the huge text using <4KB RAM and minimizing block reads. Provide high-level pseudocode and explain how you handle block boundaries and state retention between reads.

Sample Answer

**Approach (high-level)**

Use a streaming Knuth–Morris–Pratt (KMP) matcher so you keep only the pattern's prefix table and current match state between block reads. Read the flash in large block-aligned chunks to minimize block_read calls, but keep a small RAM buffer (<=4KB). Handle boundaries by carrying over the last (m-1) bytes (or less) implicitly via KMP state — no need to copy whole overlap.

**Why KMP**- KMP is streaming-friendly: it processes bytes one-by-one and only requires the pattern prefix table (pi[0..m-1]) and current j (0..m).- Memory: pi (m integers, m<=512) fits <4KB; plus a read buffer (e.g., 2048 bytes) keeps total RAM under constraint.

**Constraints & choices**- Reserve memory: pi[] (m * 2 or 4 bytes), buffer_size = min(2048, available RAM - pi_size).- Read block size choose to align with flash block to reduce IO; if block_read requires specific granularity, request multiples of that.

**Pseudocode**

// build prefix table
void build_pi(uint8_t *pat, int m, int16_t *pi) {
  pi[0] = 0;
  int k = 0;
  for (int q=1; q<m; ++q) {
    while (k>0 && pat[k] != pat[q]) k = pi[k-1];
    if (pat[k] == pat[q]) ++k;
    pi[q] = k;
  }
}

// streaming search
// callback(offset) when match found
void search_flash(uint8_t *pat, int m, off_t text_len) {
  int16_t pi[512];                // fits under RAM budget
  build_pi(pat, m, pi);
  const size_t BUF = 2048;        // choose so pi + buf < 4KB
  uint8_t buf[BUF];
  off_t off = 0;
  int j = 0;                       // current KMP state
  while (off < text_len) {
    size_t to_read = min(BUF, text_len - off);
    ssize_t r = read_block(off, buf, to_read);
    if (r <= 0) break;
    for (size_t i=0; i<(size_t)r; ++i) {
      uint8_t c = buf[i];
      while (j>0 && pat[j] != c) j = pi[j-1];
      if (pat[j] == c) ++j;
      if (j == m) {
        report_match(off + i - m + 1);
        j = pi[j-1];             // continue searching (handles overlap)
      }
    }
    off += r;
  }
}

**Block-boundary & state retention**- No explicit overlap copy: KMP variable j retains how many pattern bytes matched at the end of the previous block. When next block bytes arrive, matching continues seamlessly.- If pattern longer than buffer, pi still fits; but ensure buffer >=1 so progress is made.

**Performance & trade-offs**- Minimizes block reads by making each read large and aligned.- CPU: O(n + m) overall, per-byte constant work.- Memory: pi (~1–2KB for m<=512) + buf (tunable) fits <4KB.- If flash read granularity > BUF, choose read size = flash block size or its multiple.

EasyTechnical

48 practiced

Write a C implementation of a naive substring search:

int naive_strstr(const char *haystack, const char *needle);

Return the index of the first occurrence of needle in haystack or -1 if not found. Do not call library search functions. Handle empty needle (return 0) and avoid reading past terminators. This will be used in embedded code with small stacks.

Sample Answer

**Approach**- Simple double-loop naive search using pointers to avoid extra stack usage. Return 0 for empty needle. Carefully check terminators to avoid reading past string ends (important in embedded systems).

**Code**

#include <stddef.h>

int naive_strstr(const char *haystack, const char *needle) {
    if (!haystack || !needle) return -1; /* defensive; adjust if NULL never passed */
    /* empty needle -> match at 0 */
    if (*needle == '\0') return 0;

    for (int i = 0; haystack[i] != '\0'; ++i) {
        int j = 0;
        /* compare needle against haystack starting at i */
        while (needle[j] != '\0' && haystack[i + j] != '\0' &&
               haystack[i + j] == needle[j]) {
            ++j;
        }
        if (needle[j] == '\0') return i; /* full match */
        /* if haystack ends, no further matches possible */
        if (haystack[i + j] == '\0') return -1;
    }
    return -1;
}

**Explanation & Complexity**- Uses only indices and stack-local ints (small stack footprint).- Time: O(n * m) worst-case (n = |haystack|, m = |needle|). Space: O(1).- Edge cases handled: empty needle, needle longer than remaining haystack, no library calls. Suitable for constrained embedded environments.

HardTechnical

84 practiced

Implement in C an in-place POSIX-style path canonicalizer:

size_t canonicalize_path(char *path);

Given a null-terminated path that may contain "/", "//", ".", and ".." components, transform it in-place to the canonical path (no trailing slash unless root) and return the new length. No heap allocation; the path buffer has a fixed size—ensure you never write past the original buffer.

Sample Answer

**1. Brief approach**- Walk input with a read pointer, write normalized components into buffer in-place using a stack-pointer (index of write).- Handle "/", ".", ".." correctly; preserve leading "/" for absolute paths.- Never allocate heap; only use integer indices and existing buffer. Ensure trailing slash removed unless path is root "/".

**2. Code implementation**

#include <string.h>
#include <stddef.h>

size_t canonicalize_path(char *path) {
    if (!path) return 0;
    size_t n = strlen(path);
    size_t read = 0, write = 0;
    int absolute = (n>0 && path[0]=='/');
    if (absolute) { path[write++] = '/'; while (read < n && path[read]=='/') read++; }

    while (read < n) {
        // find next component [read, end)
        size_t start = read;
        while (read < n && path[read] != '/') read++;
        size_t len = read - start;

        if (len == 0) { // multiple slashes -> skip
            while (read < n && path[read]=='/') read++;
            continue;
        } else if (len == 1 && path[start]=='.') {
            // no-op
        } else if (len == 2 && path[start]=='.' && path[start+1]=='.') {
            // back up one component if possible
            if (write > 1 || (write>0 && !absolute)) {
                // remove trailing slash if present
                if (write>0 && path[write-1]=='/') write--;
                // back up to previous '/'
                while (write>0 && path[write-1] != '/') write--;
                // for relative, allow removing last component entirely
            } else if (!absolute) {
                // relative and nothing to pop -> append ".."
                if (write && path[write-1] != '/') path[write++] = '/';
                memcpy(path+write, "..", 2); write += 2;
            }
        } else {
            // append separator if needed
            if (write>0 && path[write-1] != '/') path[write++] = '/';
            // copy component (safe since read >= write or same buffer)
            memmove(path+write, path+start, len);
            write += len;
        }
        // skip slashes between components
        while (read < n && path[read]=='/') read++;
    }

    // Final adjustments: remove trailing slash unless root
    if (write > 1 && path[write-1] == '/') write--;
    path[write] = '\0';
    return write;
}

**3. Key concepts & reasoning**- Use two-pointer in-place transform; memmove used to handle overlapping regions.- Treat absolute and relative paths differently for leading "..".- Preserve root "/" when result empty.

**4. Complexity**- Time: O(n). Space: O(1) extra.

**5. Edge cases**- "", "/", "///", ".", "..", "a//b/./c", "/a/../..", relative leading ".." preserved.

MediumTechnical

60 practiced

Implement UTF-8 validation and codepoint counting in C:

ssize_t utf8_validate_and_count(const uint8_t *buf, size_t len);

Return the number of Unicode codepoints if the byte sequence is valid UTF-8, otherwise return -1. Validate against overlong encodings, invalid continuation bytes, and surrogate halves. Target correctness over exotic performance features.

Sample Answer

**Approach**- Iterate bytes, decode UTF-8 sequences, validate lengths, continuation bytes, overlong encodings, and disallow surrogate halves (U+D800..U+DFFF). Count codepoints; on any error return -1.

**Code**

#include <stddef.h>
#include <stdint.h>
#include <sys/types.h>

ssize_t utf8_validate_and_count(const uint8_t *buf, size_t len) {
    size_t i = 0;
    ssize_t count = 0;
    while (i < len) {
        uint8_t b = buf[i];
        uint32_t cp = 0;
        size_t need = 0;
        if (b <= 0x7F) { cp = b; need = 0; }
        else if ((b & 0xE0) == 0xC0) { cp = b & 0x1F; need = 1; if (cp < 0x2) return -1; } // prevent overlong: cp >= 0x80
        else if ((b & 0xF0) == 0xE0) { cp = b & 0x0F; need = 2; }
        else if ((b & 0xF8) == 0xF0) { cp = b & 0x07; need = 3; if (cp > 0x4) return -1; } // > U+10FFFF
        else return -1;
        if (i + need >= len) return -1;
        for (size_t k = 1; k <= need; ++k) {
            uint8_t cb = buf[i+k];
            if ((cb & 0xC0) != 0x80) return -1;
            cp = (cp << 6) | (cb & 0x3F);
        }
        // Overlong checks for 3- and 4-byte sequences and surrogate check
        if (need == 2 && cp < 0x800) return -1;
        if (need == 3 && cp < 0x10000) return -1;
        if (cp >= 0xD800 && cp <= 0xDFFF) return -1; // surrogate halves invalid
        if (cp > 0x10FFFF) return -1;
        i += 1 + need;
        count++;
    }
    return count;
}

**Explanation & Complexity**- Single pass O(n) time, O(1) space. Handles ASCII, multi-byte rules, rejects invalid/overlong/surrogate encodings. For embedded use, code is branch-light and avoids heap. Edge cases: truncated sequences, invalid continuation bytes, overlong encodings, codepoints > U+10FFFF, and surrogate range.

MediumTechnical

49 practiced

Implement a function that computes the length of the longest substring without repeating characters for an ASCII string:

size_t longest_unique_substr_len(const char *s);

Aim for O(n) time and O(1) extra memory (bounded by a 256-entry table). This is intended for an embedded device where heap usage is undesirable. Discuss how to adapt the solution for full Unicode codepoints and for very large alphabets when memory is constrained.

Sample Answer

**Approach (sliding window, ASCII table)** Use two pointers (i,j) and a 256-entry array last_index[] storing last seen +1 (0 means unseen). Move j forward, if char c was seen inside window (last_index[c] > i) advance i to last_index[c]. Update last_index[c] = j+1 and track max length. O(n) time, O(1) extra memory (256 entries).

**C implementation**

#include <stddef.h>
#include <stdint.h>

size_t longest_unique_substr_len(const char *s) {
    if (!s) return 0;
    size_t last[256] = {0}; // last seen position +1
    size_t i = 0, j = 0, max = 0;
    while (s[j]) {
        unsigned char c = (unsigned char)s[j];
        if (last[c] > i) i = last[c];        // shrink window past previous occurrence
        last[c] = j + 1;                     // store position+1
        size_t len = j - i + 1;
        if (len > max) max = len;
        j++;
    }
    return max;
}

**Complexity**- Time: O(n)- Space: O(1) fixed 256-entry table

**Edge cases**- NULL or empty string -> 0- All-unique / all-same strings handled

**Adapting to Unicode / large alphabets**- Unicode codepoints: decode UTF-8 to codepoints, but codepoint range >>256. Use a compact hashtable mapping codepoint->last index (open addressing) sized proportionally to expected distinct run; still O(n) average time.- Very large alphabets with tight memory: use LRU-style bloom/approximate or sliding-window with window-indexed map stored as sorted array when distinct count small; or stream-processing trade-off: limit tracked set to recent K characters, sacrificing exactness. For correctness with low memory, prefer a small dynamic hash table using preallocated bucket pool to avoid heap (embedded-friendly).

Unlock Full Question Bank

Get access to hundreds of Array and String Manipulation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.