Quick Overview

This question evaluates understanding of graph connectivity and equivalence relations, requiring recognition of connected components from an adjacency-matrix representation of pairwise similarity.

Count Similar Photo Groups

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given `n` photos labeled `0` to `n - 1` and an `n x n` binary matrix `isSimilar`. - `isSimilar[i][j] = 1` means photo `i` and photo `j` are **directly similar**. - `isSimilar[i][j] = 0` means they are not directly similar. Similarity is also **transitive**: if photo `A` is similar to `B`, and `B` is similar to `C`, then `A` is considered similar to `C` even if `A` and `C` are not directly similar. Treat each set of directly or indirectly similar photos as one **photo group**. Return the total number of photo groups. You may assume the similarity relationship is symmetric, so if `isSimilar[i][j] = 1`, then `isSimilar[j][i] = 1`.

Quick Answer: This question evaluates understanding of graph connectivity and equivalence relations, requiring recognition of connected components from an adjacency-matrix representation of pairwise similarity.

You are given a binary matrix `isSimilar` representing similarity relationships among photos. Photo indices range from `0` to `n - 1`, where `n` is the number of photos. - `isSimilar[i][j] = 1` means photo `i` and photo `j` are directly similar. - `isSimilar[i][j] = 0` means they are not directly similar. Similarity is transitive: if photo `A` is similar to `B`, and `B` is similar to `C`, then `A` and `C` belong to the same group even if `isSimilar[A][C] = 0`. Treat each set of directly or indirectly similar photos as one photo group. Return the total number of photo groups. If the input matrix is empty, return `0`.

Constraints

  • 0 <= n <= 200
  • `isSimilar` is an `n x n` matrix
  • Each value in `isSimilar` is either `0` or `1`
  • `isSimilar[i][j] == isSimilar[j][i]` for all valid `i`, `j`

Examples

Input: []

Expected Output: 0

Explanation: There are no photos, so there are no groups.

Input: [[1]]

Expected Output: 1

Explanation: A single photo forms one group by itself.

Hints

  1. Think of each photo as a node in an undirected graph, and each `1` as an edge.
  2. Count how many times you need to start a new DFS or BFS from an unvisited photo.

Loading coding console...