Opera Solutions 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 before breaking the link
        curr.next = prev     # flip this node's pointer backward
        prev, curr = curr, nxt
    return prev              # prev is the old tail, now the 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 longest_unique_substring(s):
    """Return (length, substring) of the longest run with no repeated character."""
    last_seen = {}                 # char -> most recent index
    left = best_len = best_start = 0
    for right, ch in enumerate(s):
        # Jump only if the earlier occurrence is inside the current window.
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        if right - left + 1 > best_len:
            best_len, best_start = right - left + 1, left
    return best_len, s[best_start:best_start + best_len]

Scroll sideways to view long lines.

def binary_search(a, target):
    """Return an index of target in sorted list a, or -1 if absent."""
    lo, hi = 0, len(a) - 1          # inclusive bounds
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def lower_bound(a, target):
    """Return the first index i with a[i] >= target (len(a) if none)."""
    lo, hi = 0, len(a)              # half-open range [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Scroll sideways to view long lines.

def knapsack(weights, values, capacity):
    """0/1 knapsack: return (best_value, sorted indices of chosen items)."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                 # skip item i-1
            if wt <= w:                              # or take it
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)
    chosen, w = [], capacity                         # walk back through the table
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            chosen.append(i - 1)
            w -= weights[i - 1]
    return dp[n][capacity], chosen[::-1]


def knapsack_value(weights, values, capacity):
    """Same answer in O(W) memory (value only)."""
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):       # downward: each item used once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

Scroll sideways to view long lines.