Solve two set and graph problems

Implement solutions for the following two data-structure / algorithm problems.

Problem 1: Friend-purchase recommendations

You are given three entity types:

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:

(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.