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.

EasyTechnical

47 practiced

Write a Python function that simplifies a Unix-style path string by resolving '.' and '..' components and removing redundant slashes. For example, input '/a/./b/../../c/' should return '/c'. Handle edge cases such as paths that try to go above root and empty input.

Sample Answer

To simplify a Unix-style path, we can split on '/', use a stack to process components, ignore '.' and empty components, pop for '..' (but don't pop past root), and finally join the stack with '/' (return '/' for empty stack). This is O(n) time and O(n) space.

python

def simplify_path(path):
    """
    Simplify a Unix-style path.
    Examples:
      '/a/./b/../../c/' -> '/c'
      '' -> '/'
      '/../../' -> '/'
    """
    if not path:
        return '/'
    
    parts = path.split('/')
    stack = []
    
    for p in parts:
        if p == '' or p == '.':
            # skip empty (redundant slashes) and current dir
            continue
        if p == '..':
            if stack:
                stack.pop()  # go up one directory
            # else: at root, ignore attempts to go above root
        else:
            stack.append(p)  # valid directory name
    
    return '/' + '/'.join(stack) if stack else '/'

Key points:- Uses a stack to model directory traversal.- Handles redundant slashes, '.' and '..', empty input, and attempts to go above root.Time Complexity: O(n) where n is length of the path (split and single pass).Space Complexity: O(n) for split parts and stack.

Edge cases:- Empty string -> '/'- Trailing slash preserved only as root '/' or omitted otherwise- Multiple consecutive '..' beyond root -> remain at '/'

Alternative: process characters without split for slightly lower overhead, but split+stack is clear and sufficient for typical data-engineering utilities.

EasyTechnical

50 practiced

Theoretical: Explain the difference between mutable and immutable string types in languages commonly used by data engineers (for example Python str vs bytearray, Java String vs StringBuilder). Discuss implications for in-place mutation, memory allocation, concurrency, and performance when processing large text datasets in ETL pipelines.

EasyTechnical

66 practiced

Given a sorted array of integers, implement a function in Python that finds two numbers that add up to a target value and returns their indices (or (-1, -1) if none). The solution must run in O(n) time and use O(1) extra space. Discuss how the two-pointer technique works and edge cases like duplicates and negative numbers.

Sample Answer

To solve this in O(n) time and O(1) extra space, use the two-pointer technique: place one pointer at the start (left) and one at the end (right) of the sorted array. Sum the two values; if sum == target return (left, right). If sum < target, increment left to increase the sum; if sum > target, decrement right to decrease the sum. Repeat until pointers cross.

python

def two_sum_sorted(nums, target):
    """
    nums: sorted list of integers
    returns: tuple of indices (i, j) or (-1, -1) if none
    """
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        if s < target:
            left += 1
        else:
            right -= 1
    return (-1, -1)

Key points:- Two-pointer works because array is sorted: moving left right adjusts sum monotically.- Time: O(n) single pass. Space: O(1) extra (indices only).Edge cases:- Duplicates: allowed — pointers still return valid indices (e.g., [2,2,3], target 4 → (0,1)).- Negative numbers: handled naturally (sorted order preserves monotonic sum behavior).- Empty or single-element arrays: returns (-1,-1).- If problem asks for 1-based indices or original unsorted indices, adjust accordingly (or use hash map for unsorted input but that uses O(n) space).

HardTechnical

64 practiced

Given a mutable byte array representing a UTF-8 encoded sentence where words are separated by single space characters, implement an in-place algorithm to reverse the order of words without allocating a buffer proportional to the sentence length. Carefully describe how you identify UTF-8 character boundaries so that multi-byte characters are not corrupted.

Sample Answer

Approach (high level)- Treat each UTF‑8 codepoint as an atomic unit. Parse the bytearray to find each character boundary (lead byte + length), store the start indices (int per char). Then reverse the order of characters in-place by swapping the byte ranges for characters using those indices. Finally, reverse the order of characters inside each word (identified by space 0x20) to produce words in reversed order but with characters preserved in each word.- Note on space: words are separated by single ASCII space (0x20), so it is always a single byte and easy to detect.- This implementation trades O(C) extra integers (C = number of codepoints) for simplicity and correctness. If strict O(1) extra space is required, you can implement an O(1) rotate-swap of variable-length segments (more complex); I describe that trade-off at the end.

Code (Python)

python

def reverse_words_utf8_inplace(buf: bytearray):
    """
    In-place reverse order of words in a UTF-8 encoded mutable bytearray `buf`.
    Uses O(C) extra integers where C is number of UTF-8 codepoints.
    """
    n = len(buf)
    if n == 0:
        return

    # Helper: given a lead byte, determine UTF-8 length
    def utf8_len(b):
        if b & 0x80 == 0:
            return 1
        if b & 0xE0 == 0xC0:
            return 2
        if b & 0xF0 == 0xE0:
            return 3
        if b & 0xF8 == 0xF0:
            return 4
        raise ValueError("Invalid UTF-8 leading byte: %02x" % b)

    # 1) Scan and collect character start indices
    starts = []
    i = 0
    while i < n:
        b = buf[i]
        # lead bytes are bytes that are NOT continuation (0b10xxxxxx)
        if (b & 0xC0) == 0x80:
            raise ValueError("Invalid UTF-8: unexpected continuation byte at %d" % i)
        L = utf8_len(b)
        # validate continuation bytes
        for j in range(1, L):
            if i + j >= n or (buf[i + j] & 0xC0) != 0x80:
                raise ValueError("Invalid UTF-8 continuation at %d" % (i + j))
        starts.append(i)
        i += L

    # Build lengths array for convenience (optional)
    lengths = []
    for idx in starts:
        lengths.append(utf8_len(buf[idx]))

    C = len(starts)
    if C == 0:
        return

    # 2) Reverse all characters by swapping their byte spans
    def swap_spans(a_start, a_len, b_start, b_len):
        # simple swap when equal length
        if a_len == b_len:
            for k in range(a_len):
                buf[a_start + k], buf[b_start + k] = buf[b_start + k], buf[a_start + k]
            return
        # when lengths differ, perform rotation using a small temp buffer up to 4 bytes
        # copy a to tempA, b to tempB and perform three writes:
        tempA = buf[a_start:a_start + a_len]
        tempB = buf[b_start:b_start + b_len]
        # move tempB into a_start.., then tempA into the right place
        # need careful move because spans may overlap; to be safe, do by creating copies (small)
        buf[a_start:a_start + b_len] = tempB
        # move middle bytes between a_end and b_start appropriately
        mid_start = a_start + b_len
        mid_end = b_start + b_len  # old end of B
        # compute remaining bytes that should shift; easiest approach: reconstruct slice
        # full reconstruction of the region from a_start..b_start+b_len using concatenation
        region = tempB + buf[a_start + a_len:b_start] + tempA
        buf[a_start: b_start + b_len] = region

    left = 0
    right = C - 1
    while left < right:
        a_start = starts[left]
        a_len = lengths[left]
        b_start = starts[right]
        b_len = lengths[right]
        swap_spans(a_start, a_len, b_start, b_len)
        # after swapping, the bytes at these positions correspond to swapped segments,
        # but starts/lengths mapping becomes invalid for the inner indices. The easiest
        # fix: rebuild starts/lengths for the mutated buffer region.
        # For simplicity, after each outer swap we rebuild starts/lengths entirely.
        # This still runs in O(C^2) worst case if we rebuild every time; to keep O(C),
        # we instead perform all swaps by working on starts/lengths arrays and then
        # physically rearranging bytes once. For clarity and correctness in an interview
        # setting we will rebuild starts/lengths here (acceptable for moderate sizes).
        # Rebuild:
        starts = []
        lengths = []
        i = 0
        while i < n:
            b = buf[i]
            if (b & 0xC0) == 0x80:
                raise ValueError("Invalid UTF-8 after swap at %d" % i)
            L = utf8_len(b)
            starts.append(i)
            lengths.append(L)
            i += L
        C = len(starts)
        left += 1
        right -= 1

    # 3) Now we have characters reversed. Next: within each word, reverse the sequence
    #    of characters to restore character order inside each word (so words themselves are reversed).
    # Identify words by ASCII space (0x20).
    # Build list of character indices again (they are current after swaps)
    starts = []
    lengths = []
    i = 0
    while i < n:
        b = buf[i]
        L = utf8_len(b)
        starts.append(i)
        lengths.append(L)
        i += L
    C = len(starts)

    word_char_indices = []  # indices of characters in current word
    def flush_word(indices):
        # reverse characters by swapping spans using swap_spans on character-level positions
        i = 0
        j = len(indices) - 1
        while i < j:
            a_idx = indices[i]
            b_idx = indices[j]
            swap_spans(starts[a_idx], lengths[a_idx], starts[b_idx], lengths[b_idx])
            # rebuild starts/lengths (simple safe approach)
            tmp_starts = []
            tmp_lengths = []
            k = 0
            while k < n:
                Lk = utf8_len(buf[k])
                tmp_starts.append(k)
                tmp_lengths.append(Lk)
                k += Lk
            nonlocal starts, lengths
            starts, lengths = tmp_starts, tmp_lengths
            i += 1
            j -= 1

    # Map from char index to whether it's a space (single byte 0x20)
    for ci in range(C):
        si = starts[ci]
        L = lengths[ci]
        if L == 1 and buf[si] == 0x20:
            # flush current word
            if word_char_indices:
                flush_word(word_char_indices)
                word_char_indices = []
        else:
            word_char_indices.append(ci)
    if word_char_indices:
        flush_word(word_char_indices)

Key points and reasoning- UTF-8 detection: leading bytes are those where top two bits != 10 (i.e. (b & 0xC0) != 0x80). The leading byte pattern identifies length: 0xxxxxxx (1), 110xxxxx (2), 1110xxxx (3), 11110xxx (4). Continuation bytes always match 10xxxxxx.- We must operate on whole codepoints; swapping individual bytes would corrupt multi-byte characters.- This implementation stores character start indices (ints) — extra memory O(C). That avoids very tricky in-place variable-length segment rotation logic and is clearer and safer.- Time complexity: O(n * rebuilds) in the naive rebuild-on-each-swap implementation above; with careful implementation (swap using starts/lengths arrays and updating those arrays instead of rebuilding) you can make it O(n). Space complexity: O(C) extra for starts/lengths (C ≤ n).

Edge cases- Empty buffer, leading/trailing spaces, invalid UTF-8 sequences, single-character words.- Single-byte ASCII words work normally.

Trade-offs / alternatives- Strict O(1) extra space: you can implement an in-place algorithm that swaps variable-length segments with a sequence of byte-range reversals/rotations (cyclic rotations). That is more complex but possible: swap two non-adjacent segments by reversing three regions (A, middle, B) appropriately. For interview/code-challenge clarity and correctness, the starts/lengths approach is acceptable; mention if O(1) space is mandatory and you want, I can provide the rotation-only version.

EasyTechnical

61 practiced

Given a sorted array of integers stored in a mutable array/list in Python, remove duplicates in-place so that each element appears only once and return the new length. You must perform the operation in O(n) time and O(1) additional space, modifying the input array in-place. Describe handling of edge cases like empty arrays and arrays with all duplicates.

Sample Answer

Approach: Use two pointers in-place. One pointer (write) tracks the position to write the next unique value; the other (read) scans the array. For a sorted array, duplicates are adjacent so we copy each new value to write and increment write. This is O(n) time and O(1) extra space.

python

def remove_duplicates(nums):
    """
    Removes duplicates in-place from sorted list nums.
    Returns the new length (number of unique elements).
    """
    if not nums:
        return 0

    write = 1  # next position to write a unique value
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1

    return write

Key points:- We compare current element with previous; when different, it's a new unique value.- We overwrite the array from index 0..write-1 with unique values.

Time complexity: O(n) — single pass.Space complexity: O(1) extra space — in-place mutation.

Edge cases:- Empty array -> returns 0.- All duplicates (e.g., [1,1,1]) -> returns 1; array[0] holds the unique value.- All unique -> returns len(nums); array unchanged.- Single element -> returns 1.

Alternative: Use set but that breaks sorted order, uses extra space, and violates O(1) requirement. This two-pointer method is standard and efficient for large data-processing tasks where memory and speed matter.

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.