How should I practice Minimum Direction Violations?

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

Is Minimum Direction Violations associated with Google?

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

Minimum Direction Violations

Google● MediumFULLTIMEINTERNONSITE INTERVIEW

Problem statement

You are given a directed graph with n vertices numbered from 0 to n - 1. Each pair [u, v] in edges is an original directed edge from u to v.

You may traverse every listed edge in either direction:

Traversing from u to v, the original direction, costs 0 violations.
Traversing from v to u, against the original direction, costs 1 violation.

Return the minimum total number of direction violations needed to travel from start to end.

Interview Follow-Ups

Negative edge weights: If a generalized version allows negative edge weights, 0-1 BFS no longer applies. Use Bellman-Ford, and handle any reachable negative-cycle policy required by that version.
Multiple sources and destinations: Add a super-source with zero-cost edges to every source and a super-sink with zero-cost edges from every destination. Then solve one shortest-path query from the super-source to the super-sink. With the original 0/1 costs, 0-1 BFS remains valid.

These follow-ups are explanatory and do not change the judged function.

Function

minimumDirectionViolations(n: int, edges: int[][], start: int, end: int) → int

Examples

Example 1

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

Follow 0 -> 1, reverse 2 -> 1 to move 1 -> 2, follow 2 -> 3, and reverse 4 -> 3 to move 3 -> 4. Exactly two traversals oppose their original directions, and no path uses fewer violations.

Example 2

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

The path 0 -> 1 -> 2 -> 3 follows every original edge direction, so its total violation cost is 0.

Example 3

n = 3edges = [[1,0],[0,2],[2,1]]start = 0end = 1return = 0

Reversing the direct edge 1 -> 0 would cost 1, but the longer path 0 -> 2 -> 1 follows original directions and costs 0.

Constraints

1 <= n <= 100000
0 <= edges.length <= 200000
Every entry in edges contains exactly two valid vertex indices.
0 <= start, end < n
end is reachable from start when all edge directions are ignored.