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
54 practiced
Implement longest_palindromic_substring(s) for a backend feature that highlights longest symmetric segments in user text. Provide either Manacher's algorithm (O(n)) or a clear O(n^2) DP/expand-around-center solution. Explain how to handle even and odd length palindromes and compare memory/time trade-offs.
Sample Answer
**Approach (brief)** I’ll present Manacher’s algorithm (O(n) time, O(n) space) which uniformly handles even/odd palindromes by transforming the string. For comparison I summarize expand-around-center (O(n^2), O(1) extra).**Manacher’s algorithm (Python)**
python
def longest_palindromic_substring(s: str) -> str:
# Transform: put separators to handle even/odd uniformly
t = '^#' + '#'.join(s) + '#$' # sentinels avoid bounds checks
n = len(t)
p = [0] * n # radius array
center = right = 0
for i in range(1, n - 1):
mirror = 2 * center - i
if i < right:
p[i] = min(right - i, p[mirror])
# expand around i
while t[i + (1 + p[i])] == t[i - (1 + p[i])]:
p[i] += 1
# update center/right
if i + p[i] > right:
center, right = i, i + p[i]
# find max radius
max_len, center_index = max((val, idx) for idx, val in enumerate(p))
start = (center_index - max_len) // 2 # map back to original string
return s[start:start + max_len]
**How even/odd are handled** Inserting '#' between characters makes every palindrome in transformed string odd-length; both original even and odd palindromes map to centered odd palindromes, so a single expansion logic covers both.**Trade-offs / comparison**- Manacher: O(n) time, O(n) extra for transformed string + radius array — best for long texts or high-throughput backend processing.- Expand-around-center: simpler, O(1) extra, but O(n^2) time worst-case — acceptable for short inputs or rare calls.- For backend: prefer Manacher when processing many/large user texts or doing batch highlighting; use expand method for simplicity in low-volume or latency-tolerant paths.**Edge cases**- Empty string, single char handled by transform- Non-ASCII: work with code points (Python str is fine)
EasyTechnical
53 practiced
Implement max_subarray(nums) in your preferred language (Python/Java) to compute the maximum subarray sum (Kadane's algorithm). This is used on the backend to compute peak load windows. Explain handling of all-negative arrays, return value semantics, and provide time and space complexity.
Sample Answer
**Approach (brief)**Use Kadane’s algorithm: scan once maintaining current running sum and best seen. For backend peak load windows, we return the maximum sum and treat an all-negative array by returning the largest (least negative) element — this represents the peak even if it's negative.**Python implementation**
python
def max_subarray(nums):
# nums: list[int], returns int (maximum subarray sum)
if not nums:
raise ValueError("nums must be non-empty")
max_ending = max_so_far = nums[0]
for x in nums[1:]:
# either extend previous subarray or start new at x
max_ending = max(x, max_ending + x)
max_so_far = max(max_so_far, max_ending)
return max_so_far
**Java implementation**
java
public static int maxSubarray(int[] nums) {
if (nums == null || nums.length == 0) throw new IllegalArgumentException("nums must be non-empty");
int maxEnding = nums[0], maxSoFar = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEnding = Math.max(nums[i], maxEnding + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEnding);
}
return maxSoFar;
}
**Return semantics**- Returns a single int representing the maximum contiguous sum.- For all-negative arrays, returns the largest element (the least negative), not zero — important for accurate peak-load reporting.**Complexity**- Time: O(n) single pass.- Space: O(1) constant extra space.**Notes for backend use**- Use 64-bit type (long) if values or sums can overflow int.- Validate input and log/monitor when arrays are unexpectedly empty.
HardTechnical
59 practiced
Compare and contrast suffix arrays and suffix automata for answering substring queries in a backend search feature. Describe how to build them (high-level), their memory and query time trade-offs, and how to use these structures to answer queries like 'number of occurrences' or 'longest common substring' between two strings.
Sample Answer
**Overview — when to pick which**- Suffix Array (SA): compact, simple, good for disk-friendly or memory-constrained backend caches and for batch/offline queries.- Suffix Automaton (SAM): online-friendly, fast substring statistics, better for many dynamic or streaming builds and for counting distinct substrings.**High-level build**- SA: build suffixes, sort them (e.g., SA-IS or DC3 for O(n)). Construct LCP array (Kasai) in O(n). Suitable to precompute offline and store arrays.- SAM: online construction in O(n) by iterating characters, maintaining states and suffix links; incremental and memory grows with distinct end-pos equivalence classes (<= 2n−1 states).**Memory**- SA: O(n) for SA + O(n) for LCP (+ optional RMQ = O(n) or O(1) with sparse table). Lower constant factors; good when storing on disk or in shared memory.- SAM: O(n) states × alphabet factors (transitions). In practice ~2–3× memory of string due to maps/arrays per state. More RAM-heavy in high-alphabet backends (UTF-8).**Query time & usage**- Exact substring existence: - SA: binary search on SA with O(m log n) comparisons, or O(m + log n) with LCP-accelerated search. - SAM: O(m) by walking transitions.- Number of occurrences of pattern P: - SA: find SA range via binary search ⇒ occurrences = range size; O(m log n) or O(m + log n). - SAM: augment each state with end-pos count (propagate counts from terminal states) ⇒ walk P in O(m) then read count.- Longest Common Substring (LCS) of A and B: - SA: build combined string A + '#' + B, compute LCP between suffixes from different strings, take max LCP; O(n) after SA/LCP. - SAM: build SAM for A, run B through SAM tracking current match length and best match; O(|B|). Works well when A is indexed and many B queries arrive.**Trade-offs & backend practicalities**- Precomputation vs online: SA is ideal for static corpus (build once, serve many queries). SAM is better if you need incremental updates or streaming ingestion.- Memory vs speed: SA has smaller footprint and simpler persistent storage; SAM gives faster per-query substring counts and distinct-substring queries but uses more memory.- Implementation: SA uses arrays and is cache-friendly (good for large-scale services). SAM often uses hash maps per state — choose compact arrays for small alphabets or pooled storage to reduce overhead.- Concurrency & persistence: store SA/LCP in read-only memory-mapped files for many-read backends; serialize SAM carefully (transition compression) if you need to persist.**Summary recommendation**- For a search backend with a mostly static corpus and many pattern-occurrence or LCS batch queries, use Suffix Array + LCP + RMQ. For online ingestion, frequent incremental indexing, or lots of distinct-substring/count queries with low-latency needs, use Suffix Automaton with propagated end-pos counts.
EasyTechnical
82 practiced
As a backend developer building an API that returns recent events in reverse chronological order, implement a Python function reverse_array(arr) that reverses an array of integers in-place. You may not allocate another array proportional to n (O(1) extra space). Explain edge cases (empty array, single element, even/odd length) and whether your function mutates the input. Provide time and space complexity.
Sample Answer
**Approach (brief)** Use a two-pointer in-place swap: left at start, right at end, swap and move pointers until they cross. This uses O(1) extra space and O(n) time.**Code**
python
def reverse_array(arr):
"""
Reverse list of integers in-place and return it.
Mutates the input list.
"""
left, right = 0, len(arr) - 1
while left < right:
# swap elements
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
**Explanation & edge cases**- Empty array: len(arr)=0 -> loop never runs; returns [] (no mutation beyond input being same empty list). - Single element: left==right -> loop doesn't run; list unchanged. - Even length: pointers cross after swaps; all pairs swapped. - Odd length: middle element left == right remains in place. - The function mutates the input list in-place (important for backend memory-sensitive contexts); it also returns the same reference for convenience.**Complexity**- Time: O(n) — each element participates in at most one swap. - Space: O(1) extra — only two integer pointers used.**Notes for backend use**- In APIs, document that input list is mutated or pass a copy (arr.copy()) if immutability is required.
MediumTechnical
53 practiced
Implement length_of_longest_substring(s) in Python/Java to find the length of the longest substring without repeating characters. This is used to validate token entropy windows in a backend service. Provide a sliding window solution with O(n) time and explain how to handle Unicode characters where simple char arrays may not suffice.
Sample Answer
**1. Approach (brief)** Use sliding window with two pointers and a hash map storing last seen index for each character. Move right pointer; if a char repeats inside window, advance left to last_seen + 1. Works in O(n).**2. Python implementation**
python
def length_of_longest_substring(s: str) -> int:
last = {} # map from char to last index
start = 0
best = 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1
last[ch] = i
best = max(best, i - start + 1)
return best
- Comments: uses Python str which is Unicode-aware (iterates by code points). For full Unicode grapheme support (e.g., emojis + modifiers), normalize and use a grapheme splitter (third-party, e.g., regex \X or the `grapheme` package) to iterate user-perceived characters.**3. Complexity**- Time: O(n) single pass- Space: O(min(n, k)) where k = distinct characters**4. Edge cases**- Empty string -> 0- Very long strings -> ensure map memory acceptable- Combining characters/emoji -> consider grapheme splitting for token entropy windows**5. Alternatives**- Use array indexed by codepoint for ASCII; map is needed for Unicode.
Unlock Full Question Bank
Get access to hundreds of Array and String Manipulation interview questions and detailed answers.
