Maximum Compatibility Score Sum - Practice Coding Problems

Maximum Compatibility Score Sum - Problem

There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes).

The survey was given to m students numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the i-th student. The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the j-th mentor.

Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.

For example, if the student's answers were [1, 0, 1] and the mentor's answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.

You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.

Given students and mentors, return the maximum compatibility score sum that can be achieved.

Input & Output

Example 1 — Basic Case

$ Input: students = [[1,1,0],[1,0,1]], mentors = [[1,0,1],[0,1,1]]

› Output: 4

💡 Note: Student 0 with Mentor 0: [1,1,0] vs [1,0,1] → 2 matches (positions 0). Student 1 with Mentor 1: [1,0,1] vs [0,1,1] → 2 matches (positions 2). Total: 2 + 2 = 4.

Example 2 — Different Assignment Better

$ Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[0,1],[1,1]]

› Output: 0

💡 Note: All students answer [0,0]. Best pairing gives 0 compatibility since no mentor matches any student perfectly. Any assignment results in score 0.

Example 3 — Perfect Matches

$ Input: students = [[1,0,1],[0,1,0]], mentors = [[1,0,1],[0,1,0]]

› Output: 6

💡 Note: Perfect matching: Student 0 with Mentor 0 gives 3 matches, Student 1 with Mentor 1 gives 3 matches. Total: 3 + 3 = 6.

Constraints

1 ≤ m ≤ 8
1 ≤ n ≤ 50
students[i].length == mentors[j].length == n
students[i][k] is either 0 or 1
mentors[j][k] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Surveys

Students and mentors with binary answers to questions

Calculate Compatibility

Count matching answers between each student-mentor pair

Optimal Assignment

Find pairing that maximizes total compatibility score

Key Takeaway

🎯 Key Insight: This assignment problem can be solved efficiently using dynamic programming with bitmasks since m ≤ 8

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

This is an assignment optimization problem where we need to find the best one-to-one pairing between students and mentors. The key insight is that with small constraints (m ≤ 8), we can use dynamic programming with bitmasks to efficiently explore all possible assignments while avoiding redundant calculations. Time: O(2ᵐ × m × n), Space: O(2ᵐ × m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(m! × m × n)	O(m)	Try all possible student-mentor pairings recursively
Dynamic Programming with Bitmask	O(2ᵐ × m × n)	O(2ᵐ × m)	Use memoization with bitmask to avoid recalculating subproblems

Brute Force with Backtracking — Algorithm Steps

Calculate compatibility scores for all student-mentor pairs
Use backtracking to try assigning each student to each available mentor
Track the maximum sum across all complete pairings

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute Scores

Calculate compatibility between each student-mentor pair

Backtrack

Try assigning each student to each available mentor

Find Maximum

Return the highest total compatibility sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int backtrack(int studentIdx, bool* usedMentors, int** compatibility, int m) {
    if (studentIdx == m) {
        return 0;
    }
    
    int maxScore = 0;
    for (int mentorIdx = 0; mentorIdx < m; mentorIdx++) {
        if (!usedMentors[mentorIdx]) {
            usedMentors[mentorIdx] = true;
            int score = compatibility[studentIdx][mentorIdx] + backtrack(studentIdx + 1, usedMentors, compatibility, m);
            if (score > maxScore) {
                maxScore = score;
            }
            usedMentors[mentorIdx] = false;
        }
    }
    
    return maxScore;
}

int solution(int** students, int** mentors, int m, int n) {
    // Precompute compatibility scores
    int** compatibility = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        compatibility[i] = (int*)malloc(m * sizeof(int));
        for (int j = 0; j < m; j++) {
            int score = 0;
            for (int k = 0; k < n; k++) {
                if (students[i][k] == mentors[j][k]) {
                    score++;
                }
            }
            compatibility[i][j] = score;
        }
    }
    
    bool* usedMentors = (bool*)calloc(m, sizeof(bool));
    int result = backtrack(0, usedMentors, compatibility, m);
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(compatibility[i]);
    }
    free(compatibility);
    free(usedMentors);
    
    return result;
}

int main() {
    // Simple parsing for small inputs - assumes format [[1,1,0],[1,0,1]]
    int m = 2, n = 3; // Hardcoded for demo
    
    int** students = (int**)malloc(m * sizeof(int*));
    int** mentors = (int**)malloc(m * sizeof(int*));
    
    for (int i = 0; i < m; i++) {
        students[i] = (int*)malloc(n * sizeof(int));
        mentors[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Read and parse - simplified for demo
    students[0][0] = 1; students[0][1] = 1; students[0][2] = 0;
    students[1][0] = 1; students[1][1] = 0; students[1][2] = 1;
    mentors[0][0] = 1; mentors[0][1] = 0; mentors[0][2] = 1;
    mentors[1][0] = 0; mentors[1][1] = 1; mentors[1][2] = 1;
    
    int result = solution(students, mentors, m, n);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(students[i]);
        free(mentors[i]);
    }
    free(students);
    free(mentors);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m! × m × n)

m! permutations, each taking O(m×n) to calculate compatibility scores

✓ Linear Growth

Space Complexity

O(m)

Recursion stack depth and used mentor tracking array

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler