Katkat
Back

Find shared courses between student pairs

Walmart LabsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently map relationships and compute intersections between multiple sets to identify commonalities across pairs.

Problem Statement

You are given a list of student-course associations, where each entry is a tuple (student_id, course_id). Your task is to find all pairs of students who share at least k courses in common.

Return a list of results where each result is a tuple (student_a, student_b, shared_courses_list). To avoid duplicates and self-comparison, ensure that for every pair, student_a < student_b.

Function Signature

def find_shared_courses(enrollments, k):

Constraints

  • enrollments: A list of (student_id, course_id) tuples.
  • k: Integer, the minimum number of shared courses required.
  • The number of students N and courses M can be up to 10,000.

Examples

Example 1: Input: enrollments = [('Alice', 'Math'), ('Alice', 'History'), ('Bob', 'Math'), ('Bob', 'Physics'), ('Charlie', 'Math'), ('Charlie', 'History')] k = 2

Output: [('Alice', 'Charlie', ['Math', 'History'])] Explanation: Alice and Charlie both take Math and History (count = 2).

Edge Cases

  • k is larger than the number of courses any student takes.
  • There are no students with any shared courses.
  • Multiple students share exactly k courses.

Hints

Hint 1

First, transform the list of tuples into a dictionary where each student maps to a set of their enrolled courses for O(1) lookups.

Hint 2

Instead of checking every pair of students, you can iterate through the courses and map each course to a list of students who are enrolled in it.

Hint 3

Use a counter dictionary to keep track of the number of shared courses between every pair of students you encounter while iterating through the course-to-student map.

Follow-up questions

  • How would you optimize the solution if the number of enrollments is extremely large and doesn't fit into memory?
  • If the input is updated in real-time as students enroll in courses, how would you maintain the shared course counts efficiently?
  • What is the time complexity of your current solution, and how does it change if many students take almost all courses?