Algorithms and Data Structures Questions

Comprehensive understanding of core data structures such as arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs, and fundamental algorithms including sorting, searching, traversal, string manipulation, and graph algorithms. Ability to analyze and compare time and space complexity using asymptotic notation such as Big O, Big Theta, and Big Omega, and to reason about trade offs between different approaches. Skills include selecting the most appropriate data structure for a problem, designing efficient algorithms, applying algorithmic paradigms such as divide and conquer, dynamic programming, greedy methods, and graph search, and implementing correct and robust code for common interview problems. At more senior levels, this also covers optimizing for large scale through considerations of memory layout, caching, amortized analysis, parallelism and concurrency where applicable, and profiling and tuning for performance in realistic systems.

HardTechnical

83 practiced

An Android app shows frequent GC pauses during fast scrolling. Profiling points to allocation churn in image handling and view binding: many short-lived temporary objects created per frame. As a senior engineer, outline a step-by-step approach to identify root causes (profiling tools, hotspots) and propose algorithmic and data-structure-level fixes (object pooling, view holder reuse, primitive arrays, bitmap pooling, avoiding boxed primitives). Explain risks and how you'd validate improvements.

Sample Answer

**Situation & goal** Reduce GC pauses during fast scrolling by eliminating per-frame allocation churn in image handling and view binding.

**Step-by-step investigation**1. Reproduce reliably on device/emulator (different API levels). 2. Profiling tools: - Android Studio Memory Profiler (allocation tracking, record allocations on timeline). - Systrace / Perfetto to correlate CPU/GC with UI frames. - Allocation tracker + MAT (heap dumps) for retained objects. 3. Identify hotspots: - Record during scroll, inspect top allocation sites, short-lived objects per frame, and frequent finalizers. - Inspect call stacks: image decoding, binding adapters, RecyclerView onBindViewHolder, layout inflation.

**Algorithmic & data-structure fixes**- View reuse: - Ensure RecyclerView ViewHolder pattern strictly reused; avoid re-inflating or new listeners per bind. - Use payloads in notifyItemChanged to reduce rebinding.- Avoid temporary objects: - Replace boxed primitives (Integer/Float) with primitives; avoid String.format per bind. - Cache Spannable/TypedValue conversions; reuse StringBuilder for concatenation.- Object pooling: - Pool frequently used small objects (e.g., Rect, Matrix) via Pools.SynchronizedPool.- Bitmap & image pooling: - Use BitmapPool (Glide/Coil) or inBitmap for decoders to reuse pixel buffers. - Decode with inSampleSize, prefer hardware bitmaps when appropriate.- Use primitive arrays and reuse buffers for image transformations.- Lazy allocations: allocate on demand, but reuse across binds; move heavy work off UI thread.

**Risks & mitigations**- Pools cause memory-retention / leaks — set size limits, clear on lowMemory, run leak checks.- Pooled objects must be reset — add clear/reset method and tests.- InBitmap compatibility across API levels — fallback logic.- Premature optimization complexity — prioritize high-impact hotspots.

**Validation**- Microbenchmarks: measure allocations/frame before/after (Memory Profiler). - Perfetto traces to confirm reduced GC frequency and lower jank. - UX metrics: frame drops, 90th/99th percentile frame times. - Automated tests for correctness (no stale state from reused objects) and memory leak detection (LeakCanary).

This approach focuses on measuring, fixing hotspots with minimal invasive changes, and validating both performance and correctness.

EasyTechnical

95 practiced

Write a Kotlin function that reverses a singly-linked list in-place. Use the following node definition:

class ListNode(var value: Int, var next: ListNode?)

Implement:- fun reverse(head: ListNode?): ListNode?

Constraints: O(n) time, O(1) extra space. Handle empty and single-node lists. Briefly explain how this in-place operation affects memory and GC behavior on Android.

Sample Answer

**Approach (brief)** Use iterative three-pointer in-place reversal: previous, current, next. Works O(n) time, O(1) extra space. Handles null and single-node.

**Code**

kotlin

class ListNode(var value: Int, var next: ListNode?)

fun reverse(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var curr = head
    while (curr != null) {
        val next = curr.next       // save next
        curr.next = prev           // reverse pointer
        prev = curr                // advance prev
        curr = next                // advance curr
    }
    return prev
}

**Why it works / Complexity**- Time: O(n) — each node visited once. - Space: O(1) extra — only a few pointers.

**Edge cases**- head == null -> returns null- single node -> returns same node (next becomes null then prev is node)

**Android memory / GC notes**- In-place reversal reuses existing nodes; no new allocations, reducing GC churn and temporary object pressure on Android. This lowers pause risk and improves performance, especially in tight loops or low-memory devices. Ensure you don't keep stale external references to old head if you expect it to be collectible.

EasyTechnical

128 practiced

Explain how immutable strings in Java/Kotlin and Swift affect memory allocation, duplication, and performance on mobile devices. Give examples where naive string concatenation in tight loops or JSON construction causes allocation churn and GC/ARC pressure. Describe platform-specific mitigation techniques (StringBuilder/StringBuffer in JVM, String interpolation patterns in Kotlin, NSMutableString or Data/ByteBuffer strategies in Swift) and how you'd profile and fix excessive string allocations on Android and iOS.

Sample Answer

**Brief summary**Immutable strings mean every modification produces a new object/value. On mobile this increases heap churn, GC (Android) or ARC ref-count ops (iOS), extra copies and battery/latency cost in tight loops or large JSON builds.

**Examples (problematic)**Kotlin naive concatenation in loop:

