How should I practice Delivery Service?

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

Is Delivery Service associated with InMobi?

FastPrep tags this as a InMobi online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Delivery Service

Learn this problem

● Hard

InMobiFULLTIMEOA

Problem statement

A logistics network spans n cities numbered 1 through n. Each day has a morning shift and an afternoon shift.

The network uses 2 * n state nodes:

Nodes 1 through n are the morning states of cities 1 through n.
Nodes n + 1 through 2 * n are the afternoon states. Node i + n is the afternoon state of city i.

The array routes lists scheduled directed courier routes. Each entry [u, v] means that a package can travel from state node u to state node v.

Within every city i, a package can always transition from its morning state i to its afternoon state i + n. It can never transition automatically from afternoon back to morning. These implicit morning-to-afternoon transitions are not included in routes.

A delivery from city u to city v is possible if a package starting at the morning state of city u can reach either the morning state or the afternoon state of city v by following scheduled routes and implicit transitions.

Return the number of ordered city pairs (u, v) for which delivery is impossible.

Function

countImpossibleDeliveries(n: int, routes: int[][]) → long

Examples

Example 1

n = 2routes = []return = 2

Each city can reach only itself through its implicit morning-to-afternoon transition. The impossible ordered pairs are (1, 2) and (2, 1).

Example 2

n = 3routes = [[1,2],[2,3]]return = 3

City 1 can deliver to every city, city 2 cannot deliver to city 1, and city 3 cannot deliver to cities 1 or 2. Therefore, 3 ordered pairs are impossible.

Example 3

n = 2routes = [[3,2]]return = 1

Node 3 is the afternoon state of city 1. City 1 reaches node 3 through its implicit transition and then reaches the morning state of city 2 through the scheduled route. City 2 still cannot deliver to city 1, so exactly one ordered pair is impossible.

Constraints

1 ≤ n ≤ 50,000
0 ≤ routes.length ≤ 100,000
routes[i].length = 2
1 ≤ routes[i][0], routes[i][1] ≤ 2 * n