Frontend School

Host Community Connectivity

DSA
medium

Host Community Connectivity

Medium
Union Find
Graph
Data Structures

Overview

Airbnb thrives on fostering connections, not just between guests and homes, but also among its hosts. To support initiatives like local host meetups, shared resource programs, or identifying regional host leaders, it's crucial to efficiently determine if hosts belong to the same 'community' based on various shared criteria. This problem challenges you to design a system that can manage host relationships and quickly answer queries about community membership.

What you need to do / Task

Your task is to implement a HostCommunityManager class that efficiently handles host relationships and community queries.

  1. Constructor: Implement HostCommunityManager(numHosts). This should initialize the system for numHosts hosts, indexed from 0 to numHosts - 1. Initially, each host is in their own distinct community.
  2. Establish Relationship: Implement establishRelationship(hostA, hostB). This method should merge the communities of hostA and hostB, indicating they are now part of the same collective.
  3. Check Community: Implement areInSameCommunity(hostA, hostB). This method should return true if hostA and hostB currently belong to the same community, and false otherwise.

Input & output

HostCommunityManager(numHosts: number)

  • numHosts: An integer representing the total number of hosts to manage. Hosts are identified by 0-indexed integers from 0 to numHosts - 1.
  • Returns: void (constructor).

establishRelationship(hostA: number, hostB: number): void

  • hostA, hostB: Integers representing the IDs of two hosts whose communities should be merged.
  • Returns: void.

areInSameCommunity(hostA: number, hostB: number): boolean

  • hostA, hostB: Integers representing the IDs of two hosts to check for community membership.
  • Returns: true if hostA and hostB are in the same community; false otherwise.

Clarifications

  • Host IDs are 0-indexed integers.
  • A host is always considered to be in the same community as themselves.
  • Calling establishRelationship with hosts already in the same community should not cause errors and should result in no change to the community structure.

Examples

1

Example 1

Input:

operations = ["HostCommunityManager","establishRelationship","establishRelationship","areInSameCommunity","areInSameCommunity","establishRelationship","areInSameCommunity"], params = [[4],[0,1],[2,3],[0,1],[0,2],[0,2],[1,3]]

Output:

[null,null,null,true,false,null,true]

Note:

  1. Initialize for 4 hosts: {0}, {1}, {2}, {3}
  2. establishRelationship(0, 1): Communities are now {0,1}, {2}, {3}
  3. establishRelationship(2, 3): Communities are now {0,1}, {2,3}
  4. areInSameCommunity(0, 1): Returns true (0 and 1 are connected)
  5. areInSameCommunity(0, 2): Returns false (0 is not connected to 2)
  6. establishRelationship(0, 2): Communities are now {0,1,2,3} (0's community merges with 2's)
  7. areInSameCommunity(1, 3): Returns true (1 and 3 are now connected via 0 and 2)
2

Example 2

Input:

operations = ["HostCommunityManager","establishRelationship","areInSameCommunity","establishRelationship","areInSameCommunity","areInSameCommunity"], params = [[3],[0,1],[0,1],[1,1],[0,2],[1,2]]

Output:

[null,null,true,null,false,false]

Note:

  1. Initialize for 3 hosts: {0}, {1}, {2}
  2. establishRelationship(0, 1): Communities are now {0,1}, {2}
  3. areInSameCommunity(0, 1): Returns true
  4. establishRelationship(1, 1): No change, 1 is already in its own community. Communities remain {0,1}, {2}
  5. areInSameCommunity(0, 2): Returns false
  6. areInSameCommunity(1, 2): Returns false
3

Example 3

Input:

operations = ["HostCommunityManager","establishRelationship","establishRelationship","establishRelationship","areInSameCommunity"], params = [[5],[0,1],[1,2],[3,4],[0,4]]

Output:

[null,null,null,null,false]

Note:

  1. Initialize for 5 hosts: {0}, {1}, {2}, {3}, {4}
  2. establishRelationship(0, 1): {0,1}, {2}, {3}, {4}
  3. establishRelationship(1, 2): {0,1,2}, {3}, {4}
  4. establishRelationship(3, 4): {0,1,2}, {3,4}
  5. areInSameCommunity(0, 4): Returns false (0 and 4 are in different communities)

Constraints

Constraints & assumptions

  • 1 <= numHosts <= 10^5
  • 0 <= hostA, hostB < numHosts
  • The total number of calls to establishRelationship and areInSameCommunity combined will not exceed 2 * 10^5.
  • All provided host IDs (hostA, hostB) will be valid within the 0 to numHosts - 1 range.

What interviewers evaluate

  • Correctness: The Union-Find data structure is correctly initialized and all operations (find, union) are implemented without logical errors.
  • Efficiency: establishRelationship and areInSameCommunity operations achieve near-constant time complexity (amortized O(α(N))) through optimizations like path compression and union by size/rank.
  • Code Quality: The code is clean, well-structured, readable, and follows good programming practices.
  • Problem Comprehension: Demonstrates a clear understanding of the problem requirements and constraints, handling edge cases implicitly or explicitly.

Loading editor...