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

39 practiced

Implement binary_search(nums, target) in Python to return the leftmost index of target in a sorted ascending array nums, or -1 if not found. Provide both iterative and recursive variants and explain why mid is usually calculated as mid = left + (right - left) // 2.

Sample Answer

To find the leftmost index of target in a sorted ascending array, use binary search but when nums[mid] == target continue searching left (right = mid - 1) to find the first occurrence.

Approach: maintain [left, right] inclusive window. If nums[mid] < target -> search right half; if > -> search left half; if == -> record mid and continue left.

python

def binary_search_iterative(nums, target):
    """Return leftmost index of target or -1."""
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow and is clearer
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            result = mid
            right = mid - 1  # keep searching left half
    return result

def binary_search_recursive(nums, target):
    """Recursive wrapper returning leftmost index or -1."""
    def helper(left, right):
        if left > right:
            return -1
        mid = left + (right - left) // 2
        if nums[mid] < target:
            return helper(mid + 1, right)
        elif nums[mid] > target:
            return helper(left, mid - 1)
        else:
            left_res = helper(left, mid - 1)
            return left_res if left_res != -1 else mid
    return helper(0, len(nums) - 1)

Key points:- mid = left + (right - left) // 2 prevents integer overflow in languages with fixed int ranges and is clearer about distance from left.- Time: O(log n). Space: O(1) iterative, O(log n) recursive (call stack).Edge cases: empty array, all elements equal, target at boundaries. In SRE work, prefer iterative for predictable stack use.

HardTechnical

36 practiced

Implement a thread-safe concurrent LRU cache in Python or Java that supports get and put with high concurrency. Discuss design options: coarse-grained lock, lock striping, per-bucket LRU, and the trade-offs for SRE in production.

Sample Answer

Approach: Use lock striping (segmented cache) to allow high concurrency: split key space into N segments; each segment has its own ConcurrentHashMap and a doubly-linked LRU list protected by a ReentrantLock. This gives near-lock-free reads across segments and bounded lock contention during updates. I'll provide a concise Java implementation and then discuss trade-offs (coarse-grained lock, per-bucket LRU, alternatives) and SRE considerations.

java

import java.util.concurrent.*;
import java.util.concurrent.locks.*;

public class SegmentedLRUCache<K,V> {
  private final Segment<K,V>[] segments;
  private final int segmentMask;

  static final class Node<K,V>{
    final K key; V value;
    Node<K,V> prev, next;
    Node(K k, V v){ key=k; value=v; }
  }

  static final class Segment<K,V>{
    final ReentrantLock lock = new ReentrantLock();
    final ConcurrentHashMap<K,Node<K,V>> map = new ConcurrentHashMap<>();
    final int capacity;
    Node<K,V> head, tail; // LRU: tail oldest
    Segment(int capacity){ this.capacity = capacity; }

    V get(K key){
      Node<K,V> n = map.get(key);
      if(n==null) return null;
      lock.lock();
      try { moveToHead(n); return n.value; }
      finally { lock.unlock(); }
    }

    void put(K key, V value){
      lock.lock();
      try {
        Node<K,V> n = map.get(key);
        if(n!=null){ n.value=value; moveToHead(n); return; }
        n = new Node<>(key,value);
        addHead(n);
        map.put(key,n);
        if(map.size()>capacity) {
          Node<K,V> ev = removeTail();
          if(ev!=null) map.remove(ev.key);
        }
      } finally { lock.unlock(); }
    }

    private void moveToHead(Node<K,V> n){
      if(n==head) return;
      // unlink
      if(n.prev!=null) n.prev.next = n.next;
      if(n.next!=null) n.next.prev = n.prev;
      if(n==tail) tail = n.prev;
      addHead(n);
    }
    private void addHead(Node<K,V> n){
      n.prev = null; n.next = head;
      if(head!=null) head.prev = n;
      head = n;
      if(tail==null) tail = n;
    }
    private Node<K,V> removeTail(){
      if(tail==null) return null;
      Node<K,V> r = tail;
      if(tail.prev!=null) tail.prev.next = null;
      tail = tail.prev;
      if(tail==null) head = null;
      r.prev = r.next = null;
      return r;
    }
  }

