Frontend School

Maximum K-Shared Feature Group

DSA
hard

Maximum K-Shared Feature Group

Hard
Bit Manipulation
Dynamic Programming
Algorithms

Overview

In the context of understanding user demographics and interests on a platform like LinkedIn, identifying groups of users who share very specific common attributes is crucial for targeted outreach, content recommendations, and community building. Each user's profile can be represented as a bitmask, where individual bits correspond to distinct features or interests (e.g., skills, industries, groups). This problem challenges you to find the largest possible group of users who collectively possess a precisely defined set of k common features.

What you need to do / Task

Your task is to implement a function maxKSharedFeatureGroup that takes an array of non-negative integers profiles (representing user feature sets) and an integer k. The function should return the maximum possible size of a group of users such that:

  1. There exists a common feature mask M with exactly k bits set (popcount(M) == k).
  2. Every user P in the identified group possesses all features specified by M. That is, for every user P in the group, (P & M) == M.

Input & output

Function Signature: function maxKSharedFeatureGroup(profiles: number[], k: number): number

  • profiles: An array of non-negative integers, where each integer profiles[i] represents a unique user's feature set as a bitmask.
  • k: An integer representing the exact number of common features required for the group's defining mask M.

Return Value:

  • A single non-negative integer representing the maximum size of such a group. If no such group can be formed (e.g., no mask M with popcount(M) == k yields any users, or k is out of valid range for available bits), return 0.

Clarifications

  • Unique profiles: All numbers in profiles are guaranteed to be unique.
  • Bit positions: Assume features are represented by bits from 0 up to 19 (inclusive), meaning profiles will be less than 2^20.
  • Popcount: popcount(X) refers to the number of set bits (1s) in the binary representation of X.

Examples

1

Example 1

Input:

profiles = [3, 5, 6], k = 1

Output:

2

Note:

Profiles in binary: 3 (011_2), 5 (101_2), 6 (110_2). k = 1. We need to find a common mask M with popcount(M) == 1 that maximizes group size.

  • If M = 1 (001_2): Users 3 (011) and 5 (101) both have bit 0 set. Group: {3, 5}. Size: 2.
  • If M = 2 (010_2): Users 3 (011) and 6 (110) both have bit 1 set. Group: {3, 6}. Size: 2.
  • If M = 4 (100_2): Users 5 (101) and 6 (110) both have bit 2 set. Group: {5, 6}. Size: 2. The maximum group size is 2.
2

Example 2

Input:

profiles = [7, 15, 11], k = 2

Output:

3

Note:

Profiles in binary: 7 (0111_2), 15 (1111_2), 11 (1011_2). k = 2. We need a common mask M with popcount(M) == 2. Consider M = 3 (0011_2) (bits 0 and 1 set, popcount=2):

  • 7 (0111) has bits 0 and 1 set. (7 & 3) == 3. Yes.
  • 15 (1111) has bits 0 and 1 set. (15 & 3) == 3. Yes.
  • 11 (1011) has bits 0 and 1 set. (11 & 3) == 3. Yes. Thus, for M=3, the group {7, 15, 11} of size 3 is valid. There are other masks with popcount=2 (e.g., M=5, M=6), but none yield a larger group. The maximum group size is 3.
3

Example 3

Input:

profiles = [1, 2, 4, 8], k = 2

Output:

0

Note:

Profiles in binary: 1 (0001_2), 2 (0010_2), 4 (0100_2), 8 (1000_2). k = 2. Each profile has exactly one bit set (popcount=1). To form a group, we need a common mask M with popcount(M) == 2. If M has two bits set (e.g., M=3 (0011_2)), no profile in the input profiles can be a superset of M, because each profile only has one bit set. Thus, no group can be formed, and the maximum size is 0.

Constraints

Constraints & assumptions

  • 1 <= profiles.length <= 10^5
  • 0 <= profiles[i] < 2^20 (i.e., profiles fit within 20 bits)
  • 0 <= k <= 20
  • All profiles[i] values are unique.

What interviewers evaluate

  • Algorithm Design: Ability to identify and apply an efficient algorithm (e.g., dynamic programming over subsets/supersets) to solve the problem within complexity limits.
  • Bit Manipulation Proficiency: Correct and effective use of bitwise operators (AND, OR, shifts) and understanding of bit properties (e.g., popcount).
  • Edge Case Handling: Correctly addressing scenarios like empty groups, k=0, or k being larger than any possible popcount.
  • Code Quality & Readability: Clean, well-structured, and understandable code with appropriate variable naming.

Loading editor...