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.

MediumTechnical

64 practiced

Given two sorted arrays A and B where A has length m+n with the first m elements valid and the last n positions empty and B has n elements, implement in Python an in-place merge so that A contains the sorted result of size m+n. Aim for O(m+n) time and O(1) extra space. Explain edge cases and how you'd adapt to arrays of strings or very large elements.

Sample Answer

Approach: Merge from the end of A in-place. Use three pointers: i = m-1 (end of valid A), j = n-1 (end of B), k = m+n-1 (write position). Compare A[i] and B[j] and write the larger to A[k], decrementing appropriate pointers. This avoids overwriting valid A elements and achieves O(m+n) time and O(1) extra space.

python

def merge_in_place(A, m, B, n):
    """
    Merge sorted arrays A and B into A in-place.
    A has length m+n with first m valid elements; B has n elements.
    """
    i, j, k = m - 1, n - 1, m + n - 1

    while j >= 0:
        # If A exhausted, take from B; otherwise take the larger of A[i], B[j]
        if i >= 0 and A[i] > B[j]:
            A[k] = A[i]
            i -= 1
        else:
            A[k] = B[j]
            j -= 1
        k -= 1
    # A now contains merged sorted elements

Key points:- Time: O(m + n) — each element moved at most once.- Space: O(1) extra memory; operations done in-place.

Edge cases:- n == 0 (B empty): function leaves A unchanged.- m == 0 (A has only buffer): loop copies all B into A.- Duplicate values handled naturally.- Already merged when largest elements are in A: loop still correct.

Adapting to strings or very large elements:- Same algorithm works for any comparable types (strings compare lexicographically).- For very large or heavy-to-copy elements (large objects), prefer storing references/pointers (Python stores references by default) so cost is pointer assignment not deep copy.- If elements are immutable large objects and copying cost matters in other languages, consider moving pointers or indices instead of copying content, or use stable external merge if memory permits.

Testing tips: include empty arrays, all elements from one array smaller than the other, duplicates, and mixed types if allowed.

HardTechnical

54 practiced

Implement in Go a function that validates an io.Reader byte stream as UTF-8 and counts Unicode code points. The reader must be consumed in fixed-size chunks (e.g., 4096 bytes) without loading the whole stream. The function should correctly handle multibyte sequences split across chunk boundaries and report the byte offset of the first invalid sequence if any.

Sample Answer

Approach:Read the stream in fixed-size chunks, append each chunk to a small buffer that may contain leftover bytes from the previous read, and decode runes only when a complete UTF‑8 sequence is present (using utf8.FullRune). This ensures correct handling when multibyte sequences are split across chunk boundaries. On invalid sequences, return the byte offset of the first invalid byte (relative to the stream start) and an error. Count code points as you decode.

package main

import (
	"errors"
	"io"
	"unicode/utf8"
)

// ValidateUTF8AndCount reads from r in fixed-size chunks, validates UTF-8, and returns
// the number of Unicode code points. If invalid UTF-8 is found, it returns the byte
// offset (0-based) of the first invalid byte.
func ValidateUTF8AndCount(r io.Reader, chunkSize int) (count int64, invalidOffset int64, err error) {
	if chunkSize < 1 {
		chunkSize = 4096
	}
	buf := make([]byte, 0, chunkSize*2) // leftover + current chunk
	tmp := make([]byte, chunkSize)
	var totalConsumed int64 // bytes successfully decoded so far

	for {
		n, readErr := r.Read(tmp)
		if n > 0 {
			buf = append(buf, tmp[:n]...)
		}

		// Decode all complete runes in buf
		for {
			if len(buf) == 0 {
				break
			}
			// If we don't have a full rune yet, wait for more bytes (unless EOF)
			if !utf8.FullRune(buf) {
				break
			}
			rn, size := utf8.DecodeRune(buf)
			if rn == utf8.RuneError && size == 1 {
				// invalid encoding at current consumed offset
				return count, totalConsumed, errors.New("invalid UTF-8 sequence")
			}
			count++
			totalConsumed += int64(size)
			buf = buf[size:]
		}

		if readErr != nil {
			if readErr == io.EOF {
				// If leftover bytes remain, they must form a complete rune; otherwise invalid
				if len(buf) != 0 {
					// leftover incomplete sequence -> invalid at totalConsumed
					return count, totalConsumed, errors.New("incomplete/invalid UTF-8 sequence at EOF")
				}
				return count, -1, nil // valid, no invalid offset
			}
			// other read error
			return count, totalConsumed, readErr
		}
	}
}

