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
62 practiced
Implement a Rabin-Karp rolling-hash based function in Python to find the first occurrence of a pattern in a text. Your implementation should compute rolling hashes in O(1) per step, handle collisions by verification, and work with Unicode by mapping codepoints to integers. Explain choice of base and modulus and how to reduce collision probability.
Sample Answer
Approach: use a polynomial rolling hash h(s) = sum_{i=0..m-1} s[i]*base^{m-1-i} mod mod. Precompute base^{m-1} to remove leading char in O(1) and update hash per step. On hash match, verify by direct string comparison to avoid false positives. Map Unicode by using ord().
python
def rabin_karp(text: str, pattern: str):
"""
Return index of first occurrence of pattern in text or -1.
Works with Unicode (uses ord), rolling hashes updated O(1) per step.
"""
if pattern == "":
return 0
n, m = len(text), len(pattern)
if m > n:
return -1
base = 257 # a prime > max small codepoint byte value
mod = 2**61 - 1 # large Mersenne-like prime for 64-bit safe ops
def modmul(a, b):
# 64-bit friendly multiplication mod (2^61-1)
return (a * b) % mod
# compute initial hashes
h_pat = 0
h_txt = 0
power = 1 # base^(m-1)
for i in range(m):
h_pat = (h_pat * base + ord(pattern[i])) % mod
h_txt = (h_txt * base + ord(text[i])) % mod
if i < m - 1:
power = (power * base) % mod
if h_pat == h_txt and text[:m] == pattern:
return 0
for i in range(1, n - m + 1):
# remove leading char, add trailing char
leading = (ord(text[i-1]) * power) % mod
h_txt = (h_txt - leading) % mod
h_txt = (h_txt * base + ord(text[i + m - 1])) % mod
if h_txt == h_pat:
if text[i:i+m] == pattern:
return i
return -1
Key choices:- base=257: small prime > typical byte values reduces collisions and distributes values well.- mod=2**61-1: large prime avoids overflow and keeps collision probability ~1/mod.Reduce collisions: use large random base (or randomize base per run), large prime modulus, and always verify matches by direct comparison. Time: expected O(n + m), hash updates O(1); Space: O(1). Edge cases: empty pattern, pattern longer than text, Unicode combining characters (consider normalization if intended).
EasyTechnical
53 practiced
In C, implement a routine that replaces all spaces in a fixed-size character buffer with '%20' in place, given the true length of the string and enough buffer capacity. This is the classic URL-encode-in-place task often used in tight-memory systems. Carefully describe how you compute the new length and perform the copy safely.
Sample Answer
Approach: count spaces in the true string length, compute new length = true_len + 2 * space_count (since each space becomes 3 chars '%','2','0' replacing 1), check buffer capacity, then copy characters from end to end moving backward to avoid overwrite.
c
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#include <stdbool.h>
/* Modify buffer in-place: replace ' ' with "%20'.
* buffer: char array with total capacity buf_capacity (including space for '\0')
* true_len: length of meaningful characters in buffer (not including any trailing padding)
* Returns true on success, false if capacity insufficient.
*/
bool url_encode_spaces(char *buffer, size_t true_len, size_t buf_capacity) {
if (!buffer) return false;
size_t space_count = 0;
for (size_t i = 0; i < true_len; ++i)
if (buffer[i] == ' ') ++space_count;
size_t new_len = true_len + space_count * 2; // each space adds 2 more chars
if (new_len + 1 > buf_capacity) return false; // +1 for null terminator
// work backwards
size_t read = true_len;
size_t write = new_len;
buffer[write] = '\0';
while (read > 0) {
--read;
if (buffer[read] == ' ') {
buffer[--write] = '0';
buffer[--write] = '2';
buffer[--write] = '%';
} else {
buffer[--write] = buffer[read];
}
}
return true;
}
Key points:- Compute new length precisely: new_len = true_len + 2 * (number of spaces).- Backward copy avoids overwriting source data.- Check capacity before modifying.Time: O(n), Space: O(1) extra.Edge cases: no spaces, all spaces, true_len=0, insufficient capacity, non-ASCII chars treated as bytes.
EasyTechnical
54 practiced
Write a Python function that receives a Unicode string and returns the k most frequent characters (or codepoints) with their counts. Your solution should do a single pass over the data and be streaming friendly (constant memory relative to input size except for the output). Explain trade-offs when k is large and how you'd approximate when memory is constrained.
Sample Answer
Approach: use the Misra–Gries / "space-saving" algorithm: keep at most k counters for distinct codepoints while streaming the string once. It guarantees exact counts for items that remain in the top-k heavy hitters above certain frequency thresholds; uses O(k) memory (independent of input length). If exact full counts are required and k is large (≈ number of unique codepoints), you must store all unique items which costs O(u) memory (u = unique codepoints).Code (single-pass, streaming-friendly, Unicode-safe):
python
from typing import List, Tuple
def top_k_unicode(stream: str, k: int) -> List[Tuple[str,int]]:
"""
Single-pass streaming top-k heavy hitters using Misra-Gries.
Returns up to k (codepoint, count_estimate) pairs.
"""
if k <= 0:
return []
counters = {} # codepoint -> count
for ch in stream:
if ch in counters:
counters[ch] += 1
elif len(counters) < k:
counters[ch] = 1
else:
# decrement all; remove zeros
to_delete = []
for key in list(counters.keys()):
counters[key] -= 1
if counters[key] == 0:
to_delete.append(key)
for key in to_delete:
del counters[key]
# counters contain approximate counts (lower bounds). To improve accuracy,
# a second pass with exact counting for candidates is typical; here we return estimates.
return sorted(counters.items(), key=lambda x: -x[1])[:k]
Key points:- Single pass, O(k) memory, O(n * k) worst-case time if decrement loop always iterates k (but in practice average is much lower). Can optimize with linked structures/heap for lower overhead.- Returned counts are lower-bound estimates; to get exact top-k you can, after collecting candidates, do a second pass to compute exact counts for only those candidates (still streaming-friendly if you can re-scan or store candidate set).Trade-offs when k is large:- If k approaches the number of unique codepoints, O(k) ≈ O(u) memory — no savings. Then you must either allocate more memory or accept approximations.Approximation under tight memory:- Use Count–Min Sketch for fixed small memory and tunable error (probabilistic overestimates).- Use sampling or lossy counting variants; Count–Min + top-k candidate extraction is common.Edge cases:- Empty string, k <= 0 handled.- Unicode combining characters: this treats Python codepoints (not grapheme clusters); if grapheme-level is needed, preprocess with a grapheme splitter (e.g., regex or the `grapheme` library).
HardTechnical
58 practiced
Explain suffix arrays and how to construct them (e.g., prefix-doubling algorithm) and how to compute the LCP array. Then describe how to use SA + LCP to compute the number of distinct substrings in O(n log n) or O(n) time. Provide high-level pseudocode and complexity analysis.
Sample Answer
Suffix array (SA) is the array of start indices of all suffixes of string S sorted lexicographically. LCP[i] is the longest common prefix length between suffixes SA[i] and SA[i-1]. These two structures enable many substring queries; in particular number of distinct substrings = total substrings − sum(LCP) = n*(n+1)/2 − sum(LCP).Prefix-doubling construction (O(n log n)):1. Initially sort suffixes by first character → assign rank[i].2. For k = 1,2,4,... while k < n: sort suffixes by pair (rank[i], rank[i+k]) using counting/radix sort (stable) → reassign ranks; stop when ranks are all distinct.This yields O(n log n) time (log n rounds, each round O(n) with radix counting).Pseudocode (high-level):
python
def build_SA(s):
n = len(s)
rank = [ord(c) for c in s] + [-1]
sa = list(range(n))
k = 1
while k < n:
sa.sort(key=lambda i: (rank[i], rank[i+k] if i+k<n else -1)) # use radix for O(n)
tmp = [0]*n
for i in range(1,n):
prev, cur = sa[i-1], sa[i]
tmp[cur] = tmp[prev] + ( (rank[cur], rank[cur+k] if cur+k<n else -1) != (rank[prev], rank[prev+k] if prev+k<n else -1) )
rank = tmp
if max(rank)==n-1: break
k <<= 1
return sa
LCP via Kasai (O(n)):- Build inverse SA: pos[sa[i]] = i.- Iterate i=0..n-1, maintain h = max(h-1,0). If pos[i]==0 set LCP[pos[i]]=0 else compare characters starting at i+h and sa[pos[i]-1]+h, increment h while equal, set LCP[pos[i]] = h.Pseudocode:
python
def build_LCP(s, sa):
n = len(s)
pos = [0]*n
for i in range(n): pos[sa[i]]=i
lcp=[0]*n
h=0
for i in range(n):
if pos[i]==0: continue
j = sa[pos[i]-1]
while i+h < n and j+h < n and s[i+h]==s[j+h]: h+=1
lcp[pos[i]] = h
if h>0: h-=1
return lcp
Distinct substrings:- total = n*(n+1)//2- distinct = total - sum(lcp)Complexity:- Prefix-doubling with radix sort: O(n log n) time, O(n) space.- Kasai LCP: O(n) time, O(n) space.- Overall distinct substrings computation: O(n log n) dominated by SA, or O(n) if you build SA with linear algorithms (SA-IS) and then Kasai → overall O(n).Edge cases:- Empty string (0).- Repeated characters (LCP large).Notes:- For practice implement radix counting for pairs to ensure O(n) per round; for production use SA-IS for linear SA.
EasyTechnical
48 practiced
Given a sorted list of integers and a target integer, implement an O(n) time, O(1) extra space function in Python that returns a pair of indices (i, j) such that nums[i] + nums[j] == target. If no such pair exists, return (-1, -1). Provide example input/output and explain edge cases (duplicates, negative numbers).
Sample Answer
Use the two-pointer technique: start one pointer at the left (i=0) and one at the right (j=len(nums)-1). Move pointers inward — if sum < target, increment left; if sum > target, decrement right. Because the list is sorted this finds a valid pair in O(n) time using O(1) extra space.
python
def two_sum_sorted(nums, target):
"""
nums: sorted list of integers
target: integer
Returns a tuple (i, j) with i < j such that nums[i] + nums[j] == target,
or (-1, -1) if no such pair exists.
"""
i, j = 0, len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == target:
return (i, j)
elif s < target:
i += 1
else:
j -= 1
return (-1, -1)
Example:- Input: nums = [-3, -1, 0, 2, 4, 5], target = 1- Output: (1, 4) because -1 + 2? (correct is -1 + 2 = 1) — actually indexes (1,3). Using the function returns (1,3).Time complexity: O(n) — each pointer moves at most n steps. Space complexity: O(1) extra space.Edge cases:- Empty or single-element list → returns (-1, -1).- Duplicates: handled naturally (e.g., nums=[1,1,2], target=2 returns (0,1)).- Negative numbers: handled because order and comparisons still hold.- Multiple valid pairs: returns the first found by the pointer strategy (not necessarily unique).
Unlock Full Question Bank
Get access to hundreds of Array and String Manipulation interview questions and detailed answers.
