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;
   
    }
}

- Nitin September 05, 2014 | Flag Reply
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?

- doxy reign September 11, 2014 | Flag Reply
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

- Jurko Gospodnetić November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jurko Gospodnetić November 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jurko Gospodnetić November 16, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More