Jane Street Leetcode Study Guide

def countWords(words1: list[str], words2: list[str]) -> int:
    from collections import Counter

    count1 = Counter(words1)
    count2 = Counter(words2)

    return sum(1 for word in count1 if count1[word] == 1 and count2.get(word, 0) == 1)

# Complexity Analysis
# - Time Complexity: O(n + m), where n and m are the lengths of words1 and words2.
# - Space Complexity: O(n + m), for storing counts.

def robotSim(commands, obstacles):
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]  # North, East, South, West
    x = y = direction = 0
    obstacle_set = set(map(tuple, obstacles))
    max_distance = 0

    for command in commands:
        if command == -2:  # turn left
            direction = (direction - 1) % 4
        elif command == -1:  # turn right
            direction = (direction + 1) % 4
        else:
            for _ in range(command):
                if (x + dx[direction], y + dy[direction]) not in obstacle_set:
                    x += dx[direction]
                    y += dy[direction]
                    max_distance = max(max_distance, x * x + y * y)

    return max_distance

# Complexity Analysis
# - Time Complexity: O(n+k), where n is the number of commands and k the number of obstacles.
# - Space Complexity: O(k), space for obstacles.

from collections import defaultdict

class StreamChecker:
    def __init__(self, words: list[str]):
        self.trie = {}
        self.stream = []
        for word in words:
            node = self.trie
            for char in reversed(word):
                if char not in node:
                    node[char] = {}
                node = node[char]
            node['#'] = True

    def query(self, letter: str) -> bool:
        self.stream.append(letter)
        node = self.trie
        for char in reversed(self.stream):
            if char in node:
                node = node[char]
                if '#' in node:
                    return True
            else:
                break
        return False

# Complexity Analysis
# - Time Complexity: O(q * l), where q is the number of queries and l average length of words.
# - Space Complexity: O(t), where t is the total length of all words for trie building.

def add(num1: int, num2: int) -> int:
    return num1 + num2

# Complexity Analysis
# - Time Complexity: O(1), constant time operation.
# - Space Complexity: O(1), no extra space.

def longestCommonPrefix(strs: list[str]) -> str:
    if not strs:
        return ""

    prefix = strs[0]
    for s in strs:
        while s[:len(prefix)] != prefix:
            prefix = prefix[:-1]
            if not prefix:
                return ""

    return prefix

# Complexity Analysis
# - Time Complexity: O(n * m), where n is the number of strings and m is the length of the shortest string.
# - Space Complexity: O(1), constant space used for comparisons.

from collections import defaultdict
import collections

def calcEquation(equations, values, queries):
    graph = defaultdict(dict)

    # Build the graph
    for (dividend, divisor), value in zip(equations, values):
        graph[dividend][divisor] = value
        graph[divisor][dividend] = 1 / value

    def bfs(src, dst):
        if src not in graph or dst not in graph:
            return -1.0
        queue = collections.deque([(src, 1.0)])
        visited = set([src])
        while queue:
            current_node, current_product = queue.popleft()
            if current_node == dst:
                return current_product
            for neighbor, value in graph[current_node].items():
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, current_product * value))
        return -1.0

    results = []
    for dividend, divisor in queries:
        results.append(bfs(dividend, divisor))
    return results

# Complexity Analysis
# - Time Complexity: O(N * Q), where N is the number of equations and Q is the number of queries.
# - Space Complexity: O(N), for storing the graph.

def addStrings(num1: str, num2: str) -> str:
    i, j = len(num1) - 1, len(num2) - 1
    carry, result = 0, []
    
    while i >= 0 or j >= 0 or carry:
        n1 = int(num1[i]) if i >= 0 else 0
        n2 = int(num2[j]) if j >= 0 else 0
        carry, digit = divmod(n1 + n2 + carry, 10)
        result.append(str(digit))
        i, j = i - 1, j - 1
    
    return ''.join(reversed(result))

# Complexity Analysis
# - Time Complexity: O(max(n, m)), where n and m are the lengths of the strings.
# - Space Complexity: O(max(n, m)), for storing the result.

def judgePoint24(cards):
    if len(cards) == 1:
        return abs(cards[0] - 24) < 1e-6
    
    for i in range(len(cards)):
        for j in range(len(cards)):
            if i != j:
                next_cards = [cards[k] for k in range(len(cards)) if k != i and k != j]
                for op in ('+', '-', '*', '/'):
                    if op in ('+', '*') and j > i:
                        continue
                    if op == '+':
                        next_cards.append(cards[i] + cards[j])
                    elif op == '-':
                        next_cards.append(cards[i] - cards[j])
                    elif op == '*':
                        next_cards.append(cards[i] * cards[j])
                    elif op == '/' and cards[j]:
                        next_cards.append(cards[i] / cards[j])
                    
                    if judgePoint24(next_cards):
                        return True
                    next_cards.pop()
                    
    return False

# Complexity Analysis
# - Time Complexity: factorial time complexity due to permutations and operations, around O(N!)
# - Space Complexity: O(N), where N is the depth of recursion tree (inherently bound by constants here)