Programming Fundamentals and Code Quality Questions

Encompasses core programming skills, data structures, basic algorithms, language fundamentals, and code quality practices. Expect proficiency with arrays, strings, lists, hash maps or dictionaries, sets, common collection operations, basic sorting and searching algorithms, and tradeoffs between data structures. Understand control flow, functions and modular design, classes and object oriented programming concepts including encapsulation, inheritance, and polymorphism, exception handling, file input and output, and common language idioms for mainstream interview languages such as Python, Java, and C plus plus. Emphasizes writing clean, readable, maintainable code: meaningful naming, modular functions, small interfaces, handling edge cases and errors, logging and documentation, simple testing and debugging strategies, and awareness of time and space complexity for common operations. Candidates should be able to implement correct solutions, follow language specific idioms where appropriate, and demonstrate attention to code quality and readability.

HardTechnical

31 practiced

Discuss trade-offs between recursion and iteration: readability, stack usage, risk of stack overflow, and tail-call optimization availability across languages. Provide a recursive factorial implementation and a tail-recursive (or iterative) variant, and explain why tail recursion might not be optimized in Python and what alternatives exist.

Sample Answer

Recursion vs iteration — trade-offs- Readability: Recursion often maps directly to the problem (tree traversal, divide-and-conquer) and can be clearer; iteration can be more verbose for some algorithms but is explicit about control flow.- Stack usage and risk: Recursion uses the call stack per call frame; deep recursion increases memory use and risks stack overflow. Iteration uses a single frame and typically constant stack space (O(1)).- Tail-call optimization (TCO): If a language/runtime implements TCO, tail-recursive functions can run with constant stack like loops. Many functional languages (Scheme, Haskell) and some compilers guarantee TCO; JVM languages generally do not (Scala can annotate but JVM rarely optimizes); C compilers may optimize tail calls in some situations; CPython does not implement TCO.

Example — naive recursive factorial (clear but uses O(n) stack):

python

