Solve Dependency, Prefix, and Cache Problems

Solve the following three coding problems.

Problem 1: Determine Whether All Tasks Can Be Completed

You are given numTasks, the number of tasks labeled from 0 to numTasks - 1, and a list of prerequisite pairs prerequisites. Each pair [a, b] means task b must be completed before task a.

Return true if it is possible to complete all tasks. Return false if the prerequisite graph contains a cycle.

Example:

numTasks = 2
prerequisites = [[1, 0]]
Output: true

numTasks = 2
prerequisites = [[1, 0], [0, 1]]
Output: false

Problem 2: Implement a Prefix-Based Word Store

Design a data structure that supports the following operations:

• insert(word): Add a lowercase English word.
• search(word): Return whether the exact word exists.
• startsWith(prefix): Return whether any inserted word starts with the given prefix.

All inputs contain only lowercase English letters a through z.

Example:

insert("apple")
search("apple")    -> true
search("app")      -> false
startsWith("app")  -> true
insert("app")
search("app")      -> true

Problem 3: Implement a Fixed-Capacity Least-Recently-Used Cache

Design a cache with positive integer capacity that supports:

• get(key): Return the value associated with key if it exists; otherwise return -1. Accessing a key makes it the most recently used item.
• put(key, value): Insert or update the value for key. If the cache exceeds capacity, evict the least recently used item.

Both operations should run in average O(1) time.

Example:

capacity = 2
put(1, 1)
put(2, 2)
get(1)     -> 1
put(3, 3)  // evicts key 2
get(2)     -> -1
put(4, 4)  // evicts key 1
get(1)     -> -1
get(3)     -> 3
get(4)     -> 4

Part 1: Determine Whether All Tasks Can Be Completed

Given an integer numTasks and a list of prerequisite pairs prerequisites, where each pair [a, b] means task b must be completed before task a, determine whether it is possible to finish every task. Return True if the prerequisite graph contains no cycle; otherwise return False.

Constraints

• 0 <= numTasks <= 100000
• 0 <= len(prerequisites) <= 200000
• Each prerequisite is a pair [a, b] with 0 <= a, b < numTasks

Examples

Example 1

Input: (2, [[1, 0]])
Output: True

Explanation: Task 0 can be done first, then task 1. There is no cycle.

Example 2

Input: (2, [[1, 0], [0, 1]])
Output: False

Explanation: Task 0 depends on task 1 and task 1 depends on task 0, forming a cycle.

Hints

1. Model the tasks as a directed graph and look for a way to detect cycles.
2. If you repeatedly remove tasks with indegree 0 and cannot process all tasks, a cycle must exist.

Part 2: Implement a Prefix-Based Word Store

Implement a prefix-based word store using a function interface. The function receives a list of operations. Each operation is a tuple (op, text), where op is one of 'insert', 'search', or 'startsWith'. For each 'insert', append None to the output list. For each 'search' or 'startsWith', append the boolean result. Return the full result list in operation order.

Constraints

• 0 <= len(operations) <= 20000
• Each word or prefix has length between 1 and 2000
• The sum of lengths of all words and prefixes is at most 200000
• All characters are lowercase English letters a through z

Examples

Example 1

Input: [('insert', 'apple'), ('search', 'apple'), ('search', 'app'), ('startsWith', 'app'), ('insert', 'app'), ('search', 'app')]
Output: [None, True, False, True, None, True]

Explanation: 'apple' is inserted first. Exact search for 'apple' is True, exact search for 'app' is False until 'app' is inserted, while startsWith('app') is already True because 'apple' starts with it.

Example 2

Input: [('search', 'dog'), ('startsWith', 'do')]
Output: [False, False]

Explanation: No words have been inserted yet, so both the exact search and prefix check return False.

Hints

1. A trie stores one character per level and is a natural fit for both exact word checks and prefix checks.
2. Exact search and prefix search traverse similarly; only exact search must verify an end-of-word marker.

Part 3: Implement a Fixed-Capacity Least-Recently-Used Cache

Simulate an LRU cache using a function interface. The function receives a positive integer capacity and a list of operations. Each operation is either ('put', key, value) or ('get', key). Return a list aligned with the operations: append None for each put, and append the returned integer for each get. Accessing or updating a key makes it the most recently used item. When the cache exceeds capacity, evict the least recently used key.

Constraints

• 1 <= capacity <= 30000
• 0 <= len(operations) <= 200000
• 0 <= key <= 1000000000
• 0 <= value <= 1000000000

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: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: After getting key 1, it becomes most recently used. Putting 3 evicts 2. Putting 4 later evicts 1.

Example 2

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

Explanation: With capacity 1, each new key evicts the previous one. Key 2 is gone after putting 3, and key 3 is gone after putting 4.

Hints

1. Use a hash map for O(1) access to cache entries and a doubly linked list to track recency order.
2. Move a key to the front whenever it is read or updated, and remove from the tail when eviction is needed.