How should I practice Is Graph Bipartite??

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Is Graph Bipartite? associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Is Graph Bipartite?

Microsoft● MediumNEW GRADFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given an adjacency-list representation of an undirected graph. The vertices are numbered from 0 through graph.length - 1, and graph[u] lists every neighbor of vertex u.

Return true when the vertices can be divided into two groups such that every edge connects vertices from different groups. Otherwise, return false.

The graph may be disconnected.

Function

isBipartite(graph: int[][]) → boolean

Examples

Example 1

graph = [[1,2,3],[0,2],[0,1,3],[0,2]]return = false

Vertices 0, 1, and 2 form an odd cycle.

Example 2

graph = [[1,3],[0,2],[1,3],[0,2]]return = true

One valid partition is {0, 2} and {1, 3}.

Example 3

graph = [[],[]]return = true

Two isolated vertices have no conflicting edge.

Constraints

1 <= graph.length <= 500
Every neighbor is in the range from 0 through graph.length - 1.
No vertex lists itself, and a neighbor appears at most once in one adjacency list.
The graph is undirected: if v appears in graph[u], then u appears in graph[v].