PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates competencies in bipartite matching and combinatorial optimization, along with practical data-structure design for scalable tag-based assignment and priority-aware selection.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Match people to questions using tags and priorities

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are building a simplified “Q&A matching” feature. You have: - `people`: `N` people, where person `i` has a set of expertise tags `P[i]`. - `questions`: `M` questions, where question `j` has a set of tags `Q[j]` and an integer priority `prio[j]` (larger means more important). A person `i` can be assigned to answer a question `j` if they share **at least one** tag: \[ P[i] \cap Q[j] \neq \emptyset \] Each person can answer **at most one** question, and each question can be answered by **at most one** person. ### Task Compute an assignment of people to questions that: 1. **Maximizes** the number of answered questions. 2. Subject to (1), **maximizes** the total priority sum of answered questions. Return: - the maximum number of matched (answered) questions - the maximum achievable total priority under that maximum match count ### Input/Output format (you may choose a reasonable one) - Tags are strings. - Total number of tags across all people/questions can be large. ### Follow-ups 1. Describe a brute-force approach and its complexity. 2. Improve the time complexity using a hash-based index (e.g., `tag -> list of people/questions`). 3. If processing questions in priority order, explain how a priority queue could help in your implementation.

Quick Answer: This question evaluates competencies in bipartite matching and combinatorial optimization, along with practical data-structure design for scalable tag-based assignment and priority-aware selection.

Part 1: Optimal person-to-question assignment

You are given a list of people and a list of questions. `people[i]` is the list of expertise tags for person `i`. `question_tags[j]` is the list of tags for question `j`, and `priorities[j]` is that question's non-negative priority. A person can answer a question if they share at least one tag. Each person can answer at most one question, and each question can be answered by at most one person. Compute the best possible assignment under this lexicographic objective: first maximize the number of answered questions, and among all such assignments maximize the total priority of answered questions. Return `(max_answered, max_priority_sum)`. Treat each tag list as a set, so duplicate tags do not change compatibility.

Constraints

  • 0 <= len(people), len(question_tags) <= 60
  • 0 <= priorities[j] <= 10^6
  • Each tag is a non-empty string
  • Duplicate tags may appear in an input list but should be treated as one tag

Examples

Input: ([['python', 'sql'], ['java'], ['ml']], [['sql'], ['java', 'python'], ['ml'], ['go']], [5, 7, 4, 10])

Expected Output: (3, 16)

Explanation: All three people can be matched: person 0 to question 0 or 1, person 1 to question 1, and person 2 to question 2. The best priority total among size-3 matchings is 16.

Input: ([['a'], ['a']], [['a'], ['a'], ['b']], [1, 10, 100])

Expected Output: (2, 11)

Explanation: Question 2 is impossible to answer. The maximum matching size is 2, and the best two compatible questions have priorities 10 and 1.

Input: ([['x'], ['y']], [['a'], ['b']], [5, 9])

Expected Output: (0, 0)

Explanation: No person shares any tag with any question.

Input: ([['a', 'b']], [['a'], ['b']], [2, 8])

Expected Output: (1, 8)

Explanation: Only one question can be answered because there is only one person, so choose the higher-priority compatible question.

Input: ([], [['a']], [1])

Expected Output: (0, 0)

Explanation: With no people, no question can be answered.

Hints

  1. Model the problem as bipartite matching: people on one side and questions on the other.
  2. A min-cost max-flow formulation can maximize matching size first and priority sum second by placing the priority on the question side as an edge cost.

Part 2: Brute-force matching for tiny inputs

Solve the same assignment objective as Part 1, but under very small constraints. `people[i]` contains the tags for person `i`, `question_tags[j]` contains the tags for question `j`, and `priorities[j]` is the priority of question `j`. A person can answer a question if they share at least one tag. Each person and each question can be used at most once. Return `(max_answered, max_priority_sum)`, maximizing the number of answered questions first and total priority second. The intended approach is exhaustive search or backtracking.

Constraints

  • 0 <= len(people), len(question_tags) <= 8
  • 0 <= priorities[j] <= 10^6
  • Tag lists may contain duplicates; treat them as sets

Examples

Input: ([['python'], ['sql']], [['python'], ['sql'], ['java']], [5, 3, 9])

Expected Output: (2, 8)

