Stifel Financial Software Engineer
Interview Guide

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


class LinkedList:
    def __init__(self, values=()):
        self.head = None
        self.tail = None
        self.size = 0
        for v in values:
            self.append(v)

    def append(self, val):
        """O(1) thanks to the tail pointer."""
        node = Node(val)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

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

    def reverse(self):
        """Reverse in place: O(n) time, O(1) extra space."""
        prev, curr = None, self.head
        self.tail = self.head          # the old head becomes the tail
        while curr:
            nxt = curr.next            # save the rest before rewiring
            curr.next = prev
            prev, curr = curr, nxt
        self.head = prev

Scroll sideways to view long lines.

def find_duplicates(nums):
    """Each value that appears more than once, reported once, in the
    order its first repeat is seen. O(n) expected time, O(n) space."""
    seen, reported, dupes = set(), set(), []
    for x in nums:
        if x not in seen:
            seen.add(x)
        elif x not in reported:
            reported.add(x)
            dupes.append(x)
    return dupes


def find_duplicates_bounded(nums):
    """Only when every value lies in 1..len(nums). O(n) time, O(1)
    extra space: tallies counts inside the array, then restores it."""
    n = len(nums)
    for x in nums:
        orig = (x - 1) % n + 1          # value even if its slot was bumped
        nums[orig - 1] += n
    dupes = [i + 1 for i in range(n) if (nums[i] - 1) // n >= 2]
    for i in range(n):
        nums[i] = (nums[i] - 1) % n + 1  # undo the tallies
    return dupes

Scroll sideways to view long lines.

def flatten(nested):
    """Recursively flatten arbitrarily nested lists/tuples.
    O(total elements) time; O(depth) call-stack space."""
    out = []

    def walk(item):
        if isinstance(item, (list, tuple)):
            for child in item:      # recursive case: a smaller piece
                walk(child)
        else:
            out.append(item)        # base case: a leaf value

    walk(nested)
    return out


def flatten_iterative(nested):
    """Same result with an explicit stack of iterators: no recursion
    limit, but we now hand-manage what the call stack did for free."""
    out, stack = [], [iter([nested])]
    while stack:
        for item in stack[-1]:
            if isinstance(item, (list, tuple)):
                stack.append(iter(item))
                break
            out.append(item)
        else:
            stack.pop()
    return out

Scroll sideways to view long lines.