Key points:- Use utf8.FullRune to avoid misinterpreting partial sequences split across chunks.- Use utf8.DecodeRune to get rune and width; treat RuneError with size==1 as invalid byte sequence.- Track totalConsumed to report the byte offset of the first invalid byte.

Complexity:- Time: O(n) over stream length n (each byte processed once).- Space: O(chunkSize) extra; buffer only holds leftover and current chunk.

Edge cases:- Empty stream -> count 0.- Valid single-byte and multibyte mix.- Multibyte sequence split across chunk boundary (handled).- Incomplete sequence at EOF -> reported invalid at its starting offset.- Non-EOF read errors are propagated.

Alternative:- You could validate using bufio.Reader.Peek to simplify handling, but explicit chunk reads are preferred when you must control fixed chunk sizes and minimize allocations.

MediumTechnical

45 practiced

Describe and implement (pseudocode or Python) a method to check whether a user-visible string is a palindrome while accounting for Unicode normalization (NFC/NFD), case-folding, ignoring combining marks, and skipping non-letter characters. Explain why naive byte-wise or codepoint-wise checks can be incorrect when combining marks or different normalization forms appear.

Sample Answer

Approach: Normalize to a canonical form (NFC or NFD), case-fold for Unicode-aware lowercasing, remove combining marks (diacritics) so base letters compare, keep only characters classified as letters (Unicode categories starting with "L"), then check palindrome by two-pointer compare.

Why naive checks fail: Different normalization forms (e.g., "é" as single U+00E9 vs. "e" + U+0301) have different codepoint sequences though they look identical. Combining marks can attach to different base codepoints or be in different orders; simple byte- or codepoint-wise reversal will treat visually identical strings as different. Case-insensitive ASCII lowercasing isn't sufficient for languages with special case-fold rules (German ß → "ss", Greek sigma final forms). Removing combining marks ensures diacritics don't make visually identical base letters mismatch when the intent is to ignore marks.

Python implementation:

python

import unicodedata

def is_unicode_palindrome(s: str) -> bool:
    """
    Return True if user-visible string s is a palindrome under:
    - Unicode normalization (NFC → use NFD to separate combining marks)
    - case-folding (Unicode-aware)
    - ignoring combining marks (diacritics)
    - skipping non-letter characters
    """
    # Normalize to NFD to separate base + combining marks
    normalized = unicodedata.normalize('NFD', s)
    # Case-fold for Unicode-aware case-insensitivity
    folded = normalized.casefold()

    # Keep only base letters, dropping combining marks and non-letters
    filtered_chars = []
    for ch in folded:
        cat = unicodedata.category(ch)
        if cat.startswith('M'):
            # Mark (combining) — skip
            continue
        if cat.startswith('L'):
            filtered_chars.append(ch)
        # else: ignore punctuation, spaces, numbers, symbols

    # Two-pointer palindrome check
    i, j = 0, len(filtered_chars) - 1
    while i < j:
        if filtered_chars[i] != filtered_chars[j]:
            return False
        i += 1
        j -= 1
    return True

Key points:- Use NFD to separate combining marks so they can be removed reliably; NFC could be used too but separating makes dropping marks straightforward.- Use str.casefold() for robust Unicode case-insensitivity.- unicodedata.category() identifies letters vs. marks vs. punctuation.- Time complexity: O(n) for normalization and single pass; space O(n) for filtered list.- Edge cases: scripts where "letters" include non-Latin scripts (works); languages where diacritics change meaning — dropping marks is a policy decision. If you must preserve certain marks, adapt filtering. For security/visual-similarity concerns, consider additional normalization (NFKC) or script-aware checks.

MediumTechnical

44 practiced

