Algorithmic Problem Solving Fundamentals Questions

Core foundation for solving entry level algorithmic problems. Focuses on arrays, strings, basic mathematics and number theory problems, simple bit manipulation, basic linked list and tree operations, stacks and queues, basic sorting and searching algorithms, simple recursion, and use of hash based data structures for counting and lookup. Emphasizes understanding asymptotic time and space complexity, selecting appropriate data structures for a task, and clear step by step problem solving including writing a brute force solution and analyzing correctness.

MediumTechnical

41 practiced

Implement a queue using two stacks in Python. Provide push, pop, peek, and empty operations with amortized O(1) time. Explain why amortized complexity is O(1) and discuss thread-safety considerations in a production SRE environment.

Sample Answer

Use two stacks: an input stack for push operations and an output stack for pop/peek. Push always appends to input. On pop/peek, if output is empty, transfer all items from input to output (reversing order). This gives amortized O(1) per operation because each element is moved at most once between stacks.

python

class MyQueue:
    def __init__(self):
        self._in = []   # push here
        self._out = []  # pop/peek from here

    def push(self, x):
        # O(1)
        self._in.append(x)

    def _transfer(self):
        # Move elements only when needed: O(n) occasionally
        while self._in:
            self._out.append(self._in.pop())

    def pop(self):
        # Amortized O(1)
        if not self._out:
            self._transfer()
        return self._out.pop()

    def peek(self):
        if not self._out:
            self._transfer()
        return self._out[-1]

    def empty(self):
        return not self._in and not self._out

Why amortized O(1):- Each element is pushed once (O(1)) and transferred at most once to _out, then popped once. Transfer cost amortized across those operations -> average constant time.

Thread-safety considerations (SRE perspective):- This implementation is not thread-safe. In production, protect shared state with synchronization: - Use a mutex (threading.Lock) around public methods to ensure atomicity and consistent state. - For high throughput, consider finer-grained locks or lock-free/atomic queues from the standard library (queue.Queue) which is thread-safe and optimized. - In async contexts, prefer asyncio.Queue. - For distributed systems, avoid in-process queues for cross-process communication; use durable message systems (Kafka, RabbitMQ) with backpressure and persistence.- Also consider performance trade-offs: locking adds latency; measure under realistic load, instrument latency, and choose appropriate primitives (e.g., concurrent queues, sharding) to meet SLOs.

EasyTechnical

50 practiced

Write a Python function to validate a string of parentheses that may contain '()', '{}', and '[]'. Return True if the input is well-formed (every opening bracket has a matching closing bracket in the correct order). This is useful to validate expressions or templates in configuration files.

Sample Answer

To validate balanced parentheses of types (), {}, and [], use a stack: push expected closing bracket when you see an opening one; when you see a closing bracket, check it matches the top of the stack. That yields O(n) time and O(n) space.

python

def is_well_formed(s: str) -> bool:
    """
    Return True if s contains well-formed parentheses among (), {}, [].
    """
    pairs = {'(': ')', '{': '}', '[': ']'}
    stack = []
    for ch in s:
        if ch in pairs:            # opening bracket
            stack.append(pairs[ch]) # push expected closing
        elif ch in pairs.values(): # closing bracket
            if not stack or stack.pop() != ch:
                return False
        else:
            # ignore other characters (or return False if only brackets allowed)
            continue
    return not stack

Key points:- We push expected closing characters to simplify comparisons.- Time complexity: O(n) — one pass over the string.- Space complexity: O(n) in worst case (all openings).Edge cases:- Empty string -> True.- Strings with non-bracket chars (current code ignores them; change to reject if necessary).- Unmatched or misordered brackets detected correctly.

HardTechnical

46 practiced

Design an approach to deduplicate a very large dataset of strings stored on disk that does not fit memory. Describe an external-memory algorithm (hash partitioning or external sorting), provide complexity and I/O analysis, and discuss practical implementation concerns (hash skew, disk throughput).

Sample Answer

Approach summary- Two standard external-memory options: hash-partition (stream + per-partition in-memory/disk dedupe) and external sort (multi-way external merge sort then single scan). Both are practical; choice depends on distribution, memory, and IO characteristics.

Hash-partitioning (preferred when keys hash uniformly)1. Partition phase: stream input, compute 64-bit hash for each string, write record to partition file P = ceil(N / target_partition_size). Use buffered writes and rotate files to avoid too many open fds.2. Per-partition dedupe: for each partition (fits in memory), read into memory (or sort chunk if slightly larger), dedupe with a hash set and write unique values to output.I/O: one read of input + one write per record to partitions + one read per partition + one write of unique output ≈ 3N reads/writes worst-case (depends on implementation). CPU: O(N) hashing; memory per partition = target_partition_size.Practical: choose partition size << available RAM. Mitigate hash skew by using 128-bit hash or two-level partitioning; detect oversized partitions and spill to secondary partitioning.

