Medium Difficulty Coding Problems Questions

from functools import lru_cache

def is_match(s: str, p: str) -> bool:
    """
    Returns True if string s matches pattern p where:
    - '.' matches any single character
    - '*' matches zero or more of the preceding element
    Uses top-down DP with memoization.
    """
    @lru_cache(None)
    def match(i: int, j: int) -> bool:
        # If we've reached the end of pattern, string must also be finished
        if j == len(p):
            return i == len(s)

        # Check if current positions match (i within s and char matches or pattern has '.')
        first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')

        # Handle '*' as the next character in pattern
        if j + 1 < len(p) and p[j + 1] == '*':
            # Two options:
            # 1) Treat '*' as zero occurrences: skip p[j:j+2]
            # 2) If first_match, consume one char from s and keep pattern at j (use '*' again)
            return match(i, j + 2) or (first_match and match(i + 1, j))
        else:
            # No '*', must consume one char from both
            return first_match and match(i + 1, j + 1)

    return match(0, 0)

from bisect import bisect_left

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.freq = 0
        self.top_k = []  # list of (freq, sentence), sorted descending freq, then lex

class Autocomplete:
    def __init__(self, k=3):
        self.root = TrieNode()
        self.k = k
        self.freq_map = {}  # maps sentence -> freq

    def _insert_topk(self, node, sentence, freq):
        entry = (-freq, sentence)  # negative freq for ascending sort via bisect
        lst = node.top_k
        # remove old if present
        for i, e in enumerate(lst):
            if e[1] == sentence:
                lst.pop(i)
                break
        # insert keeping ascending by (-freq, sentence)
        idx = bisect_left(lst, entry)
        lst.insert(idx, entry)
        if len(lst) > self.k:
            lst.pop()  # remove worst

    def insert(self, sentence, count=1):
        new_freq = self.freq_map.get(sentence, 0) + count
        self.freq_map[sentence] = new_freq

        node = self.root
        self._insert_topk(node, sentence, new_freq)
        for ch in sentence:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            self._insert_topk(node, sentence, new_freq)
        node.is_end = True
        node.freq = new_freq

    def query(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        # convert back to (sentence, freq) sorted by freq desc
        return [(s, -f) for f, s in node.top_k]

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

def delete_duplicates(head: ListNode) -> ListNode:
    """
    Remove duplicates from sorted singly-linked list in-place.
    Returns head of modified list.
    """
    cur = head
    while cur and cur.next:
        if cur.val == cur.next.val:
            # skip the duplicate node
            cur.next = cur.next.next
        else:
            # move forward when next is different
            cur = cur.next
    return head

def length_of_longest_substring(s: str) -> int:
    """
    O(n) time, O(min(n, alphabet_size)) extra space.
    Returns length of longest substring without repeating characters.
    """
    last_index = {}  # char -> last seen index
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        if ch in last_index and last_index[ch] >= left:
            # Move left just past the previous occurrence
            left = last_index[ch] + 1
        last_index[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len

def trap(height):
    """
    Compute trapped rain water using two-pointer O(n) time, O(1) extra space.
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    trapped = 0

    while left <= right:
        if height[left] <= height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                trapped += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                trapped += right_max - height[right]
            right -= 1

    return trapped