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