  @SuppressWarnings("unchecked")
  public SegmentedLRUCache(int totalCapacity, int concurrency){
    int segs = 1;
    while(segs < concurrency) segs <<=1;
    segmentMask = segs -1;
    segments = new Segment[segs];
    int per = Math.max(1, totalCapacity / segs);
    for(int i=0;i<segs;i++) segments[i] = new Segment<>(per);
  }

  private int idx(Object key){ return (key.hashCode() & Integer.MAX_VALUE) & segmentMask; }

  public V get(K key){ return segments[idx(key)].get(key); }
  public void put(K key, V value){ segments[idx(key)].put(key,value); }
}

Key points & trade-offs:- Coarse-grained lock: simple but serializes all ops → poor throughput under concurrency.- Lock striping/segmented (above): good balance — parallelism across segments, bounded eviction per-segment, predictable contention.- Per-bucket LRU (one LRU per hash bucket): minimizes lock scope further but increases complexity and memory; harder to maintain global capacity and causes uneven eviction.- Alternatives: pure ConcurrentHashMap + background eviction (approx-LRU) for very high throughput; use Caffeine/Guava for production-grade caches.

SRE considerations:- Observability: expose metrics (hit/miss, eviction rate, segment contention, latency).- Capacity planning: segmented per-segment capacity can cause hot-key skew; consider adaptive rebalancing or global admission policy.- Failures & backpressure: avoid blocking callers on long lock waits; consider async writes or request coalescing.- Testing: load-test with realistic key distribution, measure contention and GC impact.- Safety: consider TTLs, write-behind persistence, and metrics-based autoscaling.

Complexity:- get/put average O(1). Space O(N). Segment count trades latency vs concurrency.

EasyTechnical

33 practiced

Write a function is_valid_parentheses(s) in Python to determine whether a string containing '()[]{}' is balanced. The function should run in O(n) time and O(n) space. Describe how you would handle unexpected characters or streaming input.

Sample Answer

Use a stack to push opening brackets and match them with closing brackets as you scan the string once. This yields O(n) time and O(n) space.

python

def is_valid_parentheses(s: str) -> bool:
    """
    Return True if s contains balanced parentheses among () [] {}.
    Runs O(n) time, O(n) space.
    """
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():         # opening
            stack.append(ch)
        elif ch in pairs:               # closing
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            # unexpected character: skip or treat as error depending on policy
            # Here we choose to ignore non-bracket chars (common in logs/streams).
            continue
    return not stack

Key points:- Single pass stack algorithm; push opens, pop and compare on closes.- Time: O(n). Space: O(n) worst-case (all opens).- Edge cases: empty string → True; unmatched opens/closes → False; mixed duplicates and nesting handled.Handling unexpected characters:- Option A (lenient): ignore non-bracket chars as above — useful when parsing logs/messages.- Option B (strict): raise ValueError or return False on unexpected chars — use for strict input validation.Handling streaming input:- Maintain the stack across chunks; process each chunk sequentially.- At end of stream, valid only if stack is empty.Operational notes for SREs:- Add input validation, bounds checks, and instrument counters for malformed inputs to alert if unexpected-character rate spikes.

MediumTechnical

39 practiced

Implement debounce(func, wait_ms) semantics in Python for log aggregation: repeated events within wait_ms should be collapsed into a single action. Provide thread-safe behavior and explain how you'd test correctness under concurrency.

Sample Answer

Approach: implement a Debouncer object that collects events and schedules a single timer to call the provided handler after wait_ms of inactivity. Use a threading.Lock for all shared state (pending aggregated payload, timer handle, canceled flag) so calls from multiple threads are safe. On each event, acquire lock, update aggregation, cancel and reschedule timer. When timer fires, call handler outside the lock to avoid deadlocks.

python

import threading
import time
from typing import Callable, Any, Optional

