雪花秋季实习Core Engineer OA

Viewed 31

感觉是因为自己的能力不够,这三题真的写了很久也还没思路。对C++也不是很熟悉,真的尽力了。有大佬有思路欢迎交流。
snowflake_7.jpg
snowflake_8.jpg
snowflake_9.jpg
snowflake_10.jpg
snowflake_11.jpg

2 Answers

请问是要求c++作答吗

可选Java或者C++

用ChatGPT把图片转换成文本,方便阅读。明天思考一下来写代码。

1. Optimal Transfer

There are n servers in the network arranged in ascending order of their capacity. In the array capacity, the capacity of the ith server is capacity[i], where 0 ≤ i < n.

The distance between two servers, i and j, is defined as the absolute difference in their capacities: |capacity[i] - capacity[j]|. For each server i, the closest server j is the one with the smallest distance to i, and this closest server is unique.

To manage the network, the following operations can be done to server x:

  • Connect to any server y at a cost of |capacity[x] - capacity[y]| units.
  • Connect to the closest server of x for a fixed cost of one unit.

Given m queries, each defined by two integers fromServer[i] and toServer[i], find the minimum cost required to connect from fromServer[i] to toServer[i] for each query. The connection can be either direct or routed through a server z.

Note:

  • The values in the capacity array are distinct.

Example

n = 3, m = 3  
capacity = [2, 7, 10]  
fromServer = [0, 1, 2]  
toServer = [2, 2, 1]  

Optimal connections for each query

Starting server Ending server Path Cost
0 2 0 → 1 → 2 1 + 1 = 2
1 2 1 → 2 1
2 1 2 → 1 1

  • For 0 → 1: server 1 is closest because |2 - 7| < |2 - 10|
  • For 1 → 2: server 2 is closest because |7 - 10| < |7 - 2|
  • For 2 → 1: server 1 is closest because |10 - 7| < |10 - 2|