Shape Security Software Engineer
Interview Guide

def reverse_string(s: str) -> str:
    """Return s reversed, using two pointers on a mutable copy."""
    chars = list(s)  # Python strings are immutable, so work on a list
    left, right = 0, len(chars) - 1
    while left < right:
        # Swap the outermost unswapped pair, then move both pointers inward.
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)  # one O(n) join, not repeated concatenation

Scroll sideways to view long lines.

def binary_search(nums: list, target: int) -> int:
    """Return an index of target in sorted nums, or -1 if absent."""
    lo, hi = 0, len(nums) - 1          # closed interval [lo, hi]
    while lo <= hi:
        mid = lo + (hi - lo) // 2      # overflow-safe form for fixed-width ints
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1               # target can only be right of mid
        else:
            hi = mid - 1               # target can only be left of mid
    return -1


def lower_bound(nums: list, target: int) -> int:
    """Return the first index i with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)              # half-open interval [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2      # same overflow-safe form
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid                   # mid may be the answer; keep it
    return lo

Scroll sideways to view long lines.

def two_sum(nums, target):
    """Return indices [i, j] with i < j and nums[i] + nums[j] == target, else None."""
    seen = {}  # value -> index where it was seen
    for j, x in enumerate(nums):
        complement = target - x
        if complement in seen:        # look up before inserting: no self-pairing
            return [seen[complement], j]
        seen[x] = j
    return None

Scroll sideways to view long lines.

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


def has_cycle(head):
    """Floyd's tortoise and hare: O(n) time, O(1) extra space."""
    slow = fast = head
    while fast and fast.next:          # fast reaching None means no cycle
        slow = slow.next
        fast = fast.next.next
        if slow is fast:               # compare identity, not values
            return True
    return False


def cycle_start(head):
    """Return the node where the cycle begins, or None if the list ends."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # head->entry distance equals meeting point->entry distance
            # modulo the cycle length, so step both one node at a time.
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p
    return None

Scroll sideways to view long lines.