Arrays, Strings, and Collections Fundamentals Questions

def subarray_sum(nums, k):
    """
    Count continuous subarrays whose sum equals k in O(n) time.
    """
    from collections import defaultdict
    count = defaultdict(int)
    count[0] = 1  # empty prefix
    res = 0
    curr = 0

    for x in nums:
        curr += x
        # if there was a prefix with sum curr - k, removing it gives subarray sum k
        res += count.get(curr - k, 0)
        count[curr] += 1

    return res

def remove_vowels(s: str) -> str:
    """
    Remove English vowels (a, e, i, o, u) from the input string.
    This version treats vowels case-insensitively; adjust if only lowercase is required.
    """
    vowels = set("aeiouAEIOU")  # O(1) membership tests
    # Use list comprehension + join for efficient concatenation
    return "".join(ch for ch in s if ch not in vowels)

# Example
print(remove_vowels("leetcode"))  # -> "ltcd"

def length_of_lis(nums):
    """
    Return length of longest increasing subsequence in O(n log n).
    """
    if not nums:
        return 0

    tails = []  # tails[i] = smallest tail of an increasing subseq of length i+1

    for x in nums:
        # binary search for leftmost index in tails where tails[idx] >= x
        l, r = 0, len(tails) - 1
        pos = len(tails)  # default append position
        while l <= r:
            m = l + (r - l) // 2
            if tails[m] >= x:
                pos = m
                r = m - 1
            else:
                l = m + 1

        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x

    return len(tails)

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

def detect_cycle_entry(head):
    # Floyd's cycle detection. Returns entry node or None.
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # find entry
            ptr = head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None

def intersection_no_cycle(h1, h2):
    # Align by length then walk together
    def length(head):
        n = 0
        while head:
            n += 1
            head = head.next
        return n
    l1, l2 = length(h1), length(h2)
    # advance longer
    while l1 > l2:
        h1 = h1.next; l1 -= 1
    while l2 > l1:
        h2 = h2.next; l2 -= 1
    while h1 and h2:
        if h1 is h2:
            return h1
        h1 = h1.next; h2 = h2.next
    return None

def get_intersection(headA, headB):
    e1 = detect_cycle_entry(headA)
    e2 = detect_cycle_entry(headB)

    if not e1 and not e2:
        return intersection_no_cycle(headA, headB)

    if (e1 and not e2) or (e2 and not e1):
        # one cyclic, one acyclic -> cannot intersect by reference
        return None

    # both have cycles
    if e1 is e2:
        # shared entry: intersection might be before entry or at/after entry.
        # Temporarily treat entry as end to find possible earlier intersection.
        # Compute lengths up to entry
        def dist_to_entry(head, entry):
            d = 0
            while head is not entry:
                d += 1
                head = head.next
            return d
        d1 = dist_to_entry(headA, e1)
        d2 = dist_to_entry(headB, e1)
        # align and scan until either meet or reach entry
        pa, pb = headA, headB
        while d1 > d2:
            pa = pa.next; d1 -= 1
        while d2 > d1:
            pb = pb.next; d2 -= 1
        while pa is not pb and pa is not e1 and pb is not e1:
            pa = pa.next; pb = pb.next
        return pa if pa is pb else e1  # if none before entry, entry is intersection
    else:
        # Different entry nodes: cycles may still be connected if entries are in same cycle
        # Walk one cycle starting at e1 to see if we can reach e2
        p = e1.next
        while p is not e1:
            if p is e2:
                return e1  # cycles intersect; any node in shared cycle is acceptable (return e1 or e2)
            p = p.next
        return None  # disjoint cycles