## Two Algorithmic Tasks Implement both parts. They are independent and should have separate functions. ### Part A - Nearby Centers with Inventory An undirected graph represents delivery routes between centers. Given `connections`, a `destination`, a nonnegative `max_step`, and an `inventory` map, return every center that can send inventory to the destination. Implement: ```text eligible_centers(connections, destination, max_step, inventory) -> list[int] ``` A center is eligible when all of the following hold: - It is not the destination. - Its inventory value is greater than zero. - Its shortest-path distance to the destination is at most `max_step`. The result may be returned in any order. Centers may appear in `inventory` even if they have no route, and routes may mention centers absent from `inventory`; a missing inventory value means zero. Example: ```text connections = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]] destination = 4 max_step = 1 inventory = {1: 2, 2: 0, 3: 5, 4: 3, 5: 6} result = [3, 5] ``` Constraints: - `0 <= len(connections) <= 100000` - Center IDs are integers. - Duplicate edges and self-loops may appear and must not change the result. Hints: - Search outward from the destination rather than running a search from every stocked center. - Once the search reaches `max_step`, deeper nodes are irrelevant. ### Part B - Return One Word Segmentation Given a lowercase string and a dictionary, return any sequence of dictionary words whose concatenation is exactly the string. Implement: ```text segment_words(text, dictionary) -> list[str] ``` You may treat membership in `dictionary` as the reported `isWord` helper. At least one valid segmentation is guaranteed. Do not reorder or omit characters. Example: ```text text = "myhousehavecat" dictionary = {"my", "house", "have", "cat", "househave"} result = ["my", "house", "have", "cat"] ``` Returning `["my", "househave", "cat"]` is also valid. Constraints: - `1 <= len(text) <= 2000` - Every dictionary word is nonempty and lowercase. - The dictionary contains at most 20000 words. Hints: - Backtrack from a character index and try valid next words. - Cache indices that cannot lead to a complete segmentation so repeated suffixes are not recomputed. - Bounding candidate lengths by the longest dictionary word can reduce unnecessary checks. ### Discussion Extensions - Give the time and space complexity of each part. - How would Part B change if all valid segmentations were required? - How would you make Part A answer many destination queries on a mostly static graph?