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
61 practiced
Move all zeros in an integer array to the end while maintaining the relative order of non-zero elements. Do this in-place with O(1) extra space. Example: nums=[0,1,0,3,12] -> [1,3,12,0,0]. Provide code and complexity analysis.
Sample Answer
To solve this in-place with O(1) extra space and maintain order, use two pointers: a slow pointer to place the next non-zero, and a fast pointer to scan the array. When fast finds a non-zero, write it to slow and increment slow. After the pass, fill remaining positions with zeros.
python
def move_zeroes(nums):
"""
Move all zeros in nums to the end in-place, preserving order of non-zero elements.
"""
n = len(nums)
slow = 0 # position to place next non-zero
for fast in range(n):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
# fill remaining slots with zeros
for i in range(slow, n):
nums[i] = 0
# Example
arr = [0,1,0,3,12]
move_zeroes(arr)
print(arr) # -> [1,3,12,0,0]
Key points:- Maintains relative order because we copy non-zeros in encountered order.- In-place: only constant extra variables used.Time Complexity: O(n) — single scan plus filling (both O(n)).Space Complexity: O(1) extra space.Edge cases:- All zeros (result unchanged).- No zeros (array unchanged).- Empty array (handles normally).- Large arrays: algorithm still linear.Alternative: swap when fast finds non-zero with slow to avoid second loop:
python
# alternative swapping approach
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
This preserves order as long as slow <= fast and moves zeros right as you go.
HardTechnical
59 practiced
Given a string representing a mathematical expression containing non-negative integers, +, -, *, /, parentheses, and spaces, parse and evaluate it correctly honoring operator precedence and parentheses. For simplicity assume integer division truncates toward zero. Provide an implementation and discuss stack-based parsing vs recursive descent approaches.
Sample Answer
Approach: Use a recursive-descent parser that respects precedence by splitting parsing into factor (numbers, parenthesis, unary +/-), term (*,/), and expression (+,-). Recursive descent is concise and clear for this grammar; stack-based (shunting-yard or two-stack) is iterative and good for streaming or when avoiding recursion.
python
def evaluate(s: str) -> int:
"""
Parse and evaluate an expression with +,-,*,/, parentheses.
Integer division truncates toward zero.
"""
i = 0
n = len(s)
def next_char():
nonlocal i
while i < n and s[i] == ' ':
i += 1
return s[i] if i < n else None
def parse_number():
nonlocal i
while i < n and s[i] == ' ':
i += 1
sign = 1
if i < n and s[i] in '+-': # allow unary signs in number parsing
if s[i] == '-':
sign = -1
i += 1
while i < n and s[i] == ' ':
i += 1
if i >= n or not s[i].isdigit():
# not a raw number, roll back sign to caller (handled in factor)
i -= 1 if sign == -1 else 1 if sign == 1 and s[i-1] in '+-' else 0
num = 0
started = False
while i < n and s[i].isdigit():
started = True
num = num * 10 + (ord(s[i]) - 48)
i += 1
return sign * num if started else None
def parse_factor():
nonlocal i
while i < n and s[i] == ' ':
i += 1
ch = next_char()
if ch == '(':
i += 1 # consume '('
val = parse_expr()
while i < n and s[i] == ' ':
i += 1
if i < n and s[i] == ')':
i += 1
return val
# handle unary +/-
if ch in '+-':
sign = 1
if ch == '-':
sign = -1
i += 1
val = parse_factor()
return sign * val
# number
num = 0
started = False
while i < n and s[i] == ' ':
i += 1
while i < n and s[i].isdigit():
started = True
num = num * 10 + (ord(s[i]) - 48)
i += 1
if not started:
return 0
return num
def parse_term():
val = parse_factor()
while True:
while i < n and s[i] == ' ':
i += 1
if i < n and s[i] in '*/':
op = s[i]; i += 1
rhs = parse_factor()
if op == '*':
val = val * rhs
else:
# truncate toward zero
val = int(val / rhs)
else:
break
return val
def parse_expr():
val = parse_term()
while True:
while i < n and s[i] == ' ':
i += 1
if i < n and s[i] in '+-':
op = s[i]; i += 1
rhs = parse_term()
if op == '+':
val = val + rhs
else:
val = val - rhs
else:
break
return val
return parse_expr()
Key points:- parse_factor handles parentheses and unary +/-.- parse_term handles * and / (higher precedence).- parse_expr handles + and -.Complexity: O(n) time, O(depth) recursion space (depth = parenthesis nesting). Edge cases: spaces, unary operators, division by zero (raises), large integers. Stack-based (shunting-yard) is iterative and easier to convert to RPN for evaluation; recursive descent maps naturally to grammar, is more readable, but uses call stack which may overflow on extremely deep nesting.
EasyTechnical
48 practiced
Implement twoSum(nums, target): given an array of integers and a target, return indices of the two numbers such that they add up to target. You may assume each input has exactly one solution and you may not use the same element twice. Provide code (Python/Java/C++), discuss time/space complexity, and consider large arrays where performance matters.
Sample Answer
Approach: Use a single-pass hash map mapping value → index. For each number x at index i, compute complement = target - x. If complement is already in map, return [map[complement], i]. Otherwise store x→i. This is O(n) time and O(n) space, optimal for large arrays.
python
def twoSum(nums, target):
"""
Returns indices of the two numbers that add up to target.
Assumes exactly one solution and indices are 0-based.
"""
seen = {} # value -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
raise ValueError("No two sum solution")
Key points:- Time complexity: O(n) — one pass through the array.- Space complexity: O(n) — hash map stores seen elements (worst-case).- Handles large arrays efficiently because lookups/inserts in a hash map are average O(1). For extremely large inputs, ensure enough memory; consider using integers-only optimized hash maps or streaming approaches if memory constrained.- Edge cases: duplicates (works because we store index), negative numbers, very large/small integers. Validate input length < 2.
HardSystem Design
48 practiced
Given a massive text file of newline-separated words (billions), design an algorithm to group words into anagram buckets (words that are anagrams of each other). Discuss storage, hashing strategies, external sort or shuffle strategies, and how to produce the top-k largest anagram groups. Consider memory and distributed processing constraints.
Sample Answer
Requirements & constraints:- Input: billions of newline-separated words (too big for one machine).- Output: buckets of anagrams; ability to list top-k largest buckets.- Non-functional: limited memory per node, distributed processing, reasonable latency.High-level approach:Use a distributed shuffle (MapReduce/Spark) or external-sort pipeline that maps each word to a canonical key (sorted letters) and groups by that key, then counts and emits groups.Design:1. Canonical key:- Key = characters of word sorted (e.g., "listen" -> "eilnst"). For long alphabets, consider frequency-encoded signature (26 counts for lowercase: a#1|b#0|...).- Use stable canonicalization to ensure identical keys.2. Map phase (streaming, memory-light):- Read file in chunks. For each word, compute key and emit (key, word) or (key, 1) + store word if you need full group contents.- To save network, emit (key, word) only if group sizes expected small; otherwise emit (key,1) in counting pass and collect group ids later.3. Partitioning & hashing:- Use a hash(key) modulo R to partition keys across reducers. Use a consistent hash or range partition to balance load.- For skewed keys (common anagrams like "eat" variations), detect heavy keys via sampling; route heavy keys to dedicated reducers or use combiners to pre-aggregate.4. Shuffle / External grouping:- Reducers receive all records for assigned keys. If a reducer’s incoming data exceeds memory, perform external merge: write intermediate files partitioned by key, sort by key on-disk, then stream-merge to group.- In Spark, use map-side combine and memory/tungsten spill tuning; in Hadoop, use combiners and increase reducers.5. Producing groups and top-k:Option A (two-pass):- Pass 1: MapReduce count: emit (key, count). Reducers compute counts and write (key, count).- Global top-k: run a second job that aggregates counts across reducers (each reducer keeps local top-k and a final reducer merges them).- Pass 2 (optional): For top-k selected keys, fetch full groups by re-running mapping to filter only keys in top-k and collecting words.Option B (single-pass with streaming top-k):- Each reducer computes its local top-k groups by count, emits to aggregator which merges to global top-k (k small so network cost tiny). To compute counts, reducers may stream and maintain counts in external store (e.g., RocksDB) if too large.Storage and durability:- Use HDFS/S3 for input and intermediate spills.- Use SSTable/embedded KV (RocksDB, LevelDB) on reducers for very large key spaces to avoid in-memory maps.- Compress intermediate data (Snappy) to reduce I/O.Skew handling:- Pre-sample input to find heavy keys.- Use key-salting: append random shard id to heavy keys in map phase, then in reduce combine partial aggregates.- Use elastic workers or dedicated "hot-key" nodes.Complexity & trade-offs:- Compute cost: key canonicalization O(L log L) per word for sorting letters; frequency-encoding O(L) reduces CPU for long words.- Network: bytes transferred proportional to size of input unless using combiners.- Storage: intermediate disk usage ~ input size (plus overhead). Two-pass increases IO but reduces memory.Edge cases:- Unicode and normalization: normalize (NFC) and case-fold.- Extremely long words: cap or stream signature.- Very small k: use efficient priority queues (min-heap).Example technologies:- Hadoop MapReduce or Spark for shuffle; use RocksDB on executors for spilling; HDFS/S3 for storage; Kafka if streaming continual updates.Summary:Canonicalize each word into a signature, partition by hash/signature, group via distributed shuffle with external merge on reducers, use combiners and sampling to handle skew, compute counts then merge local top-k into global top-k, and retrieve full groups for top-k if needed.
EasyTechnical
45 practiced
You have two sorted arrays nums1 and nums2, where nums1 has a buffer at the end large enough to hold nums2. Merge nums2 into nums1 in sorted order in-place. Provide the algorithm and code. Example: nums1=[1,2,3,0,0,0], m=3; nums2=[2,5,6], n=3 -> nums1 becomes [1,2,2,3,5,6].
Sample Answer
Approach:Use three pointers from the end to merge in-place: p1 at m-1 (end of valid nums1), p2 at n-1 (end of nums2), and write at write = m+n-1. Compare nums1[p1] and nums2[p2], place the larger at write, decrement pointers. When p2 exhausts we're done; if p1 exhausts, copy remaining nums2 elements.Python implementation:
python
def merge(nums1, m, nums2, n):
"""
Merge nums2 into nums1 in-place.
"""
p1, p2, write = m - 1, n - 1, m + n - 1
while p2 >= 0:
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]
p1 -= 1
else:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1
Java implementation:
java
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1, write = m + n - 1;
while (p2 >= 0) {
if (p1 >= 0 && nums1[p1] > nums2[p2]) {
nums1[write--] = nums1[p1--];
} else {
nums1[write--] = nums2[p2--];
}
}
}
Key points:- Works in-place, no extra array.- Time Complexity: O(m + n) — each element moved at most once.- Space Complexity: O(1).Edge cases:- n == 0 (nothing to do).- m == 0 (copy all nums2 into nums1).- Duplicates and negative numbers handled naturally.
Unlock Full Question Bank
Get access to hundreds of Array and String Manipulation interview questions and detailed answers.
