Solve two set and graph problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement solutions for the following two data-structure / algorithm problems.
---
## Problem 1: Friend-purchase recommendations
You are given three entity types:
```ts
type Purchase = {
productId: string;
amount: number;
purchaseId: string;
};
type User = {
id: string;
friends: string[]; // list of friend userIds
purchases: Purchase[];
};
type Product = {
productId: string;
productName: string;
};
```
**Input**
- `users`: array of all `User` objects in the system.
- `products`: array of all `Product` objects (mapping `productId -> productName`).
- `targetUserId`: the ID of the current user we want recommendations for.
Each `Purchase` references a `productId`. A user may have multiple purchases of the same product.
**Task**
Write a function that returns the set/list of **product names** such that:
1. At least one **friend** of the target user has purchased the product, **and**
2. The target user **has never purchased** that product.
Formally:
- Let `F` = set of friends of `targetUser`.
- Let `P_friends` = set of productIds purchased by any user in `F`.
- Let `P_user` = set of productIds purchased by `targetUser`.
- Return `productName` for all productIds in `P_friends − P_user`.
Additional details/assumptions:
- You may assume that all `friends` user IDs exist in the `users` array.
- The same product may occur in multiple purchases; treat it as a single product in the output.
- The output order does not matter, or you may define a reasonable ordering (e.g., lexicographically by `productName`).
**Questions**
1. Describe your algorithm in detail.
2. Provide the time and space complexity in terms of `U = number of users`, `F = number of friends of target user`, `T = total number of purchases`, and `P = number of distinct products`.
---
## Problem 2: URL reachability from navigation table
You are given a dataset (or table) of navigation events with schema:
```text
(user_id, source_url, destination_url)
```
Each record means that a user visited `destination_url` immediately after `source_url`. We treat each `(source_url, destination_url)` pair as a **directed edge** in a graph whose nodes are URLs.
**Input**
- A collection of navigation records as described above.
- Two URLs: `url1` and `url2`.
**Task**
Determine whether it is possible to **navigate from `url1` to `url2`** by following one or more edges implied by the table (i.e., whether `url2` is reachable from `url1` in the directed URL graph).
You should:
1. Describe how you would build an in-memory representation of the graph from the set of navigation records.
2. Implement a function, e.g., `boolean canReach(String url1, String url2)`, that returns `true` if there is a path from `url1` to `url2`, and `false` otherwise.
3. Analyze the time and space complexity in terms of `V = number of distinct URLs` and `E = number of edges (distinct source→destination pairs)`.
You may assume that the full set of records fits in memory for the purpose of this problem.
Quick Answer: This question evaluates proficiency in data-structure manipulation (set operations, mapping and deduplication), directed-graph modeling and traversal for reachability, and algorithmic time/space complexity analysis.
