Medium Difficulty Coding Problems Questions

Practice and master medium difficulty algorithmic coding problems that commonly appear in technical interviews. Topics include arrays, strings, linked lists, trees, graphs, hash tables, and dynamic programming. Typical techniques to know are two pointer methods, sliding window, breadth first search and depth first search, recursion and backtracking, memoization and bottom up dynamic programming, sorting and greedy heuristics, and common data structure operations. Interviewers evaluate systematic problem solving: clarifying requirements, designing a correct solution, explaining time and space complexity, handling edge cases and input validation, writing clean and working code in your chosen language, and then iterating to optimize performance. Candidates should be comfortable explaining tradeoffs between approaches, testing with example cases, and communicating thought process clearly while coding under time constraints.

HardTechnical

51 practiced

You receive logs from several services with unsynchronized clocks. Implement in Python an event ordering function that, given events each with a local timestamp and a service id, produces a plausible total order using Lamport timestamps or logical clocks. Provide code to assign Lamport timestamps and then sort events deterministically. Discuss tie-break rules.

Sample Answer

Approach: We can't reconstruct true causal order without message metadata, but we can produce a plausible, deterministic total order that preserves per-service (intra-process) ordering using Lamport-style logical clocks. Steps: (1) for each service, sort its events by local timestamp and assign a per-service sequence (logical clock) that increments — this preserves local order; (2) combine all events and sort by a deterministic composite key: (lamport, local_ts, service_id, seq). Ties broken by stable fields (service id, sequence) to guarantee reproducibility.

Code (assign lamport = per-service sequence number, then deterministic sort):

python

from typing import List, Dict, Any, Tuple

def order_events(events: List[Dict[str, Any]]) -> List[Dict[str, Any]]:
    """
    events: list of dicts with keys: 'service_id' (str), 'local_ts' (float/int), plus any payload
    Returns: list of events annotated with 'lamport' and 'seq', sorted into a plausible total order.
    """
    # 1) Group by service and sort by local timestamp to preserve intra-service order
    by_service: Dict[str, List[Dict[str, Any]]] = {}
    for e in events:
        by_service.setdefault(e['service_id'], []).append(e)
    for svc, lst in by_service.items():
        lst.sort(key=lambda x: (x['local_ts'],))  # stable sort: earlier local_ts first

    # 2) Assign per-service sequence numbers (Lamport-style logical clocks per site)
    annotated: List[Dict[str, Any]] = []
    for svc, lst in by_service.items():
        seq = 0
        for ev in lst:
            seq += 1
            a = ev.copy()
            a['seq'] = seq            # per-service logical clock
            a['lamport'] = seq       # using seq as Lamport timestamp (plausible)
            a['service_id'] = svc
            annotated.append(a)

    # 3) Deterministic total ordering: primary lamport, secondary local_ts, then service id, then seq
    ordered = sorted(
        annotated,
        key=lambda x: (x['lamport'], x['local_ts'], x['service_id'], x['seq'])
    )
    return ordered

Key points and reasoning:- Using per-service sequence numbers as Lamport timestamps preserves causal order within each service (if A before B locally, lamport(A)<lamport(B)).- Without message send/receive metadata we cannot infer inter-service causality; using local_ts as a secondary key uses clock skew heuristically.- Deterministic tie-break: service_id (lexicographic) then seq ensures stable, reproducible total order.

Complexity:- Grouping & per-service sorts: O(n log n) total (dominated by sorting).- Final sort: O(n log n).- Space: O(n) for annotated list.

Edge cases:- Events with identical local_ts within same service: sequence assignment orders them deterministically by input sort stability.- Clock skew: local_ts only heuristic; if you have message IDs (send/recv) you should incorporate them to compute true Lamport clocks (update receiving event lamport = max(local, sender_lamport)+1).- Large scale: stream processing version can assign seq incrementally per service and use external sort or merge strategies for very large logs.

MediumTechnical

46 practiced

Given a simulated filesystem with files represented as (path, content), implement find_duplicate_files(files) in Python that returns groups of file paths with identical content. Optimize for large files by using hashing in stages: size, partial hash, and full hash. Discuss collision handling and memory trade-offs.

Sample Answer

To detect duplicate files efficiently, group by file size (cheap), then by partial hash (e.g., first 4KB) to filter, and finally by full hash for confirmation. This minimizes expensive hashing for large files.

