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
80 practiced
Implement the Levenshtein edit distance in Python for two strings a and b using dynamic programming (O(nm) time, O(min(n,m)) space). Then explain how you would optimize for the case where the distance is known to be small (k), or how to apply banded DP to reduce time/space.
Sample Answer
To compute Levenshtein distance with O(nm) time and O(min(n,m)) space, use dynamic programming with two rolling rows (shorter string across columns). Below is a compact, commented Python implementation plus an explanation of banded DP / k-optimization.
python
def levenshtein(a: str, b: str) -> int:
# ensure b is the shorter to use O(min(n,m)) space
if len(a) < len(b):
a, b = b, a
n, m = len(a), len(b)
# previous row: distances from empty prefix of a to prefixes of b
prev = list(range(m + 1))
for i in range(1, n + 1):
cur = [i] + [0] * m
ai = a[i - 1]
for j in range(1, m + 1):
cost = 0 if ai == b[j - 1] else 1
cur[j] = min(
prev[j] + 1, # deletion
cur[j - 1] + 1, # insertion
prev[j - 1] + cost # substitution
)
prev = cur
return prev[m]
Key points:- Time: O(n*m). Space: O(min(n,m)) because we only store two rows with length m+1.- Handles empty strings, identical strings, and varying lengths.Optimizing when distance ≤ k (banded DP):- Only cells with |i - j| ≤ k can be ≤ k; compute DP in a diagonal band of width 2k+1.- For each i, iterate j from max(1, i-k) to min(m, i+k), initialize unreachable cells to >k or inf.- Time becomes O(k * n) and space O(k) (or O(min(n,m,k))): much faster when k ≪ min(n,m).- Also useful: early exit if entire row values > k (distance > k), or use Ukkonen’s algorithm for iterative widening of k.Edge cases:- Large k ~ min(n,m): falls back to full DP.- Unicode / byte vs char differences: ensure consistent indexing.- Memory/cell initialization for band boundaries must treat out-of-band as INF.
MediumTechnical
48 practiced
Write an implementation of Kadane's algorithm in Python that returns both the maximum subarray sum and the start/end indices of that subarray. Explain edge cases (all negative numbers) and how you'd modify the approach to return the maximum subarray product instead.
Sample Answer
To solve this, use Kadane’s algorithm tracking the best sum seen so far and the current running sum with start/end indices. Handle the all-negative case by allowing resets only when current sum drops below 0 but still track the maximum single element.
python
def kadane_with_indices(arr):
"""
Returns (max_sum, start_index, end_index).
Works for arrays of ints/floats, including all-negative arrays.
"""
if not arr:
raise ValueError("arr must be non-empty")
max_sum = cur_sum = arr[0]
max_start = max_end = cur_start = 0
for i in range(1, len(arr)):
x = arr[i]
# If extending is worse than starting new at x, start new
if cur_sum + x < x:
cur_sum = x
cur_start = i
else:
cur_sum += x
# Update global max and indices
if cur_sum > max_sum:
max_sum = cur_sum
max_start = cur_start
max_end = i
return max_sum, max_start, max_end
Key points:- Time O(n), Space O(1).- Edge case: all negatives — algorithm still returns the largest (least negative) element because we initialize with arr[0] and only update when cur_sum > max_sum.- If you need an empty-subarray allowed (sum 0), adjust initialization and reset rule.To modify for maximum subarray product:- You must track both current maximum product and current minimum product at each step because a negative number can flip signs.- Recurrence: new_max = max(x, x*cur_max, x*cur_min); new_min = min(x, x*cur_max, x*cur_min). Also track indices carefully by remembering when you start a new product sequence and updating start/end when new_max changes. Complexity remains O(n), space O(1).
EasyTechnical
52 practiced
Given an array of integers that may contain negative numbers, write a function in your favorite language to return the element that appears most frequently. Discuss how you would adapt this when the array is extremely large or when elements are streaming (cannot store counts for all unique values).
Sample Answer
Approach: For a finite array, the simplest correct solution is to count frequencies with a hash map and return the key with max count. For very large or streaming data where you cannot store counts for every unique value, use streaming heavy-hitter algorithms (Misra–Gries / Space-Saving for approximate top-k) or probabilistic sketches (Count–Min Sketch) to estimate frequencies with bounded memory.
python
from collections import defaultdict
def most_frequent(nums):
"""Return one element with highest frequency (mode)."""
if not nums:
return None
freq = defaultdict(int)
best, best_count = None, 0
for x in nums:
freq[x] += 1
if freq[x] > best_count:
best, best_count = x, freq[x]
return best
# Example:
# print(most_frequent([1, -1, 2, 1, 2, 1])) # -> 1
Key points and complexity:- Uses hashing: O(n) time, O(u) space (u = unique elements).- Edge cases: empty array -> return None (or raise), ties -> returns first encountered max.Streaming / extremely large:- Misra–Gries (Space-Saving) keeps k counters; it finds all items with frequency > n/(k+1) exactly and approximates others. Use when you need top-k heavy hitters with bounded memory.- Count–Min Sketch gives approximate counts with tunable error and is good when you need frequency estimates but can tolerate overestimation.Trade-offs: sketches sacrifice exactness for fixed low memory; Space-Saving gives better top-k accuracy but still approximate for tail items. Choose based on accuracy vs memory constraints.
HardTechnical
50 practiced
Two large sorted arrays are located on separate machines. Describe an algorithm to find the global median (median of the union) minimizing network I/O and number of rounds of communication. Assume arrays sizes are m and n and both are too large to transfer entirely. Explain complexity and handling of duplicates.
Sample Answer
Approach (goal: find the median of A (size m) and B (size n) without shipping arrays): reduce to finding the k-th smallest where k = (m + n + 1) // 2. Perform a distributed binary-search-style selection with O(log min(m,n)) rounds and minimal bytes transferred.Algorithm (high level):1. Let A be the smaller array (swap if necessary). We will binary-search an index i in A (0..m).2. In each round the coordinator (or machine holding A) picks i = (lo+hi)//2 and sends (i, A[i]) to the other machine.3. The other machine replies with cnt = number of elements in B <= A[i] (computed locally by binary search) and optionally B_left = B[cnt-1] and B_right = B[cnt] (if needed).4. Using cnt we can determine rank r = i + 1 + cnt (1-based rank of A[i] in union). If r == k, A[i] is the median. If r < k, we need larger elements → set lo = i+1. If r > k, set hi = i-1.5. Continue until you locate the k-th element; if binary search in A exhausts possibilities, derive k-th from B locally (the machine holding B can return the (k - countA)th element).Communication pattern and I/O:- Each round sends one index and one numeric value (A[i]) and receives one integer cnt and maybe two neighbor values. So per round O(1) words.- Number of rounds: O(log m) = O(log min(m,n)).- Total network I/O: O(log min(m,n)) words (not O(m+n)), minimal for large arrays.Local computation:- Each machine performs local binary search to compute counts: O(log m) or O(log n) per round.- Total local time: O(log m * log n) in worst messaging interplay, but each round is cheap.Handling duplicates:- Use <= when counting elements in B to compute rank; this properly accounts for duplicates.- If multiple equal values straddle the k-th position, the algorithm still finds a correct k-th element; for median you may need average of two middle values when (m+n) even—retrieve both k and k+1 with at most one extra round (ask for neighbor values from the machine that provided the found element).Edge cases and notes:- If arrays are very unbalanced, binary-search the smaller array to minimize rounds.- If values are large objects, send only the necessary comparable key (e.g., numeric or hash) to reduce I/O.- If network latency dominates, you can pipeline multiple probe indices per round (batch queries) to reduce round-trips at cost of slightly more bytes.Why this is optimal-ish:- You need at least Ω(log min(m,n)) rounds in the comparison model to distinguish order statistics; this algorithm achieves that while transferring only O(log min(m,n)) words, far below transferring either array.
EasyTechnical
51 practiced
Write a Python function is_palindrome(s: str) -> bool that checks if a string is a palindrome ignoring non-alphanumeric characters and case. The function should run in O(n) time and O(1) extra space (excluding input). Mention how your approach treats Unicode letters and whether you would normalize first.
Sample Answer
Use a two-pointer approach scanning from both ends, skipping non-alphanumeric chars, comparing characters case-insensitively. This is O(n) time and O(1) extra space (in-place pointers). For Unicode, use str.isalnum() and .casefold(); if input may contain different Unicode compositions (e.g., "é" vs "é") normalize first with unicodedata.normalize (NFC or NFKC) — normalization costs O(n) time and O(n) extra space if you create a normalized string, but it ensures canonical equivalence.
python
import unicodedata
def is_palindrome(s: str, normalize_unicode: bool = True) -> bool:
"""
Check if s is palindrome ignoring non-alphanumeric chars and case.
normalize_unicode: if True, normalize to NFC before checking (recommended for robust Unicode handling).
"""
if normalize_unicode:
# NFC preserves composed characters; NFKC can also fold compatibility forms if desired
s = unicodedata.normalize("NFC", s)
i, j = 0, len(s) - 1
while i < j:
# advance i to next alnum
while i < j and not s[i].isalnum():
i += 1
# advance j to prev alnum
while i < j and not s[j].isalnum():
j -= 1
if i >= j:
break
# casefold for aggressive Unicode case-insensitive comparison
if s[i].casefold() != s[j].casefold():
return False
i += 1
j -= 1
return True
Key points:- Time: O(n) single pass.- Extra space: O(1) for pointers. Normalization creates a new string (O(n) space) if enabled.- Unicode: .isalnum() and .casefold() handle many Unicode cases; use unicodedata.normalize when inputs might use different compositions.
Unlock Full Question Bank
Get access to hundreds of Array and String Manipulation interview questions and detailed answers.
