Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
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;
}
}
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;
}
}
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;
}
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:
My data structure remembers:
Here is my solution in Java:
- djmclaugh September 07, 2014