How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bytedance during technical interviews.

Count Similar Photo Groups | Bytedance Coding Question

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.

Input: [[1,1,0],[1,1,0],[0,0,1]]

Expected Output: 2

Explanation: Photos 0 and 1 are connected, while photo 2 is alone, giving 2 groups.

Input: [[1,0,0],[0,1,0],[0,0,1]]

Expected Output: 3

Explanation: No two different photos are similar, so each photo is its own group.

Input: [[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]

Expected Output: 2

Explanation: Photos 0, 1, and 2 are all connected through transitivity, and photo 3 is separate.

Input: [[1,0,0,1,0],[0,1,1,0,0],[0,1,1,0,0],[1,0,0,1,0],[0,0,0,0,1]]

Expected Output: 3

Explanation: The groups are {0,3}, {1,2}, and {4}, so the answer is 3.

Hints

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

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.