Q2. Given a graph of N nodes named with 1 to N and M bidirectional weighted edges. Find the path from 1 to N such that the weight of the maximum in the path is minimum and the number of edges in the path won’t exceed K.

Sample Input:

N = 4, M = 4, K = 3
Edge 1 ↔ 2, weight = 4
Edge 1 ↔ 3, weight = 2
Edge 2 ↔ 3, weight = 5
Edge 2 ↔ 4, weight = 5
Edge 3 ↔ 4, weight = 6

Output:

5

Explanation:

Possible routes from 1 to 4 are:

• 1 → 2 → 3 → 4
• 1 → 3 → 2 → 4

The maximum edge weight in path 1 → 2 → 4 is 5 on the edge 2 → 4.
The maximum edge weight in path 1 → 3 → 2 → 4 is 6 on edge 3 → 2.

Since we need to minimize the maximum weight in the path, the answer is 5.

---

Q1. Given an array of integers arr and an integer K. While maintaining the order, split into exactly K pieces such that the sum of the maximum of every sub-array is minimum.

Example

Sample Input:

arr = [1, 5, 3, 4, 2]
K = 2

Output:

6

Explanation:

Possible splits are:

• [1], [5, 3, 4, 2]
• [1, 5], [3, 4, 2]
• [1, 5, 3], [4, 2]
• [1, 5, 3, 4], [2]

The minimum sum of maximums would be:

• [1], [5, 3, 4, 2]
  • max(1) + max(5, 3, 4, 2) = 1 + 5 = 6

Thus, the answer is 6.

Constraints:

• 1 < K <= N <= 300
• 1 ≤ arr[i] < 10⁶

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.