Coding Fundamentals and Problem Solving Questions

Focuses on algorithmic thinking, data structures, and the process of solving coding problems under time constraints. Topics include core data structures such as arrays, linked lists, hash tables, trees, and graphs, common algorithms for searching and sorting, basics of dynamic programming and graph traversal, complexity analysis for time and space, and standard coding patterns. Emphasis on a disciplined problem solving approach: understanding the problem, identifying edge cases, proposing solutions with trade offs, implementing clean and readable code, and testing or reasoning about correctness and performance. Includes debugging strategies, writing maintainable code, and practicing medium difficulty interview style problems.

EasyTechnical

34 practiced

Implement an in-place function in Python to reverse a singly linked list and return the new head. Your implementation should use O(1) additional space and O(n) time. Assume Node has attributes val and next. Provide production-ready code with clear variable names and a brief comment about complexity.

Sample Answer

To reverse a singly linked list in-place, iterate through the list and rewire each node's next pointer to its previous node. Maintain three pointers: prev (initially None), current, and next_node to avoid losing the remainder of the list. This is O(n) time and O(1) additional space.

python

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head: Node) -> Node:
    """
    Reverse a singly linked list in-place and return new head.
    Time: O(n), Space: O(1)
    """
    previous = None
    current = head

    while current is not None:
        next_node = current.next      # save next node
        current.next = previous       # reverse pointer
        previous = current            # move previous forward
        current = next_node           # move current forward

    return previous  # new head (previous is None if original list was empty)

Key points:- Handles empty list (returns None) and single-node lists.- Uses clear variable names and minimal branching for readability and maintainability.- Suitable for production after adding optional type checks or unit tests.

HardSystem Design

37 practiced

Design an external merge sort to sort a 1TB dataset on disk with only 1GB of available memory. Describe phases including chunking, in-memory sort, k-way merge, file formats, buffer sizing to optimize disk I/O, parallelization across CPUs and disks, failure handling, and how this component would integrate into a client's ETL pipeline.

Sample Answer

Requirements & constraints:- Sort 1 TB on disk with 1 GB RAM; stable, recoverable, integrates into ETL (batch), low I/O time.

High-level approach:- External merge sort: Phase 1 — chunking + in-memory sort (produce sorted runs). Phase 2 — multi-way (k-way) merge to produce final sorted file(s).

Phase 1 — chunking & in-memory sort:- Read input in M-sized chunks; choose M = 800 MB to leave headroom for OS and buffers. Each chunk yields a sorted run written to disk as a compressed binary file (e.g., record length + serialized protobuf/Avro). Use an efficient in-memory sort (std::sort / Timsort) and write runs with checksum and sequence metadata.

Run sizing and count:- 1 TB / 0.8 GB ≈ 1250 runs. Too many for single merge — use multi-pass merge.

Phase 2 — k-way merge:- Use balanced multi-pass k-way merge. Choose k based on available memory for input buffers: allocate B_in per run and B_out for output. E.g., with 1 GB RAM: reserve 200 MB for heap and control, 700 MB for buffers → if B_in = 1 MB, k ≈ 700. Practical k ~100–500 depending on heap cost for priority queue. Use loser tree or min-heap to merge with O(log k) per record.

Buffer sizing & I/O optimization:- Use large sequential reads/writes (e.g., 256 KB–4 MB) per buffer to maximize throughput and use direct I/O (O_DIRECT) or buffered with fsync based on durability needs. Use read-ahead and async I/O (aio/io_uring) and double-buffering to overlap compute and I/O.

Parallelization:- CPU: sort chunks in parallel across cores — e.g., split the 800 MB chunk into per-thread partitions or run multiple chunk sorts concurrently (bounded to memory).- Disks: if multiple disks, stripe runs across disks (RAID0 or application-level striping) and schedule merge reads from different disks concurrently to utilize aggregate bandwidth.- Merge parallelism: do staged merges producing multiple intermediate sorted shards, then final merge per shard. Also consider partitioning by key range (sample + partition) so each partition sorts/merges independently and in parallel.

