How should I practice Optimal Transfer?

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

Is Optimal Transfer associated with Visa?

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

Optimal Transfer

Visa● HardINTERNOA

Learn

Problem statement

There are n servers in a network, arranged in ascending order of their capacities. The capacity of server i is capacity[i].

The distance between server i and server j is |capacity[i] - capacity[j]|. When n > 1, each server's closest server is the one with the smallest distance in capacity, and that closest server is guaranteed to be unique.

You may perform either of the following operations from a server x:

Connect directly to any server y at cost |capacity[x] - capacity[y]|.
When another server exists, connect to the closest server of x at a fixed cost of 1.

Given query arrays fromServer and toServer, compute the minimum cost required to connect from fromServer[i] to toServer[i] for every query. A connection may be direct or may route through intermediate servers. A query whose start and destination are equal costs 0.

Function

getMinCost(capacity: int[], fromServer: int[], toServer: int[]) → int[]

Examples

Example 1

capacity = [2,7,10]fromServer = [0,1,2]toServer = [2,2,1]return = [2,1,1]

The closest-server moves are 0 -> 1, 1 -> 2, and 2 -> 1, each at cost 1. Therefore the optimal costs are 0 -> 1 -> 2 = 2, 1 -> 2 = 1, and 2 -> 1 = 1.

Example 2

capacity = [2,3,5,6]fromServer = [0,2,0]toServer = [3,0,1]return = [4,3,1]

The closest-server moves are 0 -> 1, 1 -> 0, 2 -> 3, and 3 -> 2. The minimum costs are 1 + 2 + 1 = 4 from 0 to 3, 2 + 1 = 3 from 2 to 0, and 1 from 0 to 1.

Example 3

capacity = [1,4,9,15]fromServer = [0,3,1]toServer = [3,0,3]return = [12,3,11]

The directed closest-server moves are 0 -> 1, 1 -> 0, 2 -> 1, and 3 -> 2. Walking through adjacent servers costs 12, 3, and 11 for the three queries.

Constraints

1 <= n, m <= 2 * 10^5.
1 <= capacity[i] <= 10^9.
capacity is strictly increasing.
When n > 1, every server has a unique closest server.
fromServer.length == toServer.length == m.
0 <= fromServer[i], toServer[i] < n.