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.
HardTechnical
63 practiced
Implement an algorithm to find the maximum sum submatrix in a 2D matrix (Kadane extension) for moderately sized inputs in JavaScript. Explain how you reduce the 2D problem to multiple 1D maximum subarray problems and the resulting time complexity. Discuss memory and performance considerations for large matrices in a browser.
Sample Answer
**Approach — reduce 2D to many 1D problems**- Fix left and right column bounds; for each pair collapse columns into a 1D array of row sums (sum of elements between left..right for each row). - Run 1D Kadane on that collapsed array to find max subarray (gives best top/bottom for this column span). - Track global max and coordinates.**Why it works**- Collapsing columns turns any submatrix (left..right, top..bottom) into a contiguous subarray of the row-sum vector. Enumerating left/right covers all column choices.**Time & space**- Time: O(cols^2 * rows) — for moderately sized matrices (<~300 in browser this is fine). - Space: O(rows) extra for the collapsed array.**JavaScript implementation**
javascript
// Returns {maxSum, left, right, top, bottom}
function maxSubmatrix(matrix) {
const rows = matrix.length;
const cols = rows ? matrix[0].length : 0;
let best = { maxSum: -Infinity, left:0, right:0, top:0, bottom:0 };
for (let left = 0; left < cols; left++) {
const rowSums = new Array(rows).fill(0);
for (let right = left; right < cols; right++) {
for (let r = 0; r < rows; r++) rowSums[r] += matrix[r][right];
// Kadane on rowSums
let curSum = 0, curStart = 0;
for (let r = 0; r < rows; r++) {
if (curSum <= 0) { curSum = rowSums[r]; curStart = r; }
else curSum += rowSums[r];
if (curSum > best.maxSum) {
best = { maxSum: curSum, left, right, top: curStart, bottom: r };
}
}
}
}
return best;
}
**Browser performance considerations (frontend)**- Avoid very large matrices in-memory: O(rows*cols) DOM or data costs. Stream/process on web worker to keep UI responsive. - Use typed arrays if values are numeric for lower GC pressure. - If cols >> rows, swap iteration (collapse rows) to minimize quadratic dimension. - Throttle/visualize long-running operations, show progress, or offload to backend for huge inputs. **Edge cases**- All-negative matrix handled by Kadane variant above. - Empty matrix returns -Infinity or validate input first.
MediumTechnical
46 practiced
Design and implement a small library function stableSortBy(arr, keyFn) in JavaScript that sorts objects by a key while preserving the original relative order for equal keys. Discuss how to implement stable sort in environments where Array.prototype.sort is not guaranteed stable and analyze O(n log n) stable alternatives.
Sample Answer
**Approach (brief)** Use the decorate-sort-undecorate pattern: map each element to {key, index, value}, sort by key and then by original index (tie-breaker) so equal keys preserve input order even if host sort isn't stable. For environments where you don't want to rely on Array.prototype.sort at all, implement a stable merge sort.**Code (stableSortBy using built-in sort + tie-breaker)**
javascript
// stableSortBy: returns a new array sorted by keyFn, stable across engines
function stableSortBy(arr, keyFn) {
// decorate: capture key and original index
const decorated = arr.map((value, index) => ({
value,
key: keyFn(value),
index
}));
// sort by key, then index to preserve original order for equal keys
decorated.sort((a, b) => {
if (a.key < b.key) return -1;
if (a.key > b.key) return 1;
return a.index - b.index;
});
// undecorate
return decorated.map(d => d.value);
}
**Explanation & reasoning** - Decorating captures the original index so we can break ties deterministically. - Returning non-zero for ties (via index difference) avoids relying on the engine's stability: the comparator forces the relative order. - This is simple, readable, and works well in frontend code where performance needs are moderate.**Complexity** - Time: O(n log n) for sort. - Space: O(n) additional for decoration.**Edge cases & notes** - keyFn should be deterministic and comparable with < and >; for complex keys, compute a suitable comparable form (e.g., numbers, strings). - For large arrays or performance-sensitive cases, or when you must avoid Array.prototype.sort semantics entirely, implement a stable merge sort.**Alternative: stable merge sort (sketch)** - Merge sort is naturally stable. Implement recursively, splitting, and merging while preserving order for equal keys. Time O(n log n), space O(n). Preferable if you need guaranteed stability and control over comparisons.
HardTechnical
60 practiced
Given two sequences (arrays) A and B, compute a minimal edit script of insertions and deletions to transform A into B suitable for a frontend diff/patch system (e.g., virtual DOM reconciliation). Describe the Myers diff algorithm at a high level and outline a practical implementation approach for moderate sizes in JavaScript.
Sample Answer
**High-level idea (Myers Algorithm)**Myers finds the shortest edit script (SES) between sequences by exploring "furthest reaching" diagonals in the edit graph. It performs iterations by edit distance d = 0..D, and for each d computes the farthest x on each diagonal k = x - y using either an insertion or deletion, then greedily follows matching "snakes" (equal elements). When a path reaches the bottom-right, you've found the minimal edits.**Why it fits frontend diffing**- Produces minimal insert/delete ops (no substitutions), good for virtual DOM where moves can be modeled as delete+insert or optimized separately.- Linear in output size; practical for moderate arrays (hundreds–thousands).**Practical JS approach (outline + snippet)**- Use Myers to compute SES of indices.- Translate SES into patch ops: {type: 'insert'|'delete', index, value}.- For UI, coalesce consecutive deletes/inserts and optionally detect moves by keying elements.Example core skeleton (simplified):
javascript
// returns list of {type, index, value}
function diff(A, B) {
const N = A.length, M = B.length;
const max = N + M;
const V = new Map(); V.set(1, 0);
const trace = [];
for (let d=0; d<=max; d++) {
const Vnext = new Map();
for (let k = -d; k<=d; k+=2) {
const down = (k === -d) || (k !== d && V.get(k-1) < V.get(k+1));
let x = down ? V.get(k+1) : V.get(k-1) + 1;
let y = x - k;
while (x < N && y < M && A[x] === B[y]) { x++; y++; }
Vnext.set(k, x);
if (x >= N && y >= M) { trace.push(Vnext); return buildEdits(trace, A, B); }
}
trace.push(Vnext); V.clear(); for (const [k,v] of Vnext) V.set(k,v);
}
}
**Complexity & Practical notes**- Time O((N+M)D), space O(N+M) for trace (D = edit distance).- For frontend: use keys to prefer O(n) keyed diffs; run Myers on unkeyed lists or small arrays.- Handle edge cases: empty arrays, duplicate elements (use keys), and very large arrays (chunk or use heuristics).
EasyTechnical
49 practiced
Write a function charFrequency(s) in JavaScript that returns an object mapping characters to their counts for a given string. Explain how you would adapt your implementation to correctly handle full Unicode characters (code points beyond BMP) and what libraries or built-ins might help.
Sample Answer
**Approach (brief)** Use a single pass over the string, counting each character in an object (or Map). For correct Unicode (characters beyond BMP like emojis or combined graphemes) iterate by code points rather than UTF-16 code units.**Code (handles BMP and supplementary code points)**
javascript
// Counts Unicode code points (correct for emojis / characters > U+FFFF)
function charFrequency(s) {
const freq = Object.create(null); // clean map-like object
for (const ch of s) { // for...of iterates by Unicode code points
freq[ch] = (freq[ch] || 0) + 1;
}
return freq;
}
**Key concepts & alternatives**- for...of over a string iterates by Unicode code points (ES6+), so surrogate pairs are handled.- If you need to treat user-perceived characters (grapheme clusters like "🇺🇳" or "👩👩👦"), use Intl.Segmenter or the grapheme-splitter library: - Intl.Segmenter('en', { granularity: 'grapheme' }) in modern browsers. - grapheme-splitter npm package for broader compatibility.- Use Map if insertion order or non-string keys matter.**Complexity & edge cases**- Time: O(n) where n is number of code points iterated. Space: O(k) distinct characters.- Edge cases: combining marks, ZWJ sequences — use Intl.Segmenter or grapheme-splitter when those should be counted as single units.
MediumTechnical
56 practiced
Implement maxSubarray(nums) in JavaScript that returns the maximum subarray sum (Kadane's algorithm). Then adapt your solution to also return the start and end indices of the subarray. Discuss why Kadane's is O(n) and any numerical edge cases (all negatives, very large values).
Sample Answer
**Approach (brief)** Use Kadane's algorithm: iterate once, maintain current sum; reset when it drops below 0. Track max sum and indices for the best window.**Implementation (JavaScript)**
javascript
// O(n) Kadane's algorithm returning sum and start/end indices
function maxSubarray(nums) {
if (!nums || nums.length === 0) return { sum: 0, start: -1, end: -1 };
let maxSoFar = Number.NEGATIVE_INFINITY;
let currentSum = 0;
let tempStart = 0;
let bestStart = 0;
let bestEnd = 0;
for (let i = 0; i < nums.length; i++) {
// extend or start new subarray
if (currentSum + nums[i] < nums[i]) {
currentSum = nums[i];
tempStart = i;
} else {
currentSum += nums[i];
}
// update best
if (currentSum > maxSoFar) {
maxSoFar = currentSum;
bestStart = tempStart;
bestEnd = i;
}
}
return { sum: maxSoFar, start: bestStart, end: bestEnd };
}
**Why O(n)** Single pass over the array, O(1) work per element -> linear time. Constant extra space for variables -> O(1) space.**Edge cases & numeric notes**- All negatives: algorithm returns the largest (least negative) element; initializing maxSoFar to -Infinity handles this.- Very large values: JavaScript numbers are IEEE-754 doubles; sums may overflow to Infinity if extremely large. For financial/big-integer needs consider BigInt (but BigInt disallows fractional) or arbitrary-precision libs.- Empty array handled by an early return.
Unlock Full Question Bank
Get access to hundreds of Array and String Manipulation interview questions and detailed answers.
