## 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

Here is a solution with O(N*log(N)) time and O(N) space. I think the trick to this question is to make an appropriate data structure to represent the medal distribution. I used a hashmap to remember where and by how much the medal count per officer varies.
Ex:
If the medal count is:

``20 20 20 25 25 10 10 10 10 10``

My data structure remembers:

``````0 -> 20 (starting at index 0, officers have 20 more medals than previously)
3 -> 5 (starting at index 3, officers have 5 more medals than previously)
5 -> -15 (starting at index 5, officers have 15 less medals than previously)``````

Here is my solution in Java:

``````int firstOfficerToExceedCumulativeThreshold(
int N, int[] count, int[] from, int[] to, int THRESHOLD) {
MedalDestribution MD = new MedalDestribution();
for (int i = 0; i < N; ++i) {
MD.awardMedals(count[i], from[i], to[i] + 1);
}
return MD.getOfficerWithNthMedal(THRESHOLD + 1);
}

class MedalDestribution {

private static int NUMBER_OF_OFFICERS = 1000000;

private Map<Integer, Integer> valueChange;

public medalDestribution() {
valueChange = new HashMap<Integer, Integer>();
valueChange.put(NUMBER_OF_OFFICERS + 1, 0);
}

// 'from' is inclusive while 'to' is exclusive.
public int awardMedals(int count, int from, int to) {
valueChange.put(from, valueChange.getOrDefault(from, 0) + count);
valueChange.put(to, valueChange.getOrDefault(to, 0) - count);
}

public int getOfficerWithNthMedal(int N) {
int[] changeIndices = valueChange.keySet().toArray();
Arrays.sort(changeIndices);
int sum = 0;
int rangeValue = 0;
int lastOfficer = 0;
for (int currentOfficer : changeIndices) {
sum += rangeValue * (currentOfficer - lastOfficer);
if (sum >= N) {
return currentOfficer - 1 - (sum - N) / rangeValue;
}
rangeValue += valueChange.get(currentOfficer);
lastOfficer = currentOfficer;
}
return -1;
}
}``````

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

this is wrong code.

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

getOrDefault() method is not defined in this code.

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

getOrDefault(key, defaultValue) is part of the Map interface since Java 8.

Given a map m, it returns map.get(key) if it exists, otherwise, it returns defaultValue.

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

Here's my solution:

``````int medalWinner(int n, int[] count, int[] from, int[] to, int threshold){
//build sorted set of medal distributions
MedalDist[] medalDist = new MedalDist[n];
for(int i = 0; i < n; i ++){
medalDist[i] = new MedalDist(count[i], from[i], to[i]);
}
Arrays.sort(medalDist);

PriorityQueue<ModelDist> ends = new PriorityQuery<ModelDist>(0, new Comparator<ModelDist>(){
public void int compare(ModelDist m1, ModelDist m2){
return m1.to - m1.to;
}
});
int pos = 0;
int tStart, tEnd, count = 0;
while(pos < n){
tStart = modelDist[pos].from;
ModelDist end = ends.peek();
tEnd = (end == null) ? Integer.MAX.VALUE, end.to;
if(tStart < tEnd){
count += modelDist[pos].count;
if(count >= threshold){
return modelDist[pos].from;
}
pos++;
}
else{
count -= end.count;
ends.poll();
}
}
return -1;
}

class ModelDist implements Comparable{

int count;
int from;
int to;

ModelDist(int count, int from, int to){
this.count = count;
this.from = from;
this.to = to;
}

public int compareTo(ModelDist other){
return this.from - other.from;
}
}``````

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

``````public class CandidateCode
{
public static void main(String[] args) {
int answer = DistributingMedals(1,new int[]{1},new int[]{1},new int[]{10},2);
System.out.println(answer);
}

public static int DistributingMedals(int input1,int[] input2,int[] input3,int[] input4,int input5)
{

int officerIndex = -1;
if (InputsValid(input1, input2, input3, input4, input5))
{
int medalsCount = 0;
for (int i = 0; i < input1; i++)
{
for (int o = input3[i]; o <= input4[i]; o++)
{
medalsCount += input2[i];
if (medalsCount > input5)
{
officerIndex = o;
break;
}
}
if (medalsCount > input5)
break;
}
}
return officerIndex;

}

private static boolean InputsValid(int input1, int[] input2, int[] input3, int[] input4, int input5)
{
if (((1 <= input1) && (input1 <= 1000))
&& ((input2.length == input1) && (input3.length == input1) && (input4.length == input1))
&& ((1 <= input5) && (input5 <= 1000000000)))
{
int ok = 0;
for (int i = 0; i < input1; i++)
{
if ((1 <= input3[i] && input3[i] <= input4[i] && input4[i] <= 1000000)
&& (1 <= input2[i] && input2[i] <= 100))
ok++;
}
if (ok == input1)
return true;
}
return false;
}``````

}

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

public static int DistributingMedals(int input1, int[] input2, int[] input3, int[] input4, int input5)
{

int officerIndex = -1;
if (InputsValid(input1, input2, input3, input4, input5))
{
int medalsCount = 0;
for (int i = 0; i < input1; i++)
{
for (int o = input3[i]; o <= input4[i]; o++)
{
medalsCount += input2[i];
if (medalsCount > input5)
{
officerIndex = o;
break;
}
}
if (medalsCount > input5)
break;
}
}
return officerIndex;

}

private static bool InputsValid(int input1, int[] input2, int[] input3, int[] input4, int input5)
{
if (((1 <= input1) && (input1 <= 1000))
&& ((input2.Length == input1) && (input3.Length == input1) && (input4.Length == input1))
&& ((1 <= input5) && (input5 <= 1000000000)))
{
int ok = 0;
for (int i = 0; i < input1; i++)
{
if ((1 <= input3[i] && input3[i] <= input4[i] && input4[i] <= 1000000)
&& (1 <= input2[i] && input2[i] <= 100))
ok++;
}
if (ok == input1)
return true;
}
return false;
}

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