Panda Guru LogoPanda
Guru

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