Katkat
Back

Match people to questions using tags and priorities

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a constrained matching problem using greedy or flow-based approaches while managing priority queues for tie-breaking.

Problem Statement

You are building a matching engine for a Q&A platform. There are n users and m questions. Each user has a set of tags they are interested in (e.g., "python", "sql"), and each question is associated with a single tag. Each user also has an experience_level (an integer).

We need to assign each question to exactly one user such that:

  1. The user's interests include the question's tag.
  2. A user can handle at most k questions.
  3. If multiple users qualify for a question, the user with the highest experience_level is preferred.

Design a system that assigns the maximum possible number of questions to users according to these rules.

Function Signature

def match_questions(users, questions, k):
    # users: list of dicts {'id': int, 'tags': set, 'experience': int}
    # questions: list of dicts {'id': int, 'tag': str}
    # k: int (max questions per user)
    # Returns: list of tuples (question_id, user_id)

Constraints

  • n, m = 1

Example

Input: users = [{'id': 1, 'tags': {'java'}, 'experience': 5}, {'id': 2, 'tags': {'java'}, 'experience': 10}] questions = [{'id': 101, 'tag': 'java'}, {'id': 102, 'tag': 'java'}], k = 1 Output: [(101, 2), (102, 1)] Explanation: User 2 takes 101 (higher experience), then User 1 takes 102.

Edge Cases

  • No user matches a specific question's tag.
  • More questions than total capacity (n * k).
  • Ties in experience level.

Hints

Hint 1

Consider processing questions in a specific order to ensure the highest-experience users get their preferred matches first.

Hint 2

Since we want to prioritize high-experience users, grouping questions by tag and sorting available users by experience level within those tags is efficient.

Hint 3

Use a max-heap or a sorted data structure to keep track of available users who are qualified for a specific tag.

Follow-up questions

  • How would your solution change if users had different capacities 'k_i' instead of a global 'k'?
  • If the requirement changed to 'assign questions to minimize the total experience gap between matched users', how would the complexity change?
  • How would you handle the assignment if questions had deadlines, requiring us to match them in a specific chronological window?