Current Status

Experience: 4+ years
Position: SSE at a top management consulting company
Location: Pune

Online Assessment

• Given an array arr consisting of N positive integers, find the product of the maximum of all possible subsets of the given array.

  • Input: [1, 2, 3]
  • Output: 324
  • Explanation:
    • All possible subsets of the given array with their respective maximum elements are:
      {1}, the maximum element is 1.
      {2}, the maximum element is 2.
      {3}, the maximum element is 3.
      {1, 2}, the maximum element is 2.
      {1, 3}, the maximum element is 3.
      {2, 3}, the maximum element is 3.
      {1, 2, 3}, the maximum element is 3.

  The product of all the above maximum element is 1232333 = 324.

  • Approach: Get list of all subsets of the input array and traverse it to get maximum product. Time Complexity: O(n*2^n)

• Given two positive integers X and Y and an array arr[] consisting of N positive integers such that arr[i] represents the height of the ith person and there is a tunnel of height H, the task is to find the total minimum cost required to pass all the N persons through the given tunnel such at most two-person whose sum of heights is less than H can pass at a time according to the following rules:

  • When two person passes through the tunnel at a time, then the cost is Y.
  • When one person passes through the tunnel at a time, then the cost is X.

  Note: All array elements are less than H.

  • Input: arr = [1, 3, 4, 4, 2], X = 4, Y = 6, H = 9
  • Output: 16
  • Explanation:
    • Person 1 and Person 4 having heights 1 and 4 respectively has the sum of heights as 1 + 4 = 5 < H. Therefore, the cost for this operation is Y = 6.
    • Person 2 and Person 3 having heights 3 and 4 respectively has the sum of heights as 3 + 4 = 7 < H. Therefore, the cost for this operation is Y = 6.
    • Person 5 has height 3 which is less than H. Therefore, the cost for this operation is is X = 4.

  The minimum among all possible combinations is 6+6+4 = 16, hence, return 16.

  • Approach:
    • Sort the given array arr[] in increasing order.
    • Initialize two pointers i and j as 0 and n-1 respectively to points to the extremities of the array.
    • Iterate until i < j. If arr[i] + arr[j] < H, then cost += Y, i += 1 and j -= 1. Else, j -= 1 and cost = X. If i == j then, cost += X.
    • Time Complexity: O(NlogN)

• A network is given in the form of a perfect binary tree and computations can occur at leaf nodes, while other nodes (distribution nodes) distribute data streams to the leaves. Two types of distributions are there – Splitting and Parallel.

  • Splitting Node: Splits the data into equal halves to the child nodes.
    • Example: [1,2,3,4] will split into [1,2] and [3,4] to left and right child.
  • Parallel Node: Splits the data into alternating halves to the child nodes.
    • Example: [1,2,3,4] will split into [1,3] and [2,4] to left and right child.

  Given the input streams that each leaf node receives and details of the distribution nodes, we need to find the original data stream at the root of the network.

  • Input: arr = [[1, 3], [5, 7], [2, 4], [6, 8]], distribution = [Parallel, Split]
  • Output: 12345678
  • Explanation:
    • 12345678 when distributed in parallel, evaluates as [[1, 3, 5, 7], [2, 4, 6, 8]].
    • [[1, 3, 5, 7], [2, 4, 6, 8]] further gets distributed in parallel, evaluates as [[1, 3], [5, 7], [2, 4], [6, 8]].

  Thus, return 12345678.

  Couldn't solve it, since I was short on time.

Result: Shortlisted