Meesho | OA | SDE - 1
Summary
I attempted the Meesho OA for an SDE-1 role, where I was asked to maximize the sum of efficiencies for processor deployment.
Full Experience
A supercomputer has several processors to deploy for execution. They are arranged sequentially in a row from 1 to n. The efficiency of each processor depends on the order of deployment of its adjacent processors. For the ith processor, the efficiency of the ith processor is no_adjacent[i], or both_adjacent[i], depending on whether neither, one, or both adjacent processors are deployed before it. Find the maximum possible sum of efficiencies among all possible orders of deployment. Note: The first and nth processors can only have one adjacent processor. Example n = 4 no_adjacent = [ 1, 2, 3, 4] one_adjacent = [4, 4, 2, 1] both_adjacent = [1, 1, 1, 1]
Consider the following orders of deployment (1 -based indexing): If the deployment sequence is (1->3->4->2), the sum of efficiencies - no_adjacent[1] + no_adjacent[3] + one_adjacent[4] + both_adjacent[2] = 1+3+1+1 = 6 (4-2-1-3), no_adjacent[4] + no_adjacent[2] + one_adjacent[1] + both_adjacent[3] = 4+2+4+1 = 11.
Let the deployment sequence be (4->3->2->1), no_adjacent[4] + one_adjacent[3] + one_adjacent[2] + one_adjacent[1] = 4+2+4+4=14. Similarly, other deployment orders can be performed. Amongst all possible deployments, the maximum possible sum of efficiencies is 14.
Interview Questions (1)
Maximum Efficiency Sum for Processor Deployment
A supercomputer has several processors arranged sequentially in a row from 1 to n. Each processor has three possible efficiency values:
no_adjacent[i]if none of its adjacent processors are deployed before it.one_adjacent[i]if exactly one adjacent processor is deployed before it.both_adjacent[i]if both adjacent processors are deployed before it (except for the first and last processors which have only one neighbor). Given the arraysno_adjacent,one_adjacent, andboth_adjacent, determine an order of deployment that maximizes the total sum of efficiencies.
Input:
n: number of processors.no_adjacent[1..n]one_adjacent[1..n]both_adjacent[1..n]
Output:
- The maximum possible sum of efficiencies over all deployment orders.
Example:
n = 4
no_adjacent = [1, 2, 3, 4]
one_adjacent = [4, 4, 2, 1]
both_adjacent = [1, 1, 1, 1]
One optimal deployment order is 4 -> 3 -> 2 -> 1 yielding a sum of 14.