FastPrepGroup Attribute-Connected Triplets

Group Attribute-Connected Triplets

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Each row of entries is one entity with exactly three distinct string attributes. Two entities are directly connected when their rows share at least one exact attribute.

Connectivity is transitive. Return every connected component as an array of entry indices. Sort indices within a component, and sort components by their first index.

Repeated attributes across any number of rows connect all of those rows. Attribute matching is case-sensitive.

Function

groupAttributeTriplets(entries: String[][]) → int[][]

Examples

Example 1

entries = [["a","b","c"],["c","d","e"],["x","y","z"]]return = [[0,1],[2]]

Entries 0 and 1 share attribute c; entry 2 is isolated.

Example 2

entries = [["a","b","c"],["d","e","f"],["c","d","g"]]return = [[0,1,2]]

Entry 2 transitively joins the first two entries through c and d.

Example 3

entries = []return = []

No entries produce no components.

Constraints

  • 0 <= entries.length <= 200000.
  • Every row contains exactly three distinct attributes.
  • Attributes contain 1 through 30 letters or digits.
  • The total number of attribute characters is at most 5000000.

More Google problems

See Google hiring insights
public int[][] groupAttributeTriplets(String[][] entries) {
    // Write your code here.
}
entries[["a","b","c"],["c","d","e"],["x","y","z"]]
expected[[0,1],[2]]
Checking account…