Explanation: The first two questions can both be answered, for a total priority of 8.

Input: ([['a'], ['a']], [['a'], ['a'], ['a']], [2, 9, 5])

Expected Output: (2, 14)

Explanation: At most two questions can be answered because there are only two people. Choose the two highest-priority compatible questions.

Input: ([['x']], [['a'], ['b']], [4, 6])

Expected Output: (0, 0)

Explanation: The single person is incompatible with every question.

Input: ([['a']], [], [])

Expected Output: (0, 0)

Explanation: There are no questions to assign.

Hints

  1. Process people one by one. For each person, either skip them or assign one currently unused compatible question.
  2. Because the limits are tiny, a recursive search over assignments is acceptable.

Part 3: Build the compatibility graph with a hash-based tag index

You are given `people` and `question_tags`. A person is compatible with a question if they share at least one tag. Return the compatibility graph in question-centric form: for each question `j`, output a sorted list of all person indices `i` such that person `i` can answer question `j`. The challenge is to do this efficiently when the total number of tags is large, without checking every person-question pair.

Constraints

  • 0 <= len(people), len(question_tags) <= 10^5
  • The total number of tag occurrences across all people and questions is at most 2 * 10^5
  • Tag lists may contain duplicates; treat them as sets

Examples

Input: ([['python', 'sql'], ['java'], ['sql', 'ml']], [['sql'], ['java', 'python'], ['go'], []])

Expected Output: [[0, 2], [0, 1], [], []]

Explanation: Question 0 matches people 0 and 2; question 1 matches people 0 and 1; the others match nobody.

Input: ([['a', 'a'], ['b', 'a']], [['a', 'a'], ['b'], ['c']])

Expected Output: [[0, 1], [1], []]

Explanation: Duplicate tags should not create duplicate person indices.

Input: ([], [['x'], []])

Expected Output: [[], []]

Explanation: With no people, every question has an empty compatibility list.

Input: ([['x']], [[]])

Expected Output: [[]]

Explanation: A question with no tags is incompatible with everyone.

Hints

  1. Build a dictionary from each tag to the people who have it.
  2. A person may be reached through multiple tags of the same question, so remember to deduplicate.

Part 4: Online greedy assignment using priority queues

This problem uses a different rule from Part 1. Questions already exist, each with a tag list and a priority. People then arrive one by one in the given order. When a person arrives, assign them the single unanswered compatible question with the highest priority. If several compatible unanswered questions have the same priority, assign the one with the smallest question index. If no compatible unanswered question exists, assign `-1` for that person. Return the list of assigned question indices. Tag lists should be treated as sets, so duplicates do not matter. The intended solution uses priority queues and lazy deletion.

Constraints

  • 0 <= len(question_tags), len(people) <= 10^5
  • 0 <= priorities[j] <= 10^9
  • The total number of tag occurrences across questions and people is at most 2 * 10^5
  • Question tags and person tags may contain duplicates; treat them as sets

Examples

Input: ([['sql'], ['python'], ['python', 'ml']], [5, 7, 6], [['python'], ['sql', 'ml'], ['ml']])

Expected Output: [1, 2, -1]

Explanation: The first person gets question 1, the second gets question 2, and the third has no unanswered compatible question left.

Input: ([['a'], ['b'], ['a', 'b']], [4, 4, 4], [['a', 'b'], ['b'], ['a']])

Expected Output: [0, 1, 2]

Explanation: All priorities tie, so the smallest compatible question index is chosen each time.

Input: ([['a', 'a'], ['b']], [10, 3], [['a', 'a'], ['c'], []])

Expected Output: [0, -1, -1]

Explanation: Duplicate tags do not change the result. Only the first person can take question 0.

Input: ([], [], [['x']])

Expected Output: [-1]

Explanation: There are no questions to assign.

Hints

  1. Store questions in a max-priority structure per tag, keyed by `(-priority, question_index)`.
  2. Because the same question may appear in multiple heaps, use lazy deletion when a question has already been answered.
Last updated: Jun 4, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ 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 Rooms and Top-K Streams - Google (medium)
  • Find Containing Range - Google (medium)
  • Rearrange Tasks With Cooldown - Google (medium)
  • Implement Employee Management and Expression Evaluation - Google (medium)
  • Solve Three Array and Matrix Path Problems - Google (medium)