Solve four algorithm design tasks
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.
TikTok
Aug 13, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
Solve the following four algorithmic tasks:
- 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.
- 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.
- Implement LRU cache with O(
- 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.
- 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.