How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Palantir.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Palantir during technical interviews.

Group employees by shared interests | Palantir Coding Question

Group employees by shared interests

Company: Palantir

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given N employees, each with an integer id and a set of interests (strings), write an algorithm to find all employees who share at least one common interest. Return either (a) a mapping from each interest to the sorted list of employee ids who have it, and/or (b) the list of all unique employee-id pairs (u, v) that share one or more interests. Analyze time and space complexity and provide code in your preferred language.

Quick Answer: This question evaluates a candidate's competency in organizing and querying collections, mapping relationships between entities, and reasoning about algorithmic time and space complexity within data structures and grouping operations.

Part 1: Map each interest to the sorted employee IDs

You are given a list of employees. Each employee is represented by an integer ID and a list of interest strings. Build an inverted index that maps every interest to the sorted list of employee IDs who have that interest. Treat each employee's interest list as a set, so repeated interests for the same employee should only count once.

Constraints

0 <= N <= 100000, where N is the number of employees
Employee IDs are unique integers
The total number of interest strings across all employees is at most 200000
Each interest string has length between 1 and 50
Duplicate interests within the same employee should be treated as one interest

Examples

Input: [(101, ['music', 'reading']), (102, ['sports', 'music']), (103, ['reading']), (104, [])]

Expected Output: {'music': [101, 102], 'reading': [101, 103], 'sports': [102]}

Explanation: Employees 101 and 102 share 'music', employees 101 and 103 have 'reading', and only 102 has 'sports'. Employee 104 contributes nothing.

Input: []

Expected Output: {}

Explanation: No employees means no interests in the result.

Hints

Think about reversing the relationship: instead of employee -> interests, build interest -> employees.
If an employee's list may contain duplicates, convert it to a set before adding the employee ID to each interest bucket.

Part 2: Return all unique employee-ID pairs that share an interest

You are given a list of employees. Each employee has an integer ID and a list of interest strings. Return all unique employee-ID pairs (u, v) such that u and v share at least one common interest. Each pair must appear only once even if the two employees share multiple interests. Return each pair with u < v, and sort the final list of pairs in ascending lexicographic order.

Constraints

0 <= N <= 5000, where N is the number of employees
Employee IDs are unique integers
The total number of interest strings across all employees is at most 20000
Duplicate interests within the same employee should be treated as one interest
The total number of generated candidate pairs across all interests is at most 200000

Examples

Input: [(1, ['music', 'sports']), (2, ['sports', 'cooking']), (3, ['music']), (4, ['travel'])]

Expected Output: [(1, 2), (1, 3)]

Explanation: Employees 1 and 2 share 'sports', and employees 1 and 3 share 'music'. Employee 4 shares nothing with others.

Input: []

Expected Output: []

Explanation: No employees means no shared-interest pairs.

Hints

First group employees by interest, then generate employee pairs inside each interest group.
Use a set of pairs so that if two employees share multiple interests, the pair is still returned only once.

Quick Overview

This question evaluates a candidate's competency in organizing and querying collections, mapping relationships between entities, and reasoning about algorithmic time and space complexity within data structures and grouping operations.