Flipkart Interview Question
SDE1sCountry: India
Interview Type: In-Person
static int CalculateEarning(int[] groups,int nbTours,int busCapacity)
{
if (groups.Length == 0 || busCapacity <= 0 || nbTours <=0)
return 0;
int[] tempArray = groups.Where(g => g < busCapacity).ToArray();
int result = 0;
for (int i = 0; i < nbTours;i++ )
{
int nbGroupsInBus = 0;
int localResult = 0;
while (nbGroupsInBus < tempArray.Length && localResult + tempArray[0] <= busCapacity)
{
localResult += tempArray[0];
LeftShiftArray(tempArray);
nbGroupsInBus++;
}
result += localResult;
}
return result;
}
private static void LeftShiftArray(int[] tempArray)
{
int tempValue = tempArray[0];
for (int i = 0; i < tempArray.Length -1; i++)
{
tempArray[i] = tempArray[i+1];
}
tempArray[tempArray.Length - 1] = tempValue;
}
Operates with O(nm) complexity and O(1) memory where n is the number of groups and m is the number of trips.
public static int getNumberMoved(int[] groups, int busSize, int trips){
int position = 0;
int total = 0;
while(trips > 0){
int thisTripPosition = position;
int totalForThisTrip = groups[thisTripPosition];
thisTripPosition = (thisTripPosition + 1) % groups.length;
while(totalForThisTrip + groups[thisTripPosition ] <= busSize && thisTripPosition != position){
totalForThisTrip += groups[thisTripPosition ];
thisTripPosition = (thisTripPosition + 1) % groups.length;
}
total += totalForThisTrip;
trips--;
}
return total;
}
- 1uttMentek May 27, 2015