Elevi Associates Software Engineer
Interview Guide

class ListNode:
    def __init__(self, val, 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 = None
    curr = head
    while curr:
        nxt = curr.next      # save the rest before cutting the link
        curr.next = prev     # point this node backward
        prev, curr = curr, nxt
    return prev              # the 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 merge_sort(items, key=lambda x: x):
    """Return a new list with items sorted ascending by key; stable."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    left = merge_sort(items[:mid], key)
    right = merge_sort(items[mid:], key)
    return _merge(left, right, key)


def _merge(left, right, key):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        # <= takes from the left on ties, keeping equal items in input order
        if key(left[i]) <= key(right[j]):
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])   # at most one of these two is non-empty
    merged.extend(right[j:])
    return merged

Scroll sideways to view long lines.

def two_sum(nums, target):
    """Return [i, j] with i < j and nums[i] + nums[j] == target, else None."""
    seen = {}  # value -> index of an earlier element
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:          # look up before inserting x
            return [seen[need], i]
        seen[x] = i
    return None

Scroll sideways to view long lines.

def longest_unique_substring(s):
    """Return the first longest substring of s with no repeated characters."""
    last = {}              # char -> index where it was last seen
    left = 0               # start of the current duplicate-free window
    best_start, best_len = 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1    # jump just past the earlier copy
        last[ch] = right
        if right - left + 1 > best_len:
            best_start, best_len = left, right - left + 1
    return s[best_start:best_start + best_len]

Scroll sideways to view long lines.