FastPrep
Problem · Array

Get Minimum Time

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Developers at Amazon have deployed an application with a distributed database. It is stored on total_servers different servers numbered from 1 to total_servers that are connected in a circular fashion, i.e. 1 is connected to 2, 2 is connected to 3, and so on until total_servers connects back to 1.

There is a subset of servers represented by an array servers of integers. They need to transfer the data to each other to be synchronized. Data transfer from one server to one it is directly connected to takes 1 unit of time. Starting from any server, find the minimum amount of time to transfer the data to all the other servers.

Function

getMinTime(total_servers: int, servers: int[]) → int

Complete the function getMinTime in the editor.

getMinTime takes the following arguments:

  1. int total_servers: The number of servers in the system
  2. int servers[n]: The servers to share the data with

Returns

int: The minimum time required to transfer the data on all the servers

🍊 A million thanks, spike 👍

Examples

Example 1

total_servers = 8servers = [2, 6, 8]return = 4
Example 1 illustration
Two possible paths are shown, but there can be many more. One path goes from 2 to 6 to 8 taking 6 units of time. The other path goes from 2 to 8 to 6 and takes 4 units of time. Return the shorter path length, 4.

Example 2

total_servers = 5servers = [1, 5]return = 1
The two servers are directly connected so it will take only 1 unit of time to share the data.

Example 3

total_servers = 10servers = [4, 6, 2, 9]return = 7
An optimal strategy is to start from server 2 and go to 4, then 6, then 9. It takes 2 + 2 + 3 = 7 units of time.

Constraints

  • 1 ≤ total_servers ≤ 109
  • 1 ≤ n ≤ 105
  • 1 ≤ servers[i] ≤ n

More Amazon problems

drafts saved locally
public int getMinTime(int total_servers, int[] servers) {
  // write your code here
}
total_servers8
servers[2, 6, 8]
expected4
checking account