PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

This question evaluates algorithmic skills across array manipulation, grid pathfinding, and graph-based recommendation systems, testing competencies in in-place transformations, efficient traversal/search, and candidate ranking under constraints.

  • medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Solve Array, Matrix, and Recommendation Problems

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: This question evaluates algorithmic skills across array manipulation, grid pathfinding, and graph-based recommendation systems, testing competencies in in-place transformations, efficient traversal/search, and candidate ranking under constraints.

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

Input: [1,1,2]

Expected Output: 2

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

Input: []

Expected Output: 0

Explanation: An empty array has no distinct values.

Input: [0,0,1,1,1,2,2,3,3,4]

Expected Output: 5

Explanation: The unique prefix becomes [0, 1, 2, 3, 4], which has length 5.

Input: [-3,-3,-1,0,0,0,5]

Expected Output: 4

Explanation: The unique prefix becomes [-3, -1, 0, 5], so the answer is 4.

Input: [7]

Expected Output: 1

Explanation: A single-element array already has one unique value.

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

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

Expected Output: 4

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

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

Expected Output: 4

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

Input: ([],)

Expected Output: 0

Explanation: An empty grid has no valid path.

Input: ([[42]],)

Expected Output: 1

Explanation: A single cell is a path of length 1.

Input: ([[7,7],[7,7]],)

Expected Output: 1

Explanation: No move is allowed because neighboring values are not strictly larger.

Input: ([[-3,-2,-1],[-4,-5,0]],)

Expected Output: 6

Explanation: A longest path is -5 -> -4 -> -3 -> -2 -> -1 -> 0, which visits 6 cells.

Input: ([[1,2],[4,3]],)

Expected Output: 4

Explanation: A longest path is 1 -> 2 -> 3 -> 4, moving only through adjacent cells.

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

Input: ({1: [2, 3], 2: [1, 4, 5], 3: [1, 4], 4: [2, 3], 5: [2]}, 1, 5, 1)

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

Input: ({1: [2], 2: [1]}, 1, 3, 7)

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

Input: ({1: [2, 2, 3], 2: [1, 1, 4, 4], 3: [1, 4], 4: [2, 3]}, 1, 2, 99)

Expected Output: {'candidates': [4], 'random_recommendation': 4, 'top_k': [4]}

Explanation: Duplicate adjacency entries are ignored. User 4 is the only unique candidate and has 2 mutual friends.

Input: ({1: [2, 3], 2: [1, 4, 5], 3: [1, 4, 5], 4: [2, 3], 5: [2, 3]}, 1, 1, 0)

Expected Output: {'candidates': [4, 5], 'random_recommendation': 5, 'top_k': [4]}

Explanation: Both 4 and 5 have 2 mutual friends with user 1, so the tie is broken by smaller user ID and top_k is [4]. The deterministic random choice with seed 0 selects 5.

Input: ({1: [2, 3], 2: [1, 4, 5], 3: [1, 4], 4: [2, 3], 5: [2]}, 1, 0, 1)

Expected Output: {'candidates': [4, 5], 'random_recommendation': 4, 'top_k': []}

Explanation: The candidate set is still [4, 5], but k is 0 so no ranked results are returned.

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.
Last updated: May 15, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve Two Backtracking Array Problems - Meta (hard)
  • Find a String Containing Another - Meta (medium)
  • Solve Subarray Sum and Local Minimum - Meta (hard)
  • Validate abbreviations and brackets - Meta (medium)
  • Solve Two String Problems - Meta (medium)