Solve Nearby Inventory and Word Segmentation Tasks
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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?
Overview: Implement two independent tasks: identify stocked centers close enough to a graph destination and return any exact dictionary segmentation of a string. Handle disconnected routes, duplicate edges, missing inventory, repeated suffix work, and large inputs while explaining complexity.
Community answers
Answer by horse_radish_453
def eligible_centers( connections, destination, max_step, inventory):
graph = defaultdict(set)
for a, b in connections:
if a == b:
continue
graph[a].add(b)
graph[b].add(a)
dist = {destination: 0}
queue = deque([destination])
while queue:
node = queue.popleft()
if dist[node] >= max_step:
continue
for neighbor in graph[node]:
if neighbor not in dist:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
result = []
for node, d in dist.items():
if node == destination:
continue
if d > max_step:
continue
if inventory.get(node, 0) > 0:
result.append(node)
return result
Answer by janaki9sravya
PART A:
from collections import deque
def eligible_centers(connections, destination, max_step, inventory) -> list[int]:
n = len(inventory)
adjList ={}
for con in connections:
adjList.setdefault(con[0],[]).append(con[1])
adjList.setdefault(con[1],[]).append(con[0])
q=deque()
q.append((destination,0))
visited=set()
visited.add(destination)
result=[]
while(q):
node,dist = q.popleft()
if dist<=max_step and node!= destination and inventory.get(node,0)>0:
result.append(node)
if dist list[str]:
appendix ={}
dead =set()
for d in dictionary:
appendix.setdefault(d[0],set()).add(d)
def dp(s,l,result):
if l>=len(text):
return True
if l in dead:
return False
if s[l] not in appendix:
dead.add(l)
return False
for d in appendix[s[l]]:
if s[l:l+len(d)]==d:
result.append(d)
if dp(s,l+len(d),result):
return True
else:
result.pop()
dead.add(l)
return False
result =[]
dp(text,0,result)
return result
text = "myhousehavecat"
dictionary = {"my", "house", "have", "cat", "househave"}
result = segment_words(text, dictionary)
print(result)