python

import hashlib
from collections import defaultdict

def hash_bytes(data, algo='sha256'):
    h = hashlib.new(algo)
    h.update(data)
    return h.hexdigest()

def find_duplicate_files(files):
    """
    files: iterable of (path, content_bytes)
    Returns list of lists: groups of paths with identical content
    """
    # Stage 1: group by size
    by_size = defaultdict(list)
    for path, content in files:
        by_size[len(content)].append((path, content))

    # Stage 2: group by partial hash (first 4KB)
    by_partial = defaultdict(list)
    for size, items in by_size.items():
        if len(items) < 2:
            continue
        for path, content in items:
            partial = content[:4096]
            by_partial[(size, hash_bytes(partial))].append((path, content))

    # Stage 3: group by full hash
    by_full = defaultdict(list)
    for key, items in by_partial.items():
        if len(items) < 2:
            continue
        for path, content in items:
            full = hash_bytes(content)
            by_full[full].append(path)

    # Collect groups with >1 path
    return [paths for paths in by_full.values() if len(paths) > 1]

Key points:- Use size -> partial hash -> full hash to avoid hashing all bytes for unique files.- Use a strong hash (sha256) to reduce collisions. For absolute safety, on full-hash matches, a byte-by-byte compare can eliminate theoretical collisions.- Memory trade-offs: storing file contents or hashes. For very large datasets, stream content and store only hashes and paths; use chunked reading from disk rather than loading whole files. Partial-hash size trades false positives vs cost: larger partial reduces work later but reads more data.- Complexity: O(n) reads proportional to files sizes for necessary stages; hashing cost depends on how many files reach each stage.

MediumTechnical

86 practiced

Implement an LRU cache class in Python with methods get(key) and put(key, value). The cache must run both operations in O(1) time, support a configurable capacity, and evict the least recently used item when full. Provide a short example usage and explain how this is useful for caching in SRE automation.

Sample Answer

To implement an LRU cache in O(1) for get and put, combine a hashmap for O(1) lookup with a doubly linked list to track recency (head = most recent, tail = least recent). On access, move node to head. On put when capacity exceeded, remove tail and its hashmap entry.

python

class Node:
    def __init__(self, k, v):
        self.key = k
        self.val = v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                 # key -> Node
        # dummy head/tail to simplify edge cases
        self.head, self.tail = Node(0,0), Node(0,0)
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if not node:
            return -1
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key, value):
        node = self.map.get(key)
        if node:
            node.val = value
            self._remove(node)
            self._add_to_head(node)
            return
        if len(self.map) >= self.cap:
            # evict LRU
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        new = Node(key, value)
        self._add_to_head(new)
        self.map[key] = new

Key points:- Hashmap: O(1) lookup; doubly linked list: O(1) insert/delete.- Time: get/put O(1). Space: O(capacity).- Edge cases: capacity <= 0, repeated puts, updating existing key — dummy nodes avoid null checks.

Example usage:cache = LRUCache(2); cache.put('a',1); cache.put('b',2); cache.get('a') -> 1; cache.put('c',3) evicts 'b'.

SRE relevance: Use LRU caches in automation to memoize recent API responses, rate-limit tokens, or DNS lookups to reduce external calls, lower latency, and avoid overloading services during incidents. The O(1) guarantees keep automation fast and predictable under load.

MediumTechnical

53 practiced

Given N services and a list of dependency pairs (A depends on B), implement in Python a function that detects if the dependency graph has cycles. If acyclic, return a valid deployment order using topological sort. Inputs: services as list of strings, dependencies as list of pairs [A,B]. Explain complexity and how this maps to deployment orchestration.

Sample Answer

Approach: Model services as nodes in a directed graph where an edge B → A means A depends on B (B must be deployed before A). Detect cycles while performing Kahn’s topological sort (BFS with in-degree). If a cycle exists, return an indicator; otherwise return a valid deployment order.

python

from collections import defaultdict, deque
from typing import List, Tuple, Optional

