Ecclesiastes Software Engineer
Interview Guide

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_list(head):
    """Reverse a singly linked list in place and return the new head."""
    prev, curr = None, head
    while curr:
        nxt = curr.next       # save the rest of the list
        curr.next = prev      # flip this node's pointer
        prev, curr = curr, nxt
    return prev               # old tail is the new head


def from_list(values):
    head = None
    for v in reversed(values):
        head = ListNode(v, head)
    return head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

Scroll sideways to view long lines.

def binary_search(nums, target):
    """Return the index of the first occurrence of target in sorted nums, or -1."""
    lo, hi = 0, len(nums)             # search window is [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2     # overflow-safe midpoint
        if nums[mid] < target:
            lo = mid + 1              # first match must be right of mid
        else:
            hi = mid                  # mid may be the first match
    # lo is the lower bound: first index with nums[lo] >= target
    if lo < len(nums) and nums[lo] == target:
        return lo
    return -1

Scroll sideways to view long lines.

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


class LRUCache:
    """Fixed-capacity cache whose get and put both run in O(1)."""
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.cap = capacity
        self.map = {}                             # key -> Node
        self.head, self.tail = Node(), Node()     # sentinels avoid None checks
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _push_front(self, node):                  # front = most recently used
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key, val):
        node = self.map.get(key)
        if node is not None:                      # existing key: update, no eviction
            node.val = val
            self._unlink(node)
        else:
            if len(self.map) == self.cap:         # full: evict least recently used
                lru = self.tail.prev
                self._unlink(lru)
                del self.map[lru.key]
            node = self.map[key] = Node(key, val)
        self._push_front(node)

Scroll sideways to view long lines.