Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
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
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.
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.
- Nitin September 05, 2014