Arrays, Strings, and Linked Lists Mastery Questions

Foundational data structures: arrays, strings, and linked lists. Covers core operations (insertion, deletion, traversal, searching), pattern usage, edge cases, and time/space complexity analysis, with a focus on practical implementation and common interview-style problems across mainstream programming languages.

MediumTechnical

33 practiced

Given an array of k sorted linked lists, implement mergeKLists(lists) in Java to merge them into one sorted linked list. Discuss possible approaches: iteratively merging pairs, divide-and-conquer, and using a min-heap (priority queue). Analyze time and space complexity of each approach and choose the best for large k.

Sample Answer

To merge k sorted linked lists, three common approaches are: iterative pairwise merging, divide-and-conquer, and using a min-heap (priority queue). Best choice for large k is the min-heap or divide-and-conquer; min-heap is simplest and provides O(N log k) time with good space behavior.

Approach summary and complexity:- Iterative pairwise merging (merge lists one by one): - Repeatedly merge result with next list using two-pointer merge. - Time: O(kN) in worst case (N = total number of nodes), because each merge may touch many nodes repeatedly. - Space: O(1) extra (in-place merges) besides output. - Not ideal when k is large.

- Divide-and-conquer: - Recursively merge pairs of lists (like merge sort). Merge lists in pairs, halving k each round. - Time: O(N log k) — each node participates in log k merges. - Space: O(1) extra (or O(log k) recursion stack). - Good for large k; simple and efficient.

- Min-heap (priority queue): - Put head of each non-empty list into a min-heap keyed by node value; repeatedly pop smallest and push its next. - Time: O(N log k) — each of N nodes pushed/popped once with heap size <= k. - Space: O(k) heap. - Best practical choice for large k when k fits memory; easy to implement.

Java implementation using PriorityQueue:

java

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Min-heap comparing nodes by value
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        // Initialize heap with first node of each non-empty list
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!pq.isEmpty()) {
            ListNode smallest = pq.poll();
            tail.next = smallest;
            tail = tail.next;
            if (smallest.next != null) {
                pq.offer(smallest.next);
            }
        }

        return dummy.next;
    }
}

Key points and edge cases:- Handles empty input and null lists.- Works with duplicate values.- For extremely large k where O(k) extra memory is problematic, divide-and-conquer uses less extra memory (only recursion stack) and is preferred.- If lists are very imbalanced (one huge, many tiny), complexities remain the same asymptotically; heap performs well in practice.

Recommendation: For large k and typical memory availability, use the min-heap for simplicity and performance (O(N log k)). If minimizing extra memory is critical, use divide-and-conquer.

EasyTechnical

46 practiced

Implement mergeSortedArrays(a, b) in C++ to merge two sorted integer arrays into a new sorted array and return it. Target O(n + m) time and O(n + m) space. Example: a = [1,3,5], b = [2,4] -> [1,2,3,4,5]. Discuss stability, handling duplicates, and behavior when one array is empty.

Sample Answer

Approach: Use two-pointer merge (like merge step in mergesort). Walk through both arrays, append the smaller current element to result, advance that pointer. When one array is exhausted, append remaining elements from the other. This is stable (preserves relative order for equal elements) and handles duplicates naturally.

cpp

#include <vector>

std::vector<int> mergeSortedArrays(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> res;
    res.reserve(a.size() + b.size()); // avoid reallocations

    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] <= b[j]) {      // <= ensures stability: elements from 'a' come before equal elements from 'b'
            res.push_back(a[i++]);
        } else {
            res.push_back(b[j++]);
        }
    }
    // append leftovers
    while (i < a.size()) res.push_back(a[i++]);
    while (j < b.size()) res.push_back(b[j++]);

    return res;
}

Key points:- Stability: Using <= places equal values from 'a' before those from 'b', preserving input order.- Duplicates: Preserved and included; no special handling required.- Empty arrays: If one input is empty, function returns a copy of the non-empty array (or empty if both empty).

Complexity:- Time: O(n + m) where n = a.size(), m = b.size()- Space: O(n + m) for the result vector

Edge cases:- Both empty -> empty result- One empty -> copy of the other- Arrays with large sizes -> reserve avoids repeated reallocations- Negative numbers and duplicates are handled correctly.

EasyTechnical

27 practiced

Implement reverse_array(arr) in Python that reverses an array of integers in-place without allocating another array. Constraints: O(n) time, O(1) extra space. Example: Input: arr = [1, 2, 3, 4, 5] -> Output: [5, 4, 3, 2, 1]. Describe behavior for empty arrays, arrays with one element, and odd/even lengths. Discuss time/space complexity and write brief tests.

Sample Answer

To reverse an array in-place, use the two-pointer technique: swap elements from the ends moving towards the center. This meets O(n) time and O(1) extra space.

