Round 1
Questions:
Question
-
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 minimized.
- Sample Input:
arr = [1, 5, 3, 4, 2], K = 2
- Output:
6
- 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 maximum would be = [1], [5, 3, 4, 2] = 1 + 5 = 6
Constraints:
- 1 < K <= N < 300
- 1 < arr[i] < 10^5
- Sample Input:
-
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 minimized and the number of edges in the path won't exceed K.
- Sample Input:
N = 4, M = 4, K=3 Edge = 1 <-> 2 = 4 Edge = 1 <-> 3 = 2 Edge = 2 <-> 4 = 5 Edge = 2 <-> 3 = 6
- Output:
5
- Possible routes from 1 to 4 are [1->2->3, 1->3->2->4]. The maximum in path 1 -> 2 -> 4 is 5 on the edge 2->4, while in 1->3->2->4 it is 6 at edge 3->2.
- Sample Input:
Candidate's Approach
For the first question, I solved it using a 2D DP approach in N*K time. However, for the second one, I encountered a TLE on some cases since my brute-force DFS solution was not efficient enough within the given time constraints, while the expected solution would be in O(N) or O(NlogN).
Interviewer's Feedback
No feedback provided.