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

- djmclaugh September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is wrong code.

- Captain September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

getOrDefault() method is not defined in this code.

- Captain September 08, 2014 | Flag Reply
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.

- Anonymous September 08, 2014 | Flag
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;
  }
}

- Anonymous September 08, 2014 | Flag Reply
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;
    }

}

- Anonymous September 11, 2014 | Flag Reply
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;
}

- Anonymous September 12, 2014 | Flag Reply


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