kotlin

var s = ""
for (i in 0 until n) {
  s += "item:$i,"        // creates new String each iteration -> O(n^2) work
}

Swift naive concatenation:

swift

var s = ""
for i in 0..<n {
  s += "item:\(i),"      // creates new String each time -> many allocations
}

**Why this hurts**- Each += allocates a new buffer and copies old contents -> allocation churn.- Android: triggers more GC pauses and increased young-gen promotion.- iOS: many transient String/NSString objects and ARC inc/dec overhead; temporary bridged CFString can be expensive.

**Platform mitigations**- Android/JVM: use StringBuilder (single mutable buffer) or StringBuffer if thread-safety needed.

kotlin

val sb = StringBuilder()
for (i in 0 until n) { sb.append("item:").append(i).append(",") }
val s = sb.toString()

- Kotlin idioms: buildString { append... } which uses an internal StringBuilder.

kotlin

val s = buildString { repeat(n) { append("item:").append(it).append(",") } }

- iOS/Swift: - For text: use String concatenation sparingly; prefer StringBuilder-like pattern via Array + join:

swift

let parts = (0..<n).map { "item:\($0)" }
let s = parts.joined(separator: ",")

- For heavy mutable data: use NSMutableString or Data/ByteBuffer for binary/JSON building to avoid repeated copies.

**Profiling & fixing**- Android: use Android Studio Profiler -> Memory/Allocation tracker and SystemTrace. Look for high rate of short-lived String objects. Use Allocation Tracker to find call site, replace with StringBuilder/buildString, reuse buffers (ThreadLocal if reuse across calls).- iOS: use Instruments (Allocations, Leaks, Time Profiler). Filter by string/CFString churn, check retain/release hotspots. Replace with NSMutableString or accumulate in an array and joined; use Data with manual serialization for binary JSON and JSONSerialization writing to Data.

**Tips & trade-offs**- Reuse buffers where safe to avoid repeated allocation.- Prefer higher-level builders (buildString, join) for clarity and safety.- For very large JSON consider stream-based serializers to avoid keeping entire string in memory.- Measure before/after: allocation counts, GC pause time (Android), CPU sample (iOS).

EasyTechnical

95 practiced

For common mobile collection types, state average and worst-case time complexity for these operations: random access, insertion at head/tail, deletion, and search. Cover at least: dynamic array (ArrayList), singly/doubly linked list, hash table (HashMap/Dictionary), and balanced tree (TreeMap). Also discuss memory overhead per element and how that impacts low-memory devices.

MediumSystem Design

78 practiced

Design a local SQLite/Room schema for a social feed that must support: fast retrieval of newest posts for infinite scroll, efficient insertion of new posts, and filtering by author or tag. Specify tables, necessary indices (including composite indices), and discuss normalization vs denormalization trade-offs for read-heavy mobile scenarios and migration considerations.

Sample Answer

**Clarify requirements**- Read-mostly mobile DB, infinite scroll by newest, fast inserts, filter by author or tag, offline-friendly, small storage footprint.

**Schema (Room/SQLite tables)**- posts - id TEXT PRIMARY KEY - author_id TEXT NOT NULL - created_at INTEGER NOT NULL -- epoch ms - content TEXT - preview TEXT - metadata JSON/STRING- authors - id TEXT PRIMARY KEY - name TEXT - avatar_url TEXT- tags - id INTEGER PRIMARY KEY AUTOINCREMENT - name TEXT UNIQUE- post_tags (many-to-many) - post_id TEXT - tag_id INTEGER - PRIMARY KEY (post_id, tag_id)

**Indices (critical)**- posts: CREATE INDEX idx_posts_created_at_desc ON posts(created_at DESC);- posts: CREATE INDEX idx_posts_author_created ON posts(author_id, created_at DESC); -- composite for author filter + sort- post_tags: CREATE INDEX idx_post_tags_tag_post ON post_tags(tag_id, post_id);- optional: posts(content) FTS virtual table for search

**Access patterns**- Newest posts (infinite scroll): SELECT * FROM posts ORDER BY created_at DESC LIMIT :pageSize OFFSET :offset — uses idx_posts_created_at_desc.- Filter by author: SELECT ... FROM posts WHERE author_id = ? ORDER BY created_at DESC — uses composite index.- Filter by tag: JOIN post_tags on post_id WHERE tag_id = ? ORDER BY posts.created_at DESC — uses idx_post_tags_tag_post and posts index.

**Normalization vs Denormalization**- Normalize (authors, tags, join table): saves space, avoids duplication, simpler updates (e.g., author name change).- Denormalize (store author_name, avatar in posts): faster reads (no join), fewer queries, beneficial for read-heavy mobile UI and offline rendering.- Recommendation: normalize as source-of-truth but denormalize selective fields (author_name, avatar_url) into posts for the UI; update denorm fields on sync to avoid extra join cost.

**Migration considerations**- Use Room Migration APIs to add columns or tables. For filling denormalized fields on v1→v2, run a migration that joins authors and updates posts in a transaction with batching to avoid long migrations.- Keep migrations idempotent; handle schema version checks and fallback strategies for large DBs (background post-migration indexing).- Consider incremental migrations: add columns nullable, ship, then backfill asynchronously on first app launch.

As a mobile developer I'd prefer the normalized schema with targeted denormalization for UI-critical fields, composite indices for filter+sort patterns, and cautious Room migrations that avoid blocking app startup.

Unlock Full Question Bank

Get access to hundreds of Algorithms and Data Structures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.