How should I practice Two-Color an Undirected Graph?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple online assessment problems in FastPrep.

Is Two-Color an Undirected Graph associated with Apple?

FastPrep tags this as a Apple coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Graph

Two-Color an Undirected Graph

Learn this problem

● MediumAppleFULLTIMEPHONE SCREEN

Problem statement

Given n nodes numbered from 0 through n - 1 and an array edges of undirected edges, return whether the graph can be colored with two colors so that the endpoints of every edge have different colors.

Each entry edges[i] = [u, v] represents an undirected edge between nodes u and v.

Function

canTwoColor(n: int, edges: int[][]) → boolean

Examples

Example 1

n = 4edges = [[0,1],[1,2],[2,3],[3,0]]return = true

Color nodes 0 and 2 with one color, and nodes 1 and 3 with the other. Every edge joins differently colored nodes.

Example 2

n = 3edges = [[0,1],[1,2],[2,0]]return = false

The three nodes form an odd cycle. Whichever color is assigned to node 0, nodes 1 and 2 must both receive the other color even though they share an edge.

Example 3

n = 5edges = [[0,1],[2,3],[3,4]]return = true

Each connected part can be colored independently while still using the same two available colors.