Solve four algorithm design tasks

Solve the following four algorithmic tasks:

1. Implement wildcard pattern matcher: Given a text s and a pattern p where '?' matches any single character and '*' matches any sequence (including empty), return whether s matches p. Aim for optimal time and space; discuss dynamic programming versus greedy approaches and analyze complexity.

2. Design dynamic pair-sum counter: Initialize with two integer arrays A and B. Support operations add(i, val) that performs B[i] += val, and count(total) that returns the number of pairs (a in A, b in B) such that a + b == total. Handle up to 1e5 updates/queries efficiently; justify your data structures and time/space complexities.

3. Implement LRU cache with O(1) operations: Build a cache with capacity cap supporting get(key) -> value (or -1 if absent) and put(key, value) which inserts/updates and evicts the least-recently used item on overflow. All operations must be O(1). Describe your design choices and complexity.

4. Compute max threats neutralized before breach: You are given arrays dist[i] and speed[i] for i=0..n-1. Starting at t=0, at the start of each integer minute t you may neutralize one threat. A threat reaches the base when t >= dist[i] / speed[i]; if any threat has arrived by time t before you act at that minute, the process ends immediately. Return the maximum number you can neutralize. Clearly state any tie-breaking and provide time complexity.

Wildcard Pattern Matching

Given an input string s and a pattern p, implement wildcard pattern matching where '?' matches any single character and '*' matches any sequence of characters (including the empty sequence). The match must cover the ENTIRE input string (not a partial match).

Return true if s matches the pattern p, otherwise false.

Discuss both the dynamic-programming and the two-pointer greedy approaches and analyze their complexity. The DP table dp[i][j] denotes whether the first i characters of s match the first j characters of p.

Constraints

• 0 <= len(s), len(p) <= 2000
• s contains only lowercase English letters
• p contains lowercase English letters, '?' and '*'
• The match must cover the entire input string

Examples

Example 1

Input: ("aa", "a")
Output: False

Explanation: The single 'a' in the pattern cannot cover the two-character string 'aa'.

Example 2

Input: ("aa", "*")
Output: True

Explanation: '*' matches any sequence, including 'aa'.

Hints

1. Define dp[i][j] = does s[:i] match p[:j]. Base case dp[0][0] = True.
2. A '*' in the pattern can either match no characters (dp[i][j-1]) or extend over one more character of s (dp[i-1][j]).
3. Initialize the first row: a prefix of stars can match the empty string, so dp[0][j] = dp[0][j-1] when p[j-1] == '*'.
4. The greedy alternative tracks the most recent '*' position and the last s-index it matched, so you can backtrack when a literal mismatch occurs.

Dynamic Pair-Sum Counter

Design a data structure initialized with two integer arrays A and B. Process a list of operations and return the results of all count operations in order.

Each operation is a tuple:

• ('add', i, val) performs B[i] += val (mutate the value at index i of B).
• ('count', total) returns the number of pairs (a, b) where a is an element of A (by index) and b is an element of B (by index) such that a + b == total.

Return a list containing one integer per count operation, in the order encountered. Must handle up to 1e5 updates/queries efficiently.