class Debouncer:
    def __init__(self, func: Callable[[Any], None], wait_ms: int):
        self.func = func
        self.wait = wait_ms / 1000.0
        self.lock = threading.Lock()
        self.timer: Optional[threading.Timer] = None
        self.aggregated = None  # e.g., count or last event
        self.cancelled = False

    def _timer_cb(self):
        # swap out payload under lock then call handler without lock
        with self.lock:
            if self.cancelled:
                return
            payload = self.aggregated
            self.aggregated = None
            self.timer = None
        try:
            self.func(payload)
        except Exception:
            # In production log exception; don't re-raise in background thread
            pass

    def event(self, payload: Any):
        """Called for each incoming event. Aggregates payload (example: count)."""
        with self.lock:
            if self.cancelled:
                return
            # Example aggregation: count events and keep last payload
            if self.aggregated is None:
                self.aggregated = {"count": 1, "last": payload}
            else:
                self.aggregated["count"] += 1
                self.aggregated["last"] = payload
            # cancel old timer and schedule new one
            if self.timer is not None:
                self.timer.cancel()
            self.timer = threading.Timer(self.wait, self._timer_cb)
            self.timer.daemon = True
            self.timer.start()

    def flush(self):
        """Force immediate delivery of current aggregate."""
        with self.lock:
            if self.timer is not None:
                self.timer.cancel()
                self.timer = None
            if self.aggregated is None:
                return
            payload = self.aggregated
            self.aggregated = None
        self.func(payload)

    def stop(self):
        with self.lock:
            self.cancelled = True
            if self.timer is not None:
                self.timer.cancel()
                self.timer = None
            self.aggregated = None

Key points:- Lock protects timer and aggregated payload; timer callback swaps state then calls handler unlocked.- Aggregation strategy is pluggable (count, merge logs, unique keys).- Using threading.Timer keeps simple timing semantics; alternative: single background thread and heap of timers for high throughput.

Concurrency testing:- Unit test with a threads pool where N threads call debouncer.event(...) rapidly; use a thread-safe list to record handler calls and Barrier to start simultaneously.- Assert number of handler invocations equals expected collapsed counts (e.g., with bursts separated by >wait_ms).- Include stress tests with random inter-arrival delays, repeated runs to catch races.- Use small wait_ms (10-50ms) for speed but allow timeouts in tests; mock or inject time for deterministic tests if needed.

Complexity: O(1) per event (lock + timer ops). Edge cases: handler exceptions, cancellation, shutdown during callback, extremely high event rate (consider batching or move timing to dedicated scheduler).

MediumTechnical

36 practiced

Implement a RunningMedian class in Python supporting add(num) and get_median() operations. Each add must run in O(log n) time and get_median in O(1) using two heaps (max-heap and min-heap). Explain how this helps compute median latency in monitoring.

Sample Answer

Approach: Keep two heaps — a max-heap for the lower half and a min-heap for the upper half. In Python use heapq (min-heap); simulate max-heap by pushing negatives. Maintain size invariant: sizes differ by at most 1. add(num) is O(log n); get_median() O(1).

python

import heapq

class RunningMedian:
    def __init__(self):
        # max_heap stores negatives for the lower half
        self.max_heap = []  # max-heap via negatives
        self.min_heap = []  # min-heap for upper half

    def add(self, num: float) -> None:
        # Insert into appropriate heap
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        # Rebalance so size difference <= 1
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap) + 1:
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def get_median(self) -> float:
        if not self.max_heap and not self.min_heap:
            raise IndexError("no elements")
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        if len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]
        # even count
        return (-self.max_heap[0] + self.min_heap[0]) / 2.0

Key points:- add: O(log n) due to heap push/pop.- get_median: O(1) peek at heap tops.- Handles duplicates and floats; raises on empty.

Monitoring application (SRE): Use RunningMedian to track median latency of requests in sliding windows or streaming telemetry. Median is robust to outliers (unlike mean), so it gives stable signal for SLO tracking and alerting. Combine with histograms or quantile sketches for long-term retention and to compute p95/p99 alongside median for broader latency insight.

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.