FastPrepCount Routes Through Four Shop Types
Problems/Count Routes Through Four Shop Types

Count Routes Through Four Shop Types

OpenAI logoOpenAI● MediumFULLTIMENEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report supplies the four shop types, undirected roads, exact-once counting objective, distinct reverse routes, and the six-route example. Practice extends the reported limits of 50 shops and 250 roads to 200 shops and 20,000 roads and deduplicates repeated road pairs. The core task is an approximately 95% source match.

A town has shops.length shops. Shop i has type shops[i], where the four types are numbered from 0 through 3.

The array roads contains undirected roads. Each pair [u, v] connects shops u and v.

Return the number of ordered routes that satisfy all of these rules:

  • The route contains exactly four distinct shops.
  • Consecutive shops are connected by a road.
  • The four shop types are exactly 0, 1, 2, and 3, each appearing once.

A route and the same shops visited in reverse order count as two routes. Duplicate road pairs, if supplied, still describe one road.

Function

countShopRoutes(shops: int[], roads: int[][]) → long

Examples

Example 1

shops = [0,1,2,3]roads = [[0,1],[1,2],[2,3]]return = 2

The valid ordered routes are 0 → 1 → 2 → 3 and 3 → 2 → 1 → 0.

Example 2

shops = [0,1,2,3,3]roads = [[0,1],[1,2],[2,3],[2,4]]return = 4

Either type-3 shop can finish the route from 0 through 1 and 2. Each route also counts in reverse, for four ordered routes total.

Example 3

shops = [1,0,3,2,2]roads = [[0,1],[1,2],[1,4],[2,3],[2,4]]return = 6

The six valid ordered routes are [0,1,2,3], [0,1,2,4], [0,1,4,2], [3,2,1,0], [4,2,1,0], and [2,4,1,0]. Each visits one shop of every type using the undirected roads.

Constraints

  • 1 <= shops.length <= 200
  • shops[i] is one of 0, 1, 2, or 3.
  • 0 <= roads.length <= 20000
  • Every road is [u, v] with 0 <= u, v < shops.length and u != v.
  • The answer fits in a signed 64-bit integer.

More OpenAI problems

  • Determine the Winner of Three-Card HandsPHONE SCREEN · Seen Nov 2026
  • Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Light Source Hits: Sample, Compare, and FitPHONE SCREEN · Seen Nov 2026
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public long countShopRoutes(int[] shops, int[][] roads) {
        // write your code here
    }
}
Checking account…