Comprehensive coverage of fundamental data structures, their operations, implementation trade offs, and algorithmic uses. Candidates should know arrays and strings including dynamic array amortized behavior and memory layout differences, linked lists, stacks, queues, hash tables and collision handling, sets, trees including binary search trees and balanced trees, tries, heaps as priority queues, and graph representations such as adjacency lists and adjacency matrices. Understand typical operations and costs for access, insertion, deletion, lookup, and traversal and be able to analyze asymptotic time and auxiliary space complexity using Big O notation including constant, logarithmic, linear, linearithmic, quadratic, and exponential classes as well as average case, worst case, and amortized behaviors. Be able to read code or pseudocode and derive time and space complexity, identify performance bottlenecks, and propose alternative data structures or algorithmic approaches to improve performance. Know common algorithmic patterns that interact with these structures such as traversal strategies, searching and sorting, two pointer and sliding window techniques, divide and conquer, recursion, dynamic programming, greedy methods, and priority processing, and when to combine structures for efficiency for example using a heap with a hash map for index tracking. Implementation focused skills include writing or partially implementing core operations, discussing language specific considerations such as contiguous versus non contiguous memory and pointer or manual memory management when applicable, and explaining space time trade offs and cache or memory behavior. Interview expectations vary by level from selecting and implementing appropriate structures for routine problems at junior levels to optimizing naive solutions, designing custom structures for constraints, and reasoning about amortized, average case, and concurrency implications at senior levels.
EasyTechnical
81 practiced
In Kotlin, implement a generic Stack<T> class using an internal array (do not use ArrayDeque). Provide push, pop, peek, size, and isEmpty. Ensure push has amortized O(1) time. Describe your growth strategy and explain complexity for push and pop. You can ignore concurrency and serialization concerns. Example signature:class ArrayStack<T> { // implement}
Sample Answer
**Approach**Implement a generic array-backed stack that grows by doubling capacity to ensure amortized O(1) push. Use a backing Array<Any?> and cast on pop/peek.**Code**
kotlin
class ArrayStack<T> {
private var data: Array<Any?> = arrayOfNulls(8)
private var top = 0
fun push(item: T) {
if (top == data.size) grow()
data[top++] = item
}
@Suppress("UNCHECKED_CAST")
fun pop(): T {
if (isEmpty()) throw NoSuchElementException("Stack is empty")
val idx = --top
val value = data[idx] as T
data[idx] = null // avoid memory leak
return value
}
@Suppress("UNCHECKED_CAST")
fun peek(): T {
if (isEmpty()) throw NoSuchElementException("Stack is empty")
return data[top - 1] as T
}
fun size(): Int = top
fun isEmpty(): Boolean = top == 0
private fun grow() {
val newCap = data.size * 2
val newArr = arrayOfNulls<Any?>(newCap)
System.arraycopy(data, 0, newArr, 0, data.size)
data = newArr
}
}
**Growth strategy & complexity**- Growth: double capacity when full (data.size -> 2 * data.size).- Amortized analysis: Doubling gives amortized O(1) push because expensive copies happen rarely; total copy cost over n pushes is O(n).- pop: O(1) worst-case. push: O(1) amortized, O(n) worst-case when growing.- Memory: uses contiguous array — small overhead on mobile but reduces per-node allocation versus linked structures.
EasyTechnical
99 practiced
Compare adjacency list and adjacency matrix representations for graphs. For a mobile app that processes social-graph data of up to 50k users with average degree 10, which representation would you choose and why? Discuss time/space trade-offs and cache/IO considerations for queries like "friends-of-friends" or short-path computations.
Sample Answer
**Answer (summary & recommendation)**I would choose an adjacency list. With 50k users and average degree ~10 the graph is sparse (≈250k undirected edges). Lists are far more memory- and cache-friendly on mobile while giving optimal traversal performance for common queries like friends-of-friends and short-path (BFS).**Space comparison**- Adjacency matrix: 50,000 × 50,000 = 2.5e9 entries. As bytes that's ~2.5 GB; as bits ~312 MB (still large and awkward). Mobile can’t afford the dense square.- Adjacency list: store ~500k neighbor entries (directed) or ~250k pairs (undirected). Compact arrays of 32-bit ints ≈ 2–4 MB plus small overhead — fits easily.**Time trade-offs**- Edge lookup: matrix O(1), list O(deg(u)) — if you need extremely frequent random adjacency queries and graph were dense, matrix helps.- Traversals (BFS / friends-of-friends): list O(V + E) — excellent for sparse graphs. Matrix traversal costs O(V^2) scanning a row/column each time and is wasteful.**Cache / I/O considerations**- Adjacency lists implemented as contiguous arrays (flat int arrays or typed buffers) have good locality for iterating neighbors, which benefits CPU caches and memory bandwidth on mobile.- Matrix implies huge contiguous memory or many page faults; poor cache behavior and increased GC pressure on managed runtimes.- For set operations (friends-of-friends), use sorted neighbor arrays or bitset/roaring bitmaps to accelerate union/intersection while keeping memory small.**Practical mobile notes**- Keep lists as Int32 arrays or compact buffers (avoid per-object allocation) and serialize with protobuf/flatbuffers.- Offload heavy shortest-path work to server if doing global multi-source queries; run local BFS for limited radius (e.g., 2–3 hops).- Consider memory-mapped files or partial loading for very large graphs, and use caching/LRU for active user neighborhoods.Choice rationale: sparsity + mobile memory/cache constraints make adjacency list (compact, contiguous arrays + efficient traversal patterns) the practical, performant option.
MediumTechnical
91 practiced
Given a sorted IntArray in Kotlin, implement twoSumSorted(nums: IntArray, target: Int): IntArray that returns 1-based indices of two numbers adding to target. Aim for O(n) time and O(1) extra space. The array may be large (n up to 1e6). Provide code and explain why two-pointer is preferred over a hash map on memory-constrained mobile devices.
Sample Answer
**Approach (brief)** Use a two-pointer scan exploiting the sorted order: left at 0, right at n-1. Move pointers inward until their sum equals target. This is O(n) time and O(1) extra space — ideal for memory-constrained mobile.**Code (Kotlin)**
kotlin
fun twoSumSorted(nums: IntArray, target: Int): IntArray {
var left = 0
var right = nums.size - 1
while (left < right) {
val sum = nums[left] + nums[right]
when {
sum == target -> return intArrayOf(left + 1, right + 1) // 1-based indices
sum < target -> left++
else -> right--
}
}
throw IllegalArgumentException("No solution") // or return intArrayOf(-1, -1)
}
**Why two-pointer vs hash map (mobile focus)** - Memory: Hash map requires O(n) extra memory to store values/indices — for n up to 1e6 that can be tens of MBs, impacting low-memory devices and risking GC pressure or OOM. Two-pointer uses constant extra space. - CPU & cache: Two-pointer is linear with very predictable memory access, friendly to CPU caches and battery life. Hash map has extra hashing overhead and irregular memory access patterns. - Simplicity: Fewer allocations and less GC reduces latency spikes; important for smooth mobile UI.**Complexity** - Time: O(n) - Space: O(1) extra**Edge cases** - nums size < 2 -> invalid - potential integer overflow if values near Int.MAX_VALUE (consider Long if needed)
EasyTechnical
75 practiced
Explain the amortized time complexity of append on dynamic arrays (e.g., Java ArrayList, Kotlin MutableList, Swift Array). Why is append considered amortized O(1)? Compare growth factors (2x vs 1.5x) and their effects on memory spikes and total copies. For a mobile app that frequently appends many small elements, what strategies reduce allocation spikes and GC/ARC churn?
Sample Answer
**What amortized O(1) means**- Appending to a dynamic array is usually O(1) most of the time, but occasionally O(n) when the buffer must grow and elements are copied. Amortized O(1) means averaged over many appends the cost per append is constant because expensive resizes happen rarely.**Why it averages to constant**- When capacity doubles, a resize at size k copies k elements. Over a sequence of n appends the total work from all resizes sums to O(n). So average cost per append = O(n)/n = O(1).**Growth factor trade-offs (2x vs 1.5x)**- 2x growth: - Pros: fewer resizes, lower total number of element copies (~ ≤ 2n total copies), small CPU overhead. - Cons: larger temporary memory spike at each resize (up to ~2× current usage).- 1.5x growth: - Pros: smaller memory spike per resize (less peak additional allocation). - Cons: more frequent resizes → more total copies (constant factor higher than 2x; still O(n) but with larger constant).**Mobile-app strategies to reduce allocation spikes and GC/ARC churn**- Reserve capacity up-front: - Kotlin: ArrayList(initialCapacity) or ensureCapacity(expected) - Swift: array.reserveCapacity(expectedCount) - This avoids repeated resizes and copies.- Batch inserts: append many items using bulk operations so fewer resizes.- Reuse buffers/objects: object pools or reuse mutable structs to avoid frequent allocations and ARC/GC churn.- Use value types when cheap (Swift structs) or primitive arrays (IntArray in Kotlin) to avoid boxing.- Stream/process in-place when possible to avoid accumulating large arrays.- Monitor with profiler (Instruments / Android Studio) to tune reserve sizes and growth behavior.Result: prefer reserving capacity for known workloads; choose growth factor trade-off by expected peak memory vs CPU/copy cost.
HardTechnical
91 practiced
Analyze the following pseudocode used for shortest-path in an offline mapping feature. Compute worst-case time and space complexity assuming adjacency lists. Propose mobile optimizations (graph representation, lazy loading tiles, heuristics) and name advanced techniques (A*, contraction hierarchies) to speed up queries.function shortestPath(src, dst, graph): dist = map(); prev = map(); for v in graph.vertices: dist[v] = INF dist[src] = 0 pq = MinHeap() pq.push((0, src)) while pq not empty: (d, u) = pq.pop() for edge in graph.adj[u]: if dist[edge.v] > d + edge.w: dist[edge.v] = d+edge.w; pq.push((dist[edge.v], edge.v)) return dist[dst]
Sample Answer
**Complexity Analysis (worst-case, adjacency lists)**- Time: O((V + E) log V). Initializing V distances is O(V). Each edge may cause a heap push; heap operations cost O(log V). So total O((V + E) log V), which for connected sparse graphs ≈ O(E log V).- Space: O(V + E) for the graph + O(V) for dist/prev + O(V) for the heap in worst-case ⇒ O(V + E).**Mobile-focused optimizations**- Graph representation: - Use compact binary formats (protobuf, flatbuffers) or compressed adjacency with delta-encoding for coordinates to reduce memory/io. - Store edge weights as fixed-point integers to avoid float overhead.- Lazy loading / tiled graphs: - Partition map into tiles/regions and load only nearby tiles; keep LRU cache for tiles. - When destination is outside loaded area, run incremental search and request background tile fetches; show partial route and ETA.- Heuristics & search space pruning: - Use A* with admissible heuristic (Haversine / great-circle distance) to reduce explored nodes dramatically. - Bidirectional search (bidirectional Dijkstra or A*) when appropriate.**Advanced techniques to speed queries**- Contraction Hierarchies (CH): Preprocess to add shortcuts and enable microsecond queries on mobile at cost of storage and preprocessing.- Transit Node Routing / Landmark-based (ALT): Precompute landmarks and triangle inequality bounds for fast heuristics.- Multi-level or hierarchical graphs: Combine road classes (local vs highways) to route quickly across scales.**Practical trade-offs**- Preprocessing (CH) reduces query time but increases storage and build time—do offline on server or during initial app install with progress indicators.- Favor A* + lazy tiles for responsive UX with low storage; use CH or offline bundles for premium offline experience.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
