Quick Overview

This multi-part question evaluates algorithm design and data-structure competencies including wildcard string pattern matching and trade-offs between dynamic programming and greedy strategies, dynamic pair-sum maintenance under frequent updates, O(1) LRU cache design, and scheduling/ordering for time-constrained threat neutralization.

Solve four algorithm design tasks

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

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.

Quick Answer: This multi-part question evaluates algorithm design and data-structure competencies including wildcard string pattern matching and trade-offs between dynamic programming and greedy strategies, dynamic pair-sum maintenance under frequent updates, O(1) LRU cache design, and scheduling/ordering for time-constrained threat neutralization.

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

Input: ("aa", "a")

Expected Output: False

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

Input: ("aa", "*")

Expected 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

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

Expected 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.

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

Expected 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

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

Expected 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.

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

Expected 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

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

Expected 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.

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

Expected 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.

Loading coding console...