External sort (when stable ordering needed or partitions problematic)1. Read input in memory-sized chunks, sort each chunk in-memory, write sorted runs.2. Multi-way merge runs (fan-in based on file descriptors and memory buffers) to produce fully sorted stream.3. Single pass to emit unique keys by comparing adjacent records.I/O: external merge sort does ~2N * (1 + number_of_merge_passes) IO; optimal multi-way merge can reduce passes so total IO ≈ 2N to 4N. CPU: O(N log M) where M = memory-chunk size.Practical: tune run size and merge fan-in to minimize passes; use replacement selection to produce longer runs.

Complexity and I/O reasoning (rough)- Hash partition: O(N) time for hashing + O(N) dedupe; I/O ~ O(N) to O(3N) depending on write/read passes. Good when K (unique per partition) fits memory.- External sort: O(N log N) CPU dominated by per-record comparisons across runs; I/O ~ O(N * (1 + number_of_passes)). With enough memory/fan-in, passes drop to 1 so IO ≈ 2N.

Implementation concerns & SRE practicalities- Hash skew: monitor partition sizes, instrument metrics, and re-hash oversized partitions (adaptive two-pass). Use consistent hashing only for streaming append systems.- Disk throughput: maximize sequential IO, use large buffered writes (e.g., 4–16MB), avoid random writes. Use multiple disks or RAID/striping to increase throughput; prefer SSDs for random-access heavy workloads.- Concurrency: process partitions in parallel limited by IO bandwidth and CPU. Use a worker pool sized by disk bandwidth and CPU.- Memory and file descriptor limits: limit open files, use batching, and temp directories on fast disks.- Fault tolerance: write partition files atomically (temp names + rename), checkpoint progress, and design idempotent re-runs. Keep checksums (e.g., xxhash64) to detect corruption.- Verification & monitoring: sample counts, Bloom filter to estimate uniqueness, and end-to-end CRCs. Emit metrics: bytes read/written, max partition size, runtime per phase.- Security & privacy: encrypt temp files if data sensitive, and securely delete temps.

Recommendation- Start with hash-partitioning tuned to available RAM and IO; fall back to external sort if partition skew or ordering constraints arise. Instrument heavily and tune buffer sizes, fan-in, and concurrency to match real disk throughput.

EasyTechnical

61 practiced

Given a sorted array of integers (non-decreasing), implement a Python function to find the first occurrence index of a target value using binary search. If the target is not present return -1. Explain why binary search is O(log n) and provide careful handling of boundary conditions.

Sample Answer

To find the first occurrence of target in a non-decreasing sorted array, use a modified binary search that, when it finds target, continues searching left to ensure it's the first index. This keeps O(log n) behavior because each iteration halves the search interval.

python

def first_occurrence(nums, target):
    """
    Return index of first occurrence of target in sorted list nums, or -1 if missing.
    Deterministic, O(log n) time, O(1) space.
    """
    left, right = 0, len(nums) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow (defensive)
        if nums[mid] == target:
            result = mid           # record a candidate
            right = mid - 1        # continue searching left half for earlier occurrence
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Key points:- Use mid = left + (right-left)//2 to avoid arithmetic issues.- When target found, move right = mid-1 to find first occurrence rather than returning immediately.- Loop condition left <= right ensures empty ranges handled correctly.- Time complexity O(log n): each iteration halves the search interval, so number of iterations ~ log2(n). Space O(1).- Edge cases: empty array returns -1; all elements < target or > target handled by pointer movement; duplicates handled by continuing left search.- For SRE context: this deterministic, low-latency search is suitable for runtime checks in monitoring or low-overhead lookups in automation tools.

EasyTechnical

44 practiced

You are given an array of integers representing request latencies in milliseconds and a target latency threshold. Implement a function in Python that returns indices of two distinct requests whose latencies sum to the target. The function must run in O(n) time and O(n) space. If multiple pairs exist return any. If none exist return None. Example: input = [10, 20, 5, 15], target = 25 -> return (0,3) or (2,1).

Sample Answer

Approach: Use a hash map to store seen latency -> index while scanning the array once. For each value v at index i, check if target - v exists in the map; if so return the pair of indices. This yields O(n) time and O(n) space.

python

def two_sum_latencies(latencies, target):
    """
    Returns a tuple of two distinct indices whose values sum to target,
    or None if no such pair exists.
    """
    seen = {}  # maps value -> index
    for i, v in enumerate(latencies):
        complement = target - v
        if complement in seen:
            return (seen[complement], i)
        # store current value with its index
        seen[v] = i
    return None

# Example:
# two_sum_latencies([10, 20, 5, 15], 25) -> (0, 3) or (2, 1)

Key points:- Single pass; each element checked and inserted once.- Time Complexity: O(n). Space Complexity: O(n).- Handles duplicates because we store indices; if value equals complement, the earlier index is used.Edge cases:- Empty or length < 2 -> returns None- Multiple valid pairs -> returns the first found (which is acceptable)- Large arrays -> use Python dict which is amortized O(1) per lookup, suitable for SRE scripts processing telemetry data.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.