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.

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.

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.

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

  1. Think about reversing the relationship: instead of employee -> interests, build interest -> employees.
  2. 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

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

Loading coding console...