Programming Fundamentals Interview Questions

It describes how the work grows as the input grows.

Big O describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constant factors.

Think about access by position versus inserting in the middle.

Arrays win for random access and cache-friendliness; linked lists win when you frequently insert or remove items in the middle and already hold a reference to the node.

Every recursive function needs a base case that stops the recursion.

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. It needs a base case that returns without recursing, or it will never stop.

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

Mention that Python limits recursion depth (about 1000 calls by default), so deep recursion is often rewritten as a loop.

Think of a pile of plates versus a line at a ticket counter.

• A stack is LIFO (last in, first out): you add and remove from the same end, like a pile of plates. Used for undo history and function calls.
• A queue is FIFO (first in, first out): you add at the back and remove from the front, like a line of people. Used for task scheduling and breadth-first search.

In Python, use a list as a stack (append / pop) and collections.deque as a queue (append / popleft).

For each number, the partner you need is target minus that number. A dictionary can remember what you have seen.

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, n in enumerate(nums):
        partner = target - n
        if partner in seen:
            return [seen[partner], i]
        seen[n] = i
    return None

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

This is O(n) time and O(n) extra memory. The brute-force nested loop is O(n²); explaining why the dictionary version is faster is what the interviewer is looking for.

The list must be sorted. Compare with the middle item and throw away the half that cannot contain the target.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [3, 8, 15, 23, 42, 57, 91]
print(binary_search(nums, 42))   # 4
print(binary_search(nums, 5))    # -1

Each step halves the search range, so it takes O(log n) time: about 20 steps for a million items, compared with up to a million for a linear search. It only works on sorted data. In Python, the bisect module provides a tested implementation.

A hash function turns a key into a position in an array. What happens when two keys land in the same position?

A hash table stores key-value pairs in an array of "buckets":

1. A hash function turns the key into a number, and that number (modulo the array size) gives the bucket position.
2. To look up a key, the table hashes it again and goes straight to that bucket, so lookups, inserts and deletes take O(1) time on average.
3. When two keys land in the same bucket (a collision), the table either keeps a small list in that bucket (chaining) or probes for the next free slot (open addressing, which Python's dict uses).
4. When the table gets too full, it resizes to a bigger array and re-inserts everything, which keeps collisions rare.

In the worst case (many collisions) operations become O(n), but with a good hash function this is very unlikely. Python's dict and set, and Java's HashMap, are hash tables.

Lists are arrays; dictionaries and sets are hash tables.

Practical consequences: to check membership many times, convert the list to a set first; and for a queue, use collections.deque, which adds and removes at both ends in O(1).

One explores level by level using a queue; the other goes as deep as possible using a stack (or recursion).

Both visit every node of a graph or tree, in a different order:

• Breadth-first search (BFS) visits all neighbours first, then their neighbours, level by level, using a queue. In an unweighted graph it finds the shortest path (fewest edges).
• Depth-first search (DFS) follows one path as deep as it can, then backtracks, using a stack or recursion. It is natural for exploring all possibilities, detecting cycles and topological sorting.

from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}

def bfs(start):
    seen, order, queue = {start}, [], deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

def dfs(node, seen=None):
    seen = seen if seen is not None else []
    seen.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt, seen)
    return seen

print(bfs("A"))   # ['A', 'B', 'C', 'D', 'E']
print(dfs("A"))   # ['A', 'B', 'D', 'C', 'E']

Both take O(V + E) time, where V is the number of nodes and E the number of edges.

Push each opening bracket onto a stack. Each closing bracket must match the most recent opening one.

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack   # leftover openers mean unbalanced

print(is_balanced("{[()]}"))   # True
print(is_balanced("([)]"))     # False
print(is_balanced("(("))       # False

It runs in O(n) time. The stack is the right tool because brackets must close in the reverse order they were opened (last in, first out).

Split the list in half, sort each half recursively, then merge the two sorted halves.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])

    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]

The list is halved about log n times, and each level of merging does O(n) work, so merge sort is O(n log n) in every case. It needs O(n) extra memory and is stable (equal items keep their order). Quicksort is also O(n log n) on average but O(n²) in the worst case; Python's built-in sorted() uses Timsort, a merge-sort hybrid.

Walk through the list once, turning each node's next pointer around. Keep track of the previous node.

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

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next    # remember the rest of the list
        current.next = prev   # turn the pointer around
        prev = current
        current = nxt
    return prev               # the old tail is the new head

def to_list(head):
    values = []
    while head:
        values.append(head.value)
        head = head.next
    return values

head = Node(1, Node(2, Node(3, Node(4))))
print(to_list(reverse(head)))   # [4, 3, 2, 1]

O(n) time and O(1) extra memory. The classic mistake is changing current.next before saving it, which loses the rest of the list.

Think about memory. Which one shares it?

• A process is a running program with its own memory space. Processes are isolated from each other: a crash in one does not corrupt another, but sharing data between them needs explicit communication (pipes, queues, sockets, shared memory), and creating them is relatively expensive.
• A thread runs inside a process and shares the process's memory with the other threads. Threads are cheaper to create and can share data easily, but that shared data must be protected (for example with locks) to avoid race conditions.

In Python, threads suit I/O-bound work, while processes (multiprocessing) are used for CPU-bound work because of the GIL.

Hiding data, hiding complexity, reusing code, and treating different objects the same way.

1. Encapsulation: keep an object's data and the methods that work on it together, and control access to the data (for example, a bank account's balance changes only through deposit and withdraw).
2. Abstraction: expose a simple interface and hide the details. You call account.withdraw(100) without knowing how it is stored.
3. Inheritance: a class can reuse and extend another class. A SavingsAccount is an Account with extra behaviour.
4. Polymorphism: different classes can be used through the same interface. Code that calls shape.area() works for circles, squares and any future shape.

A good follow-up point: prefer composition ("has a") over deep inheritance hierarchies, which become hard to change.

When is the code translated into something the machine can run, before running or while running?

• A compiled language (C, C++, Rust, Go) is translated into machine code before it runs, by a compiler. The result runs fast, and many errors are caught at compile time.
• An interpreted language is executed by another program, the interpreter, while it runs, which makes development quick and the code portable.

The line is blurry in practice. Standard Python (CPython) first compiles source code to bytecode (the .pyc files in __pycache__), and then the Python virtual machine interprets that bytecode. Java and C# compile to bytecode too, but their virtual machines also use just-in-time (JIT) compilation to machine code. So the best answer is: "Python is usually described as interpreted, but it compiles to bytecode first."