python

def reverse_array(arr):
    """
    Reverse list arr in-place.
    Returns the same list object for convenience.
    """
    left, right = 0, len(arr) - 1
    while left < right:
        # swap arr[left] and arr[right]
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# brief tests
if __name__ == "__main__":
    assert reverse_array([]) == []                # empty array
    assert reverse_array([1]) == [1]              # single element
    assert reverse_array([1,2]) == [2,1]          # even length
    assert reverse_array([1,2,3]) == [3,2,1]      # odd length
    assert reverse_array([1,2,3,4,5]) == [5,4,3,2,1]
    print("All tests passed")

Key points:- Empty array: loop doesn't run; function returns [].- Single element: left == right, no swaps; returns same array.- Even lengths: all pairs swapped.- Odd lengths: middle element stays in place.

Time complexity: O(n) — each element swapped at most once. Space complexity: O(1) extra space — only two index variables.

EasyTechnical

27 practiced

Implement stringToInt(str) in Java (similar to atoi). Parse leading whitespace, optional '+' or '-', then digit sequence. Stop at first non-digit. Clamp results to 32-bit signed integer range on overflow. Example: ' -42' -> -42, '4193 with words' -> 4193, '2147483648' -> 2147483647. Discuss edge cases and time complexity.

Sample Answer

Approach: Scan the string left-to-right. Skip leading whitespace, read optional '+' or '-' sign, then accumulate digits. To avoid overflow, check before multiplying/adding by comparing with Integer.MAX_VALUE/10 and remainder. If overflow would occur, return clamped value.

java

public class Solution {
    public static int stringToInt(String s) {
        if (s == null || s.isEmpty()) return 0;
        int i = 0, n = s.length();
        // skip leading whitespace
        while (i < n && Character.isWhitespace(s.charAt(i))) i++;
        if (i == n) return 0;

        // sign
        int sign = 1;
        char c = s.charAt(i);
        if (c == '+' || c == '-') {
            sign = (c == '-') ? -1 : 1;
            i++;
        }

        long result = 0; // use long to simplify but still check bounds
        while (i < n) {
            c = s.charAt(i);
            if (c < '0' || c > '9') break;
            int digit = c - '0';

            // check overflow before adding digit
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + digit;
            i++;
        }
        return (int) (sign * result);
    }
}

Key points:- Handles leading spaces and optional sign.- Stops at first non-digit.- Pre-check prevents overflow and returns INT_MAX/INT_MIN.- Uses long for accumulation but still checks bounds.

Time complexity: O(n) single pass. Space complexity: O(1).

Edge cases:- Empty or all-whitespace -> 0- Only sign with no digits -> 0- Leading zeros -> handled- Very long digit sequence -> clamped- Non-digit first non-space char -> 0 (e.g., "words123")

MediumTechnical

31 practiced

Given singly linked list L: L0->L1->...->Ln, implement reorderList(head) in C++ to transform it to L0->Ln->L1->Ln-1->... in-place without changing node values and using O(1) extra memory. Explain steps: find middle, reverse second half, merge halves and discuss correctness and complexity.

Sample Answer

Approach (brief): Split the list into two halves with slow/fast pointers, reverse the second half in-place, then merge nodes alternately from the first and reversed-second halves. This achieves L0→Ln→L1→Ln-1… in O(n) time and O(1) extra space.

cpp

#include <cstddef>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr) {}
};

void reorderList(ListNode* head) {
    if (!head || !head->next) return;

    // 1) Find middle (end of first half)
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2) Reverse second half
    ListNode* prev = nullptr;
    ListNode* cur = slow->next;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    slow->next = nullptr; // split lists

    // 3) Merge alternatingly
    ListNode* l1 = head;
    ListNode* l2 = prev; // head of reversed second half
    while (l2) {
        ListNode* n1 = l1->next;
        ListNode* n2 = l2->next;
        l1->next = l2;
        l2->next = n1;
        l1 = n1;
        l2 = n2;
    }
}

Key points and correctness:- Finding middle using slow/fast puts slow at first-half end (for both even/odd lengths).- Reversing the second half in-place preserves nodes and uses O(1) extra space.- Merging alternately reconstructs desired ordering; splitting first half prevents cycles.- The algorithm processes each node a constant number of times, so it's correct by construction.

Complexity:- Time: O(n) (one pass to find middle, one to reverse, one to merge).- Space: O(1) extra memory (in-place).

Edge cases:- Empty list or single node — no changes.- Two nodes — handled by merge.- Odd length — first half is one node longer; split and merge logic handles it.

Unlock Full Question Bank

Get access to hundreds of Arrays, Strings, and Linked Lists Mastery interview questions and detailed answers.

Join thousands of developers preparing for their dream job.