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.