LinkedIn SSE OA

Round 1

Questions:

Question

1. 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

2. 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.