(This is the classic FindSumPairs design: keep a frequency map of B. add updates the map in O(1); count iterates the DISTINCT values of the smaller array A and looks up the complement in B's frequency map.)

Constraints

• 1 <= len(A), len(B) <= 1e5
• Up to 1e5 add/count operations combined
• For add: 0 <= i < len(B), and val keeps B[i] within integer range
• Element and total values fit in a 32-bit signed integer

Examples

Example 1

Input: ([1, 1, 2, 3], [1, 4, 5, 2, 5, 4], [('count', 7), ('add', 3, 2), ('count', 8), ('count', 4)])
Output: [4, 2, 1]

Explanation: count(7): a=2 pairs with the two 5s (2), a=3 pairs with the two 4s (2) -> 4. After add(3,2) B[3] becomes 4 so B has three 4s. count(8): a=3 + each 4 -> 3 pairs? a=3 needs 5 (two 5s)=2; a=2 needs 6=0 -> 2. count(4): a=2 needs 2 (B has one 2)=1.

Example 2

Input: ([1, 2, 3], [1, 2, 3], [('count', 4)])
Output: [3]

Explanation: (1,3),(2,2),(3,1) all sum to 4 -> 3 pairs.

Hints

1. Keep a hash map of value -> frequency for B so each count is a sweep over A's distinct values with O(1) complement lookups.
2. On add(i, val): decrement the count of the OLD B[i], mutate B[i], then increment the count of the NEW value. Never rescan B.
3. Multiply A's value frequency by B's complement frequency to account for duplicate values on both sides.
4. Iterate the array with fewer DISTINCT values (here A) during count to minimize work.

LRU Cache (O(1) get and put)

Design a Least-Recently-Used (LRU) cache with a fixed capacity cap. Process a list of operations and return the results of all get operations in order.

Each operation is a tuple:

• ('get', key) returns the value for key, or -1 if the key is not present. A successful get marks the key as most-recently used.
• ('put', key, value) inserts or updates the value. If inserting a new key would exceed cap, evict the least-recently used key first. A put also marks the key as most-recently used.

Return a list with one integer per get operation, in order. Both get and put must run in O(1).

Design: a hash map (key -> node) combined with a doubly linked list ordering nodes from most- to least-recently used. Python's OrderedDict provides the same O(1) move-to-end / pop-from-front primitives.

Constraints

• 1 <= cap <= 3000
• 0 <= key <= 1e4 (or arbitrary hashable keys)
• 0 <= value <= 1e5
• Up to 2e5 get/put operations
• Every get and put must be O(1)

Examples

Example 1

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])
Output: [1, -1, -1, 3, 4]

Explanation: get(1)=1 (and makes 1 MRU); put(3) evicts LRU key 2; get(2)=-1; put(4) evicts key 1; get(1)=-1; get(3)=3; get(4)=4.

Example 2

Input: (1, [('put', 1, 1), ('get', 1), ('put', 2, 2), ('get', 1), ('get', 2)])
Output: [1, -1, 2]

Explanation: Capacity 1: put(2) evicts key 1, so get(1)=-1 and get(2)=2.

Hints

1. Pair a hash map (key -> node) with a doubly linked list ordered most- to least-recently used.
2. On get/put of an existing key, unlink the node and move it to the most-recently-used end.
3. When a put overflows capacity, evict the node at the least-recently-used end and delete its hash-map entry.
4. A sentinel head and tail node removes all null-edge special cases in the linked list.

Max Threats Neutralized Before Breach

You are given two arrays dist and speed, where dist[i] is the distance of threat i from the base and speed[i] is its speed. Threat i reaches the base at time dist[i] / speed[i] minutes.

Starting at t = 0, at the START of each integer minute t you may neutralize exactly one threat. A threat reaches the base when t >= dist[i] / speed[i]. If any (not-yet-neutralized) threat has already arrived by the current minute t BEFORE you act, the process ends immediately and you neutralize no further threats this minute.

Return the maximum number of threats you can neutralize.

Tie-breaking / strategy: greedily neutralize threats in increasing order of arrival time. Sort arrival times; at minute t (0-indexed), if arrival[t] <= t a breach has occurred and you return t; otherwise you neutralize that threat. If you survive all n minutes, return n.

Constraints

• n == len(dist) == len(speed)
• 1 <= n <= 1e5
• 1 <= dist[i], speed[i] <= 1e5
• Use exact division (compare dist[i] vs t*speed[i] with integers to avoid floating error in production)

Examples

Example 1

Input: ([1, 3, 4], [1, 1, 1])
Output: 3

Explanation: Arrivals [1,3,4]. t=0:1>0 ok; t=1:3>1 ok; t=2:4>2 ok. All three neutralized.

Example 2

Input: ([1, 1, 2, 3], [1, 1, 1, 1])
Output: 1

Explanation: Arrivals [1,1,2,3]. t=0:1>0 ok (neutralize 1); t=1:1<=1 breach -> return 1.

Hints

1. The arrival time of threat i is dist[i] / speed[i]; neutralize threats in increasing order of arrival.
2. After sorting, the threat you handle at minute t (0-indexed) is the t-th earliest arriver.
3. A breach occurs at minute t when arrival[t] <= t (it arrives before or exactly as you would act).
4. If no breach happens through all n minutes, you neutralize every threat -> return n. To avoid float precision, compare dist[i] <= t * speed[i] with integers.