## Interview Question for Developer Program Engineers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;
public class CandidateCode
{  static int officerno=0;
public static int DistributingMedals(int input1,int[] input2,int[] input3,int[] input4,int input5)
{
int sum=0;
int iteration=0;

boolean flag=false;
while(iteration<input1){
for(int i=input3[iteration];i<=input4[iteration];i++)
{sum+=input2[iteration];
if(sum>input5)
{ officerno=i;
flag=true;
break;
}

}
if(flag==false)
iteration++;
else
break;
}
if(officerno!=0)
return officerno;
else
return -1;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

does it pass all the test cases and values? like those ^6 and ^9 inputs?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Python with a bit adjusted interface:

input1 = size of start & stop
input2 = not used, assumes all elements are 1
input3 = start
input4 = stop
input5 = T

time complexity: O(N * log(N)) where N is the size of the start/stop array
space complexity: O(1)

``````def solution(start, stop, T):
N = len(start)
assert N == len(stop)
start.sort()
stop.sort()
start_i = 0
stop_i = 0
sum = 0
i = 1  # next officer to process (indices are 1-based)
while sum <= T:
# count how many medals the next officer has (+1 for each opened range;
# -1 for each closed range)
while start_i < N and start[start_i] <= i:
start_i += 1
while stop_i < N and stop[stop_i] < i:
stop_i += 1
medal_count = start_i - stop_i

# find the next officer that might have a different medal count (the
# first in or the first after some range); if none may change it, we
# have passed all the ranges, no further officers have any medals and
# we will never cross the total awarded medal count threshold
if stop_i == N:
return -1
next_i = stop[stop_i] + 1  # the first after some range
if start_i < N:
next_i = min(start[start_i], next_i)  # or the first in some range

# skip the least number of officers needed to either cross the total
# awarded medal count threshold or we reach the next officer that might
# have a different medal count
officer_count = next_i - i
if medal_count:
officer_count = min(officer_count, (T - sum) // medal_count + 1)
i += officer_count
sum += medal_count * officer_count
return i - 1  # last processed officer

import pytest

@pytest.mark.parametrize("start, stop, T, expected", (
# index: 1 2 3 4 ...
# count: 0 0 0 0 ...
# sum  : 0 0 0 0 ...
([], [], 0, -1),
([], [], 1, -1),

# index: 1 2 3 4 ...
# count: 1 0 0 0 ...
# sum  : 1 1 1 1 ...
([1], [1], 0, 1),
([1], [1], 1, -1),

# index: 1 2 3 4 ...
# count: 2 0 0 0 ...
# sum  : 2 2 2 2 ...
([1, 1], [1, 1], 0, 1),
([1, 1], [1, 1], 1, 1),
([1, 1], [1, 1], 2, -1),
([1, 1], [1, 1], 3, -1),

# index: 1 2 3 4 ...
# count: 0 1 1 0 ...
# sum  : 0 1 2 2 ...
([2], [3], 0, 2),
([2], [3], 1, 3),
([2], [3], 2, -1),
([2], [3], 3, -1),

# index: 1 2 3 4 5 ...
# count: 0 1 0 1 0 ...
# sum  : 0 1 1 2 2 ...
([2, 4], [2, 4], 0, 2),
([2, 4], [2, 4], 1, 4),
([2, 4], [2, 4], 2, -1),
([2, 4], [2, 4], 3, -1),

# index: 1 2 3 4 5 6 7 ...
# count: 0 1 1 0 1 1 0 ...
# sum  : 0 1 2 2 3 4 4 ...
([2, 5], [3, 6], 0, 2),
([2, 5], [3, 6], 1, 3),
([2, 5], [3, 6], 2, 5),
([2, 5], [3, 6], 3, 6),
([2, 5], [3, 6], 4, -1),
([2, 5], [3, 6], 4, -1),

#index: 1  2  3  4  5  6  7  8 ...
#count: 0  1  2  3  3  2  1  0 ...
#sum  : 0  1  3  6  9 11 12 12 ...
([2, 3, 4], [7, 6, 5], 0, 2),
([2, 3, 4], [7, 6, 5], 1, 3),
([2, 3, 4], [7, 6, 5], 2, 3),
([2, 3, 4], [7, 6, 5], 3, 4),
([2, 3, 4], [7, 6, 5], 4, 4),
([2, 3, 4], [7, 6, 5], 5, 4),
([2, 3, 4], [7, 6, 5], 6, 5),
([2, 3, 4], [7, 6, 5], 7, 5),
([2, 3, 4], [7, 6, 5], 8, 5),
([2, 3, 4], [7, 6, 5], 9, 6),
([2, 3, 4], [7, 6, 5], 10, 6),
([2, 3, 4], [7, 6, 5], 11, 7),
([2, 3, 4], [7, 6, 5], 12, -1),
([2, 3, 4], [7, 6, 5], 13, -1),

#index: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
#count: 0  0  1  1  2  2  3  3  3  3  2  2  1  1  0 ...
#sum  : 0  0  1  2  4  6  9 12 15 18 20 22 23 24 24 ...
([3, 5, 7], [14, 12, 10], 0, 3),
([3, 5, 7], [14, 12, 10], 1, 4),
([3, 5, 7], [14, 12, 10], 2, 5),
([3, 5, 7], [14, 12, 10], 3, 5),
([3, 5, 7], [14, 12, 10], 4, 6),
([3, 5, 7], [14, 12, 10], 5, 6),
([3, 5, 7], [14, 12, 10], 6, 7),
([3, 5, 7], [14, 12, 10], 7, 7),
([3, 5, 7], [14, 12, 10], 8, 7),
([3, 5, 7], [14, 12, 10], 9, 8),
([3, 5, 7], [14, 12, 10], 10, 8),
([3, 5, 7], [14, 12, 10], 11, 8),
([3, 5, 7], [14, 12, 10], 12, 9),
([3, 5, 7], [14, 12, 10], 13, 9),
([3, 5, 7], [14, 12, 10], 14, 9),
([3, 5, 7], [14, 12, 10], 15, 10),
([3, 5, 7], [14, 12, 10], 16, 10),
([3, 5, 7], [14, 12, 10], 17, 10),
([3, 5, 7], [14, 12, 10], 18, 11),
([3, 5, 7], [14, 12, 10], 19, 11),
([3, 5, 7], [14, 12, 10], 20, 12),
([3, 5, 7], [14, 12, 10], 21, 12),
([3, 5, 7], [14, 12, 10], 22, 13),
([3, 5, 7], [14, 12, 10], 23, 14),
([3, 5, 7], [14, 12, 10], 24, -1),
([3, 5, 7], [14, 12, 10], 25, -1)))
def test_solution(start, stop, T, expected):
assert solution(start, stop, T) == expected``````

Comment hidden because of low score. Click to expand.
0

input2 can be easily supported by tracking how many medals each start/stop adds/removes to the current medal count and not just add +-1 to the current medal count when crossing an iteration's start/stop boundary.

You can do this by using extra O(N) space for storing this information or, if you are allowed to modify the original input data, you could even keep the O(1) space complexity by encoding the count inside the sorted start/stop arrays, e.g. start/stop[i] + 1000000 * count[i]; since 1 <= start/stop[i] <= 10^6 and 1 <= count[i] <= 100 this would fit inside a 32-bit integer.

Comment hidden because of low score. Click to expand.
0

You could also tweak the implementation to make it a bit faster on the average by using sentinel elements instead of constantly explicitly checking start/stop array boundaries. But that could require extra O(N) space if adding the extra sentinel values causes the start/stop array data storage to be reallocated.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.