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
47 practiced
Explain Unicode normalization forms (NFC, NFD) and implement a mobile-safe comparator that returns true if two user-visible strings are equivalent after normalization. Describe platform APIs in iOS/Swift and Android/Java for normalization and explain performance considerations when normalizing many strings.
Sample Answer
**Explaination (NFC vs NFD)** - NFC (Normalization Form C): canonical decomposition followed by canonical composition — preferred for storage; composes characters to single code points when possible (e.g., "é" U+00E9). - NFD: canonical decomposition — breaks composed characters into base + combining marks (e.g., "e" + U+0301). Both preserve visual equivalence; choose one canonical form and compare.**Mobile-safe comparator (approach)** - Normalize both strings to the same form (NFC recommended). - Optionally apply case folding and remove Unicode-insignificant differences (e.g., apply .trimming, collapse whitespace) depending on UX.Swift (iOS) example:
swift
import Foundation
func mobileSafeEqual(_ a: String, _ b: String) -> Bool {
let na = a.precomposedStringWithCanonicalMapping // NFC
let nb = b.precomposedStringWithCanonicalMapping
return na.caseInsensitiveCompare(nb) == .orderedSame
}
Java (Android) example:
java
import java.text.Normalizer;
public static boolean mobileSafeEqual(String a, String b) {
String na = Normalizer.normalize(a, Normalizer.Form.NFC);
String nb = Normalizer.normalize(b, Normalizer.Form.NFC);
return na.equalsIgnoreCase(nb);
}
**Platform APIs** - iOS/Swift: String APIs: precomposedStringWithCanonicalMapping (NFC), decomposedStringWithCanonicalMapping (NFD). Also use CFStringTransform or StringTransform for additional transforms. - Android/Java: java.text.Normalizer.normalize(str, Normalizer.Form.NFC). Kotlin interoperates directly.**Performance considerations** - Normalization allocates new strings and can be costly if done repeatedly. Strategies: - Normalize once on input/save (normalize-on-write) and store canonical form. - Cache normalized values (LRU) for frequently compared strings. - Batch normalize when processing many strings (avoid per-character normalization loops). - Measure on target devices; cheaper to normalize smaller tokenized pieces (usernames) than large text bodies. - For sorting/searching, consider ICU collators for locale-sensitive comparisons instead of raw normalization + equals.
HardTechnical
65 practiced
Given an NxN image represented as a 2D array of bytes (or ints) in Kotlin, implement an in-place 90-degree rotation of the image. Signature: fun rotateImage(matrix: Array<IntArray>): Unit. Optimize for cache locality and low allocations on mobile GPUs/CPUs, and describe how to handle large images that don't fully fit in cache.
Sample Answer
**Approach (brief)** Do an in-place rotation by rotating rings (layers) swapping four elements at a time. For cache locality on mobile, process the matrix in small tiles (block size like 16 or 32) to keep working set in L1/L2. For large images that don't fit cache, iterate tiles so each tile is transposed/rotated in-cache, then handle cross-tile moves.**Kotlin implementation (in-place, blocked)**
kotlin
fun rotateImage(matrix: Array<IntArray>) {
val n = matrix.size
if (n <= 1) return
val block = 32 // tune per-device (16/32)
var i = 0
while (i < n / 2) {
val iEnd = minOf(i + block, n / 2)
var j = i
while (j < n / 2) {
val jEnd = minOf(j + block, n / 2)
for (r in i until iEnd) {
for (c in j until jEnd) {
val a = r
val b = c
val tmp = matrix[a][b]
var x = a
var y = b
repeat(3) {
val nx = y
val ny = n - 1 - x
matrix[x][y] = matrix[nx][ny]
x = nx; y = ny
}
matrix[x][y] = tmp
}
}
j = jEnd
}
i = iEnd
}
}
**Why this works / performance notes**- Rotates four positions per element, O(n^2) time, O(1) extra space.- Blocking improves spatial locality (work on contiguous memory) and reduces cache/DRAM traffic on mobile CPUs/GPUs.- Tune block size per device; smaller blocks if L1 is small.- For extremely large images exceeding main memory of GPU, process tiled regions saved to/from GPU staging buffers or use streaming: upload one tile, rotate, write back, and coordinate borders carefully. Also consider using native ByteBuffer and JNI for lower overhead when necessary.**Complexity**- Time: O(n^2)- Space: O(1) extra (in-place)- Cache: Blocked version reduces cache misses; ideal block ~ cache line aligned and fits L1/L2.
HardTechnical
91 practiced
Find the median of two sorted arrays in O(log(min(m,n))) time. Implement the algorithm in Kotlin and explain edge cases. Discuss why this algorithm is appropriate (or not) for mobile apps that need to combine sorted feeds from multiple sensors or data sources.
Sample Answer
**Approach (brief)** Use binary search on the smaller array to find a partition where left halves of both arrays contain half the total elements and every left element ≤ every right element. Median is max(lefts) or average of max(lefts) and min(rights).**Kotlin implementation**
kotlin
// O(log(min(m,n))) time, O(1) space
fun findMedianSortedArrays(a: IntArray, b: IntArray): Double {
var A = a; var B = b
if (A.size > B.size) { A = b; B = a } // ensure A is smaller
val m = A.size; val n = B.size
var low = 0; var high = m
val half = (m + n + 1) / 2
while (low <= high) {
val i = (low + high) / 2
val j = half - i
val Aleft = if (i == 0) Int.MIN_VALUE else A[i - 1]
val Aright = if (i == m) Int.MAX_VALUE else A[i]
val Bleft = if (j == 0) Int.MIN_VALUE else B[j - 1]
val Bright = if (j == n) Int.MAX_VALUE else B[j]
if (Aleft <= Bright && Bleft <= Aright) {
return if ((m + n) % 2 == 1) {
maxOf(Aleft, Bleft).toDouble()
} else {
(maxOf(Aleft, Bleft) + minOf(Aright, Bright)) / 2.0
}
} else if (Aleft > Bright) {
high = i - 1
} else {
low = i + 1
}
}
throw IllegalArgumentException("Input arrays not sorted")
}
**Key points & edge cases**- Handle empty arrays (works: Int.MIN/MAX used to represent infinities). If both empty, throw. - Unequal lengths, duplicates, all elements in one array: algorithm still valid. - Integer overflow avoided by using bounds sentinels and Double for median when averaging.**Complexity**- Time: O(log(min(m,n))) - Space: O(1)**Mobile-app suitability**- Appropriate when merging read-only, sorted feeds where latency and CPU matter (e.g., sensor timelines). It's CPU-efficient and low-memory—good for constrained devices. Not ideal if feeds constantly change in real time; then incremental streaming/online median structures (heaps) or merge-on-write strategies may be more practical given asynchronous updates and threading on mobile.
EasyTechnical
62 practiced
Write a function in Kotlin that reverses a mutable character array in place. Signature: fun reverseInPlace(s: CharArray): Unit. Constraints: O(n) time and O(1) extra space. Explain how Kotlin String immutability affects your approach if the input were a String instead of a CharArray. On Android, how would you avoid extra memory allocations for very large strings received from I/O (e.g., large text files) when reversing?
Sample Answer
**Approach (two‑pointer, in-place)**Use two pointers (left, right) swapping characters until they meet. O(n) time, O(1) extra space.Code:
kotlin
fun reverseInPlace(s: CharArray) {
var i = 0
var j = s.size - 1
while (i < j) {
val tmp = s[i]
s[i] = s[j]
s[j] = tmp
i++; j--
}
}
Time & space- Time: O(n) — each element swapped at most once.- Extra space: O(1) — only a single temporary char.Edge cases- Empty array or size 1: loop does nothing.- Unicode: Char in Kotlin is a UTF‑16 code unit; surrogate pairs remain split if you need to preserve grapheme clusters — handle with proper Unicode library if necessary.Kotlin String immutability- String is immutable; you cannot modify it in place. Calling s.toCharArray() produces a new copy (O(n) memory).- If API gives String but you must reverse in place semantics, convert to CharArray, reverse, then create a new String — this allocates extra memory.Android large I/O without extra allocations- Avoid loading entire file into memory. Options: - Use RandomAccessFile + FileChannel.map to memory‑map the file and perform swaps on the mapped ByteBuffer (be careful with character encoding and UTF‑16 vs bytes). - Stream and write reversed chunks: read from file ends using RandomAccessFile.seek and copy blocks to output file, swapping as you go. - Use native mmap via NDK for very large files requiring minimal GC pressure.Tradeoffs: memory‑map keeps low extra heap but touches native memory; blockwise read/writes are simpler and safer for variable encodings.
EasyTechnical
63 practiced
Implement a React Native / JavaScript function to merge and deduplicate two arrays of strings while preserving original relative order for the first occurrence across both arrays. Signature: function mergeDedup(a: string[], b: string[]): string[]. Explain time/space complexity and how to minimize memory churn in a JS bridge on mobile devices.
Sample Answer
**Approach**Use a single pass over both arrays, tracking seen items in a Set to preserve first-occurrence relative order. Avoid creating many intermediate arrays to reduce memory churn across the JS bridge.**Implementation**
javascript
// Merge two arrays preserving first-occurrence order and deduplicate
function mergeDedup(a, b) {
const seen = new Set();
const out = []; // single output buffer to minimize allocations
for (let i = 0; i < a.length; i++) {
const v = a[i];
if (!seen.has(v)) {
seen.add(v);
out.push(v);
}
}
for (let i = 0; i < b.length; i++) {
const v = b[i];
if (!seen.has(v)) {
seen.add(v);
out.push(v);
}
}
return out;
}
**Complexity**- Time: O(n + m) where n = a.length, m = b.length (each element checked once).- Space: O(k) for Set + output, where k = number of unique strings. In-place mutation of input avoided for safety.**Minimizing JS bridge memory churn (mobile)**- Allocate one output array and one Set; avoid map/filter/concat chains that create intermediate arrays.- Prefer primitive strings (already JS) over heavy objects; if bridging to native, batch results to reduce crossing frequency.- Reuse buffers in long-lived modules if safe, and avoid large synchronous allocations on the UI thread.
Unlock Full Question Bank
Get access to hundreds of Array and String Manipulation interview questions and detailed answers.
