Amazon OA | SDE

help
, , , , ,
1

You are an engineer at Amazon and you have been assigned a task to construct network in the office

For computers to be on the same network, there are the following constraints:

  1. They must be adjacent to one another.
  2. There must be a minimum number of computers.
  3. The total processing speed of the network (the sum of each computer’s processing speed) must be at least a certain threshold.
  4. A computer can only belong to one network.

Given the processing speeds and order of the computers, as well as the network constraints, determine the maximum number of networks that can be formed.

** In lame term this question can be explained as find maximum number of subarray having length >minLength and sum >= minSpeedThreshold**
Example n=6
speed= [5, 7, 9, 12, 10, 13]
minComps = 2
speedThreshold = 15

Output: 2
Explanation : Since the min length of the sub-array should be > 2 && sum should be >speedThreshold
so the two network will be as 7+9+12=28 and 10+13 =23

Can we solve this in O(n) or even O(nlog n)

2

Why not simply use sliding window

3

There is no good reason to leave out any elements i.e. we must include all elements in some subarrays as it helps increase both count and sum. Now that we are looking at the partition of array, greedy makes perfect sense. Therefore starting from the first elements we maintain sum and count and keep updating as we iterate. The moment both are past the threshold; we start afresh.

1 Like
4

Use two pointer method .Keep left pointer at starting index and iterate the array using right pointer.Whenever both the conditions are met i.e.the sum of speed>= threshold and right-left+1>=minComputer ,increase ur ans count by 1 ,move left pointer to right pointer+1 and make sum to 0. Time complexity of this approach will be O(n).

5

I approach was similar but the interviewer wan’ satisfied with that so I thought that there might be some optimization possible. Any ways thank you.

6

Is it a Amazon Interview question?? or assesment?

I think this is a simple single traversal.

1-You can’t use sorting here because it is asking for adjacent computers.

2- You can use window sliding but it is unnecessary use of space and also it will increase time complexity because u need to empty queue when conditions are matched. Since it is asking for one element in on set.

3-I think Two pointer will not work here for every case I am not sure.

4-Since it is asking for adjacent computers just use simple for loop maintaining three variables result, sum and one for checking computers should be greater than equal to min_computers and when both conditions are satisfied just increment result and make sum and m equal to 0 .At the end result will be answer.