Implement a robust CSV tokenizer in Python that splits a single CSV line into fields, correctly handling quoted fields, escaped quotes ("" representing a quote inside a quoted field), and custom delimiters. Example: input 'a,"b,c",d' should produce ['a', 'b,c', 'd']. Describe how to extend this to streaming CSVs with quoted fields that span multiple lines.

Sample Answer

To parse a single CSV line robustly, use a state machine tracking whether you're inside a quoted field. Handle doubled quotes as escaped quotes and allow a custom delimiter.

python

def tokenize_csv_line(line, delimiter=',', quotechar='"'):
    """
    Tokenize a single CSV line into fields.
    Handles quoted fields and doubled-quote escapes.
    """
    fields = []
    cur = []
    in_quotes = False
    i = 0
    n = len(line)

    while i < n:
        ch = line[i]

        if in_quotes:
            if ch == quotechar:
                # Lookahead for escaped quote ("" -> ")
                if i + 1 < n and line[i + 1] == quotechar:
                    cur.append(quotechar)
                    i += 2
                    continue
                else:
                    in_quotes = False
                    i += 1
                    continue
            else:
                cur.append(ch)
                i += 1
                continue
        else:
            if ch == quotechar:
                in_quotes = True
                i += 1
                continue
            elif ch == delimiter:
                fields.append(''.join(cur))
                cur = []
                i += 1
                continue
            else:
                cur.append(ch)
                i += 1
                continue

    # append last field
    fields.append(''.join(cur))
    return fields

Key points:- State machine with in_quotes boolean.- Doubled quotes inside quoted fields are converted to a single quote.- Custom delimiter supported.

Time complexity: O(n) where n = length of line. Space: O(n) for output.

Edge cases:- Unclosed quotes (malformed line) — decide to raise an error or accept the remainder as a field.- Empty fields, leading/trailing spaces, delimiter at line ends.

Extending to streaming multiline CSVs:- Maintain parser state across lines: keep in_quotes and current buffer between reads.- Feed each incoming line (including newline) into the same state machine; when a quote-terminated field closes and a delimiter or line-end finalizes a record, emit the row.- For efficiency in SRE contexts, parse in chunks from a file/socket and emit rows as soon as complete to avoid buffering large inputs; apply backpressure if downstream can't keep up.

MediumTechnical

47 practiced

Implement a function in Go that given a slice of integers representing per-second request counts and an integer k returns the maximum sum of any contiguous k-second window. The solution must be O(n) time and O(1) extra space. Handle edge cases such as k<=0, k>len(slice), and empty input; describe how you'd test for off-by-one errors with metric streams.

Sample Answer

Approach: use a sliding-window sum of size k, updating in O(1) per element. Handle edge cases up-front (k<=0, k>n, empty slice). For metrics streams, be careful about inclusive/exclusive window definitions and warm-up when stream hasn't produced k samples.

package main

import "errors"

// MaxKWindow returns the maximum sum of any contiguous k-second window.
// Returns error for invalid k or empty input.
func MaxKWindow(samples []int, k int) (int, error) {
	if k <= 0 {
		return 0, errors.New("k must be > 0")
	}
	n := len(samples)
	if n == 0 {
		return 0, errors.New("samples empty")
	}
	if k > n {
		return 0, errors.New("k cannot be greater than number of samples")
	}

	// initialize first window
	sum := 0
	for i := 0; i < k; i++ {
		sum += samples[i]
	}
	max := sum

	// slide window: remove left, add right
	for i := k; i < n; i++ {
		sum += samples[i] - samples[i-k]
		if sum > max {
			max = sum
		}
	}
	return max, nil
}

Key points:- Time: O(n), Space: O(1) extra (only ints).- Edge cases explicitly return errors.- For metric streams: define whether a window is "last k seconds" inclusive; in streaming collectors, buffer exactly k samples before computing; handle late/duplicate samples and alignment (e.g., wall-clock second boundaries). To test off-by-one errors: - Unit tests with small arrays where expected windows are obvious (e.g., samples [1,2,3,4], k=2 => max 7). - Tests for k=1, k=n, k=n-1. - Property tests: compare to naive O(n*k) implementation. - Simulate streaming: feed samples one-by-one and assert outputs after k, k+1,... to ensure correct timing and alignment.

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.