def resolve_dependencies(services: List[str], dependencies: List[Tuple[str, str]]) -> Optional[List[str]]:
    """
    Returns a topological ordering (deployment order) if acyclic,
    else returns None to indicate a cycle.
    dependencies: list of (A, B) meaning A depends on B.
    """
    graph = defaultdict(list)      # edge B -> A
    indeg = {s: 0 for s in services}

    for a, b in dependencies:
        if b not in indeg: indeg[b] = 0
        if a not in indeg: indeg[a] = 0
        graph[b].append(a)
        indeg[a] += 1

    q = deque([s for s, d in indeg.items() if d == 0])
    order = []

    while q:
        node = q.popleft()
        order.append(node)
        for neigh in graph[node]:
            indeg[neigh] -= 1
            if indeg[neigh] == 0:
                q.append(neigh)

    if len(order) != len(indeg):
        return None  # cycle detected
    return order

Key points:- Time complexity: O(N + M) where N = services, M = dependencies.- Space complexity: O(N + M) for graph and indegree map.- Edge cases: services with no deps, dependencies referencing unknown services (handled by inserting keys), duplicate pairs.- Deployment mapping: The topological order yields a safe sequence to deploy services so prerequisites are up first. In orchestration, you can parallelize deployments of services at the same "level" (same indegree zero batch), add health checks before marking a node deployed, and implement rollback on failures. Cycle detection prevents deadlocked deployments and surfaces circular dependencies to fix before rollout.

HardTechnical

63 practiced

Given a directed graph where edges have latency weight and each edge also has a reliability probability between 0 and 1, implement in Python an algorithm to find a path from source to target that maximizes overall reliability subject to total latency <= L. Input sizes are small enough to allow pseudo-polynomial solutions. Outline stateful Dijkstra-like DP and implement it.

Sample Answer

Approach: treat latency as a constrained resource and maximize multiplicative reliability (product of edge probabilities). Take log to convert product → sum of logs (maximize sum of logs). Use a stateful Dijkstra/DP where state is (node, used_latency). For pseudo-polynomial L (integer latencies), maintain best log-reliability seen for each (node, t) and use a max-priority queue over log-reliability. This is like knapsack+shortest-path.

python

import heapq
import math
from collections import defaultdict

def max_reliability_with_latency(graph, src, dst, L):
    """
    graph: dict[u] = list of (v, latency:int, reliability:float)
    latencies assumed integer and non-negative
    Returns: (best_reliability, path) where best_reliability in [0,1]
    """
    # dp[node][t] = max log-reliability achievable reaching node with total latency t
    dp = defaultdict(lambda: dict())
    # parent for path reconstruction: parent[(node,t)] = (prev_node, prev_t)
    parent = {}
    # max-heap by log-reliability (use negative for heapq)
    pq = []
    dp[src][0] = 0.0  # log(1)=0
    heapq.heappush(pq, (-0.0, src, 0))
    
    while pq:
        neg_logr, u, t = heapq.heappop(pq)
        logr = -neg_logr
        # skip stale
        if dp[u].get(t, -math.inf) != logr:
            continue
        if u == dst:
            # we could continue to find potentially better at other latencies <= L
            pass
        for v, lat, rel in graph.get(u, ()):
            nt = t + lat
            if nt > L:
                continue
            if rel <= 0:
                continue
            nlog = logr + math.log(rel)
            if nlog > dp[v].get(nt, -math.inf):
                dp[v][nt] = nlog
                parent[(v, nt)] = (u, t)
                heapq.heappush(pq, (-nlog, v, nt))
    # find best at dst over all t<=L
    best_t, best_log = None, -math.inf
    for t, logr in dp.get(dst, {}).items():
        if logr > best_log:
            best_log = logr
            best_t = t
    if best_t is None:
        return 0.0, []  # no feasible path
    # reconstruct path
    path = []
    cur = (dst, best_t)
    while cur[0] != src or cur[1] != 0:
        node, tt = cur
        path.append(node)
        cur = parent.get(cur)
        if cur is None:
            break
    path.append(src)
    path.reverse()
    return math.exp(best_log), path

Key points:- Using log turns multiplication into addition and avoids underflow.- State is (node, total_latency) — keep best log-reliability per state.- Priority queue explores better reliability states first; complexity O(E * L * log(E*L)) roughly.Edge cases:- Zero reliability edges (skip), zero latencies, unreachable target.Alternatives:- If latencies are large floats, discretize or switch to Lagrangian relaxation (maximize logr - lambda * latency) and binary search lambda.

Unlock Full Question Bank

Get access to hundreds of Medium Difficulty Coding Problems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.