def factorial(n):
    """Simple recursion: O(n) time, O(n) stack."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Tail-recursive style (semantically tail-recursive) and iterative equivalent:

python

def factorial_tail(n, acc=1):
    """Tail-recursive style: accumulator carries result."""
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)

def factorial_iter(n):
    """Iterative: uses constant stack."""
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc

Why Python doesn't optimize tail recursion and alternatives- CPython intentionally omits TCO to keep tracebacks simple and to encourage iterative solutions for large-depth tasks. Because of that, factorial_tail will still overflow for large n.- Alternatives: - Use iterative implementations (recommended). - Convert recursion to an explicit stack/queue data structure. - Use sys.setrecursionlimit cautiously (doesn't change C stack limits). - Use a different interpreter/implementation that may optimize (some PyPy builds or specialized interpreters), or implement critical recursion in C extension. - Use trampolines (manual loop that repeatedly invokes thunks) to emulate TCO at the cost of complexity.

When to choose which:- Use recursion when it simplifies correctness and depth is small or when language/runtime guarantees TCO.- Use iteration or explicit stacks for production code with potentially large depths to avoid runtime errors and reduce memory use.

MediumTechnical

32 practiced

Explain immutability versus mutability, their trade-offs for performance and safety, and how immutability aids concurrent programming. Provide examples in Java (String vs StringBuilder) and Python (tuple vs list), and explain when immutability might become a performance problem.

Sample Answer

Immutability means an object’s state cannot change after creation; mutability allows in-place modification. Trade-offs: immutability improves safety (no accidental side-effects, easier reasoning, safer sharing) and simplifies concurrency (no locks needed to read shared immutable state). Mutability can be faster for heavy in-place updates because it avoids allocations and copying.

Java example — String (immutable) vs StringBuilder (mutable):

java

// String: each concat creates new object
String s = "a";
s = s + "b"; // creates new String

// StringBuilder: mutate in place
StringBuilder sb = new StringBuilder("a");
sb.append("b"); // modifies internal buffer

Use String for keys, constants, safe sharing; use StringBuilder for many concatenations to avoid O(n^2) copies.

Python example — tuple (immutable) vs list (mutable):

python

t = (1,2,3)
# t[0] = 9 -> TypeError

l = [1,2,3]
l[0] = 9  # in-place change

Immutability aids concurrency by eliminating data races: threads can freely read shared immutable objects without synchronization. It also enables safe caching and structural sharing (persistent data structures).

When immutability hurts performance:- Hot loops that do many small updates (creates many short-lived objects -> GC pressure)- Large data structures where each change copies most of the structure (unless persistent/structurally-shared)- Real-time or memory-constrained systems where extra allocations are unacceptable

Guideline: prefer immutability for safety and correctness; switch to mutable or use specialized mutable buffers/structural-sharing libraries when profiling shows clear performance bottlenecks.

MediumTechnical

32 practiced

Explain what race conditions and deadlocks are in multithreaded programs. For each, give a concise pseudocode example that reproduces the problem and list practical strategies to prevent them (mutexes, atomic operations, lock ordering, timeouts, avoiding shared mutable state).

Sample Answer

Race condition: multiple threads access and modify shared data concurrently so the final result depends on timing order.

Pseudocode (race):

python

# two threads increment a shared counter without sync
counter = 0

def increment():
    global counter
    temp = counter       # read
    temp += 1            # modify
    counter = temp       # write

# Thread A and Thread B both run increment()

If A and B interleave reads/writes, one increment can be lost.

Prevention strategies (race):- Mutex/lock around read-modify-write (e.g., lock.acquire(); counter += 1; lock.release()).- Atomic operations (atomic increment provided by platform).- Use higher-level concurrency primitives (thread-safe queues, concurrent collections).- Avoid shared mutable state: prefer message passing, immutability, or functional patterns.- Minimize critical section scope to reduce contention.

Deadlock: two or more threads wait indefinitely for locks held by each other.

Pseudocode (deadlock):

python

# Thread 1
lockA.acquire()
sleep(0.1)
lockB.acquire()   # blocks waiting for lockB

# Thread 2
lockB.acquire()
sleep(0.1)
lockA.acquire()   # blocks waiting for lockA

Both wait forever.

Prevention strategies (deadlock):- Lock ordering: always acquire locks in a globally consistent order.- Try-lock with timeouts / backoff: if cannot acquire both, release and retry.- Reduce lock granularity or use lock-free algorithms.- Hold fewer locks and for shorter durations.- Use deadlock detection tools or design using immutable/shared-read, or actor/message-passing models.

These techniques combined (atomic ops where possible, consistent ordering, timeouts, avoiding shared mutable state) reduce both race conditions and deadlocks in real systems.

MediumTechnical

29 practiced

Implement the quickselect algorithm in C++ to find the kth largest element in an unsorted vector<int>. Aim for average O(n) time and explain how randomizing pivot choice reduces the chance of worst-case O(n^2) behavior. Provide clean, idiomatic C++ code.

Sample Answer

Approach: Use Quickselect (partition-based selection). Convert kth largest to index k' = n - k and run Quickselect to find the kth smallest index. Randomizing pivot by choosing a random index each partition reduces probability of repeatedly poor pivots and makes average runtime O(n).

cpp

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& a, int lo, int hi, int pivotIndex) {
    int pivot = a[pivotIndex];
    swap(a[pivotIndex], a[hi]);           // move pivot to end
    int store = lo;
    for (int i = lo; i < hi; ++i) {
        if (a[i] < pivot) {
            swap(a[store++], a[i]);
        }
    }
    swap(a[store], a[hi]);                // move pivot to its final place
    return store;
}

int quickselect(vector<int>& a, int lo, int hi, int kSmallest, mt19937& rng) {
    while (lo <= hi) {
        uniform_int_distribution<int> dist(lo, hi);
        int pivotIndex = dist(rng);
        int pivotPos = partition(a, lo, hi, pivotIndex);
        if (pivotPos == kSmallest) return a[pivotPos];
        if (kSmallest < pivotPos) hi = pivotPos - 1;
        else lo = pivotPos + 1;
    }
    return -1; // should not reach here if inputs valid
}

int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    if (k < 1 || k > n) throw invalid_argument("k out of range");
    int kSmallest = n - k;
    random_device rd;
    mt19937 rng(rd());
    return quickselect(nums, 0, n - 1, kSmallest, rng);
}

Key points:- Average time: O(n), worst-case O(n^2) if pivots are always unlucky.- Random pivoting makes worst-case exponentially unlikely (expected linear time).- Space: O(1) extra (in-place), O(log n) stack if recursive; this iterative loop avoids deep recursion.Edge cases: k out of range, duplicates (handled), empty vector.

HardTechnical

28 practiced

Outline how to implement a lock-free stack in C++ using std::atomic and compare-and-swap (CAS). Explain the ABA problem and describe mitigation strategies such as tagged pointers, hazard pointers, and epoch-based reclamation. Also discuss safe memory reclamation approaches.

Sample Answer

Approach: implement a singly-linked stack using an atomic head pointer and CAS. To avoid ABA, use a tagged pointer (version counter) in the atomic. For safe reclamation, describe hazard pointers and epoch-based reclamation (EBR) as alternatives to immediate delete.

C++ implementation (tagged pointer with 16-bit tag example):

cpp

#include <atomic>
#include <cstdint>
#include <memory>

template<typename T>
class LockFreeStack {
    struct Node { T value; Node* next; };
    // pack pointer + 16-bit tag into 64-bit on x86_64
    struct Ptr {
        uint64_t raw;
        Ptr(Node* p = nullptr, uint16_t tag = 0) {
            raw = (uint64_t)p | (uint64_t(tag) << 48);
        }
        Node* ptr() const { return (Node*)(raw & 0x0000FFFFFFFFFFFFULL); }
        uint16_t tag() const { return uint16_t(raw >> 48); }
    };
    std::atomic<uint64_t> head; // store Ptr::raw

public:
    void push(const T& v) {
        Node* n = new Node{v, nullptr};
        while (true) {
            Ptr old{(Node*) (head.load()), 0};
            old.raw = head.load();
            n->next = old.ptr();
            Ptr neu{n, uint16_t(old.tag()+1)};
            if (head.compare_exchange_weak(old.raw, neu.raw)) return;
        }
    }

    bool pop(T& out) {
        while (true) {
            uint64_t oldRaw = head.load();
            Ptr old; old.raw = oldRaw;
            Node* p = old.ptr();
            if (!p) return false;
            Ptr neu{p->next, uint16_t(old.tag()+1)};
            if (head.compare_exchange_weak(oldRaw, neu.raw)) {
                out = std::move(p->value);
                // memory reclamation: can't delete(p) here safely without hazard pointers/EBR
                return true;
            }
        }
    }
};

Key concepts:- ABA problem: CAS sees same pointer value twice but intermediate changes (A→B→A) occurred; logic may be incorrect.- Tagged pointers: attach a monotonically-increasing tag/version to break ABA; CAS compares both pointer and tag.- Hazard pointers: each thread publishes pointers it may access; reclamation defers deletes until no hazard points to object. Safe and deterministic but requires per-thread storage and scan on retire.- Epoch-based reclamation (EBR): threads enter epochs; retired nodes are reclaimed once all threads advanced past the epoch. Lower overhead but requires thread liveness (blocked threads delay reclamation).- Other approaches: reference counting (atomic-heavy), read-copy-update (RCU) for readers-writer heavy workloads.

Safe memory reclamation:- Never delete nodes immediately after successful CAS unless you can guarantee no other thread holds a pointer.- Use hazard pointers when correctness under thread stalls is required.- Use EBR for higher throughput when threads are cooperative.- Combine techniques (e.g., tags + hazard pointers) for robust lock-free stacks.

Complexity: push/pop are amortized O(1) CPU work; memory overhead and reclamation cost depend on chosen reclamation strategy.

Edge cases:- Pointer/tag overflow (wraparound): choose sufficient tag width or handle wrap.- Thread crash/starvation: EBR is sensitive to stalled threads; hazard pointers handle crashes better.- Platform pointer size/atomic width: ensure atomic fits pointer+tag (use std::atomic<std::uintptr_t> or double-wide CAS if available).

Unlock Full Question Bank

Get access to hundreds of Programming Fundamentals and Code Quality interview questions and detailed answers.

Join thousands of developers preparing for their dream job.