Solve Array, Matrix, and Recommendation Problems

During an onsite coding interview, solve the following independent tasks.

Problem 1: In-place unique prefix

You are given a nondecreasing integer array nums. Modify the array in place so that each distinct value appears exactly once in the prefix of the array, preserving the original relative order of the distinct values. Return the length of that prefix. You may ignore the contents of the array after the returned length.

Constraints: use O(1) extra space and run in O(n) time.

Follow-ups:

• How would you change the algorithm if each value were allowed to appear at most k times?
• What edge cases should be tested?

Problem 2: Longest increasing path in a grid

You are given an m x n matrix of integers. From a cell, you may move one step up, down, left, or right. You may only move to a neighboring cell with a strictly larger value. Return the length of the longest valid path.

Constraints: design a solution that avoids exponential search and works efficiently for large grids.

Follow-ups:

• How can you reconstruct one actual longest path, not just its length?
• How do you avoid recursion-depth issues on very large matrices?

Problem 3: Random friend recommender

You are given an undirected social graph where each node is a user and each edge means the two users are friends.

Implement the following functions:

1. getCandidates(userId): return all users who are friends-of-friends of userId, excluding userId and excluding direct friends. If a candidate is reachable through multiple mutual friends, it should still appear only once.
2. recommendRandom(userId): return one uniformly random candidate from getCandidates. If no candidate exists, return null.
3. recommendTopK(userId, k): rank candidates by a simple score equal to the number of mutual friends with userId; break ties deterministically, such as by smaller user ID. Return the top k candidates.
4. Discuss how the score could be extended in a production system using additional signals such as recent interactions, shared groups, blocked users, privacy settings, and freshness.

Part 1: In-place Unique Prefix

You are given a nondecreasing integer array nums. Modify nums in place so that each distinct value appears exactly once at the start of the array, preserving the original order of the distinct values. Return the length of this unique prefix. The values after the returned length do not matter.

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in nondecreasing order
• Use O(1) extra space and O(n) time

Examples

Example 1

Input: [1,1,2]
Output: 2

Explanation: The unique prefix becomes [1, 2], so the returned length is 2.

Example 2

Input: []
Output: 0

Explanation: An empty array has no distinct values.

Hints

1. Keep a write pointer for the next position where a new distinct value should go.
2. Because the array is sorted, you only need to compare the current value with the last value written into the prefix.

Part 2: Longest Increasing Path in a Grid

Given an m x n integer matrix, you may move from a cell to one of its four neighbors if and only if the neighbor has a strictly larger value. Return the length of the longest valid path. Your solution should avoid exponential search and work efficiently on large grids.

Constraints

• 0 <= m, n <= 200
• The matrix is rectangular
• You may move only up, down, left, or right
• A valid move must go to a strictly larger value

Examples

Example 1

Input: ([[9,9,4],[6,6,8],[2,1,1]],)
Output: 4

Explanation: One longest path is 1 -> 2 -> 6 -> 9, so the answer is 4.

Example 2

Input: ([[3,4,5],[3,2,6],[2,2,1]],)
Output: 4

Explanation: A longest path is 3 -> 4 -> 5 -> 6, which has length 4.

Hints

1. Think of the grid as a directed acyclic graph: draw an edge from a cell to each neighboring cell with a larger value.
2. Instead of DFS recursion, you can process the DAG level by level using indegrees starting from local minima.

Part 3: Friend Recommendation Summary

You are given an undirected social graph as an adjacency list. For a target user, compute all unique friends-of-friends excluding the user and excluding direct friends. Also produce one reproducible random recommendation and the top k candidates ranked by the number of mutual friends; ties are broken by smaller user ID. To make the random choice testable, use the supplied seed with this rule: sort the candidates ascending, then repeatedly update state = (1664525 * state + 1013904223) mod 2^32 until state is below the largest multiple of len(candidates) less than 2^32; choose index state % len(candidates). If there are no candidates, return None for the random recommendation. In a production system, the score could later be extended with recency, shared groups, blocking/privacy rules, and freshness, but this task uses only mutual-friend counts.

Constraints

• 0 <= number of users <= 10^5
• 0 <= total friendship entries <= 2 * 10^5
• 0 <= k <= 10^5
• 0 <= seed < 2^32
• Treat the graph as undirected; duplicate friend IDs should not create duplicate candidates

Examples

Example 1

Input: ({1: [2, 3], 2: [1, 4, 5], 3: [1, 4], 4: [2, 3], 5: [2]}, 1, 5, 1)
Output: {'candidates': [4, 5], 'random_recommendation': 4, 'top_k': [4, 5]}

Explanation: User 1 has direct friends 2 and 3. Friends-of-friends are 4 and 5. Candidate 4 has 2 mutual friends, and 5 has 1. With seed 1, the deterministic random pick is 4.

Example 2

Input: ({1: [2], 2: [1]}, 1, 3, 7)
Output: {'candidates': [], 'random_recommendation': None, 'top_k': []}

Explanation: User 1's only friend is 2, and 2 connects only back to 1. There are no valid friends-of-friends.

Hints

1. Use sets so you can quickly exclude the target user and all direct friends.
2. While scanning each direct friend's neighbors, count how many times each candidate appears; that count is the mutual-friend score.