File format & metadata:- Use a compact, splittable binary format (Avro/Parquet/Arrow IPC) with checksums, record counts, min/max keys, and bloom filters for downstream filtering. Include manifest listing runs and their min/max for merge planning and recovery.

Failure handling & resiliency:- Write runs atomically (write to temp, fsync, rename). Maintain a durable manifest log (append-only) of completed runs and merge tasks. On failure, resume from manifest — re-run incomplete merge tasks; reuse existing runs. For long merges, write periodic checkpoints (output segments) so restarts don't repeat work. Verify checksums after reads.

Integration into ETL:- Expose as a component accepting input streams/files; support partitioned outputs keyed by range or hash for downstream steps. Provide APIs/CLI with config for memory, buffer sizes, disks, and parallelism. Emit metrics (I/O throughput, CPU, progress) to ETL orchestrator. For incremental ETL, support merge-with existing sorted datasets (merge-join style) and provide hooks for schema evolution.

Trade-offs:- Larger M reduces passes but increases memory pressure. Higher k reduces passes but increases per-record heap cost and open-file limits. Partitioning by key reduces merge complexity at cost of sampling overhead.

This design balances low memory, high throughput I/O, parallel CPU/disk utilization, and robustness suitable for production ETL.

EasyTechnical

39 practiced

Compare arrays and singly linked lists in terms of memory layout, random access, insertion and deletion costs, cache behavior, and typical use cases. As a solutions architect advising a high-throughput service, explain which you'd pick and why for different workloads.

Sample Answer

Arrays vs. singly linked lists — concise comparison and advice for high-throughput services.

Memory layout- Arrays: contiguous block of memory; elements stored sequentially.- Singly linked lists: nodes scattered in heap; each node stores value + next pointer.

Random access- Arrays: O(1) direct index access.- Linked lists: O(n) — must traverse from head.

Insertion / deletion costs- Arrays: O(n) worst-case for arbitrary insert/delete (shifting); O(1) at end if capacity available (amortized for dynamic arrays).- Linked lists: O(1) to insert/delete given pointer to predecessor; O(n) to find position.

Cache behavior- Arrays: excellent spatial locality → cache-friendly, fewer CPU cache misses, higher throughput.- Linked lists: poor locality → pointer-chasing causes many cache misses and pipeline stalls.

Typical use cases- Arrays: random access, bulk processing, numeric computations, buffering, lookup by index, dense storage.- Linked lists: frequent mid-list insertions/deletions when references to nodes are maintained, building queues/streams where node re-linking matters, memory-constrained systems with unpredictable sizes (rarely preferred).

Recommendations for a high-throughput service- Read-heavy or random-access workloads, batch processing, or CPU-bound algorithms: choose arrays (or dynamic arrays/vector). The contiguous layout gives far better cache utilization and throughput.- Write-heavy workloads with many arbitrary mid-list insertions and if you can keep pointers to insertion points: consider linked lists only when low-cost pointer edits outweigh cache penalties—but measure carefully.- High-concurrency queues/streams: prefer lock-free ring buffers (array-based) or segmented queues over naive linked lists for throughput and lower GC/alloc overhead.- Memory fragmentation / very large elements: consider array-of-structures vs structure-of-arrays trade-offs and use pooled allocators if allocations are frequent.

Bottom line: default to array-based structures for high throughput; use linked lists only for niche insertion/delete patterns where their O(1) pointer operations are essential and cache inefficiency is acceptable.

MediumTechnical

40 practiced

A CSV parsing library occasionally mis-parses quoted fields containing embedded newlines and escaped quotes. As an architect, list comprehensive unit and integration test cases you would require, state whether to follow RFC4180 or a custom rule-set, and outline measures to validate regressions in production.

Sample Answer

Unit tests (focused, fast, deterministic)- Basic happy path: unquoted fields, single-line records.- Quoted fields without special chars.- Quoted fields with embedded newline(s) (LF, CRLF) inside quotes.- Quoted fields with escaped quotes ("" per RFC4180) and variations like backslash-quote if supported.- Mixed cases: quoted field contains commas + newlines + escaped quotes.- Edge lengths: very long field, empty quoted field (""), empty unquoted field.- Malformed inputs: unmatched quote, quote in middle of unquoted field, trailing characters after close-quote.- Charset and encoding: UTF-8 multibyte characters inside quotes.- Streamed/parsing-chunked inputs: split a quoted field across buffer boundaries.

Integration tests (end-to-end)- Real-world file from clients: CRLF vs LF endings, BOM present.- Large file with millions of rows containing random embedded newlines/quotes.- Upstream/downstream compatibility: round-trip export→parse→export equals original.- Interoperability: files generated by Excel, Python csv, OpenRefine.- Failure modes: parser recovers sync after malformed record, logs location, and provides configurable behavior (skip/stop/repair).

RFC4180 vs custom rule-set- Default to RFC4180 as canonical baseline for compatibility (quoted fields use double quotes and double-double-quote escaping; fields with CR/LF permitted inside quotes).- Allow configurable relaxation/strictness flags: support for backslash escapes, lenient recovery, Excel quirks. Document and version the rule-set; prefer explicit switches rather than changing default.

Regression validation in production- Canary deploy parsing changes on small traffic; compare outputs with previous parser (byte-for-byte where possible) and log diffs.- Add synthetic fuzzed CSV test-suite running as part of CI and nightly scheduled jobs feeding into staging; use corpus from real customer files.- Schema/row-count/field-value sanity checks: alert on sudden delta (e.g., row count drop, field truncation, unexpected nulls).- Logging: capture parsing errors with sample payload snippets and offsets; redact PII.- Metrics and alerting: parse_errors, recovery_rate, average_record_length, percent_mismatch vs baseline; set SLAs and automated rollback triggers.- Provide a “safe mode” API that returns parsing diagnostics and original raw record for human review.

This plan balances standards compliance, pragmatic client compatibility, and safe rollout with observability to catch regressions quickly.

MediumTechnical

38 practiced

Implement in Python a function that given an unsorted list of integers and a target returns indices of the two numbers that add up to the target. Your solution should run in O(n) time using O(n) extra space. Explain trade-offs versus a sort-and-two-pointer O(n log n) approach and how you would test at scale.

Sample Answer

Approach: Use a single-pass hash table mapping value->index. For each number x at i, check if target-x exists in the map; if yes return indices. This yields O(n) time and O(n) extra space.

python

def two_sum(nums, target):
    """
    Return indices of two numbers such that they add up to target.
    Assumes exactly one solution exists (common LeetCode constraint).
    """
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return None  # or raise ValueError("No solution")

Key points:- Single pass, O(n) time, O(n) space.- Handles negatives, zeros, duplicates because we store index and check complement first.

Trade-offs vs sort-and-two-pointer (O(n log n) + O(1) space):- Hash approach preserves original indices (important for many requirements). Uses extra memory proportional to n.- Sort+two-pointer reduces memory but requires pairing values back to original indices (extra bookkeeping) and changes element order — undesirable if stable indices matter.- For very large arrays where memory is tight, sort approach might be chosen; for low-latency and index-preserving needs, hash approach preferred.

Testing at scale:- Unit tests: small arrays, duplicates, negatives, no-solution cases.- Property tests: randomized arrays with known injected pair.- Performance tests: large arrays (10M elements) in a memory-controlled environment to observe memory usage and throughput; profile GC and hash growth.- Production considerations: validate input sizes, use streaming or chunking if dataset exceeds memory, document memory/latency trade-offs in architecture decisions.

Unlock Full Question Bank

Get access to hundreds of Coding Fundamentals and Problem Solving interview questions and detailed answers.

Join thousands of developers preparing for their dream job.