I was asked a question to write a optimal program that would determine the total number of stops a elevator has taken to serve X number of people.

There is a elevator in a building with M floors. This elevator can take a max of X people at a time or max of total weight Y. Given that a set of people has arrived and their weight and the floor they need to stop given how many stops has the elevator taken to serve all the people. Consider elevator serves in the first come first serve basis.

Example:

Let Array A be the weight of people to be considered A[] = {60, 80, 40 }.

Let Array B be the floors where person needs to be dropped respectively B[] = {2, 3, 5}.

Total building floors be 5,max allowed person in elevator be 2 at a time with max weight capacity being 200. For this example, the elevator would take total of 5 stops floors ground, 2, 3, ground, 5, ground.

What would be the optimal code for this? Is there any other better solutions or ways to improve my code?

class Solution
{
    /// <summary>
    /// Return total stops used
    /// </summary>
    /// <param name="A">weight of people</param>
    /// <param name="B">floors they need to get down</param>
    /// <param name="M">total floors in the building</param>
    /// <param name="X">Max people to carry at a time</param>
    /// <param name="Y">max weight to carry at a time</param>
    /// <returns></returns>
    public int solution(int[] A, int[] B, int M, int X, int Y)
    {
        // initialize variables
        int totalStops = 0;
        long totalWeightPerRound = 0;
        int maxPersonsCount = 0;
        List<int> lstFloors = new List<int>();
        int currPerson = 0;
        bool startLift = false;
        while (currPerson < A.Length)
        {
            //Should current person be considered?
            if ((totalWeightPerRound + A[currPerson]) <= Y && (maxPersonsCount+1) <= X)
            {
                totalWeightPerRound += A[currPerson];
                maxPersonsCount++;
                lstFloors.Add(B[currPerson]);
                //If curr person is last person then start the lift
                if (currPerson == A.Length - 1)
                    startLift = true;

                currPerson++;
            }
            else
            {
                startLift = true;
            }

            if (startLift)
            {
                totalStops += lstFloors.Distinct().Count() + 1;
                //reset variable
                lstFloors.Clear();
                maxPersonsCount = 0;
                totalWeightPerRound = 0;
                startLift = false;
            }
        }

        return totalStops;
    }
}

So you said that the elevator works with the first come first serve basis. That screams like using a Queue. Moreover i like using classes as much as possible because i feel that implementing a solution becomes very easy because the abstraction is more on a human level and the readability increases. I demonstrate it on my code.


So first you know that you have Persons who want to drive from ground to a Target Floor. A Person also have a Weight. So i have implemented this in a class:

public class Person
{
    public int Weight { get; set; }

    public int ActualFloor { get; set; }

    public int TargetFloor { get; set; }

    public Person(int weight, int targetFloor, int actualFloor = 0)
    {
        this.Weight = weight;
        this.TargetFloor = targetFloor;
        this.ActualFloor = actualFloor;
    }
}

Naming: Moreover you know that the Elevator has different attributes too. You have implemented them in Y for Maximum Weight and X for the Maximum Number of People and i think that X and Y are really bad names for MaxWeight and MaxPeople. Why not name them what they are? That makes it easier for you as the coder and easier for other coworkers trying to understand your code.

My Elevator Properties and the Constructor are implemented as this:

public class Elevator
{
    public readonly int MaxWeight;

    public readonly int MaxPersons;

    public readonly int MaxFloors;

    public Queue<Person> Persons { get; set; }

    private List<Person> Passengers { get; set; }

    public Elevator(int maxFloors, int maxWeight, int maxPersons)
    {
        this.MaxFloors = maxFloors;
        this.MaxPersons = maxPersons;
        this.MaxWeight = maxWeight;
        this.Persons = new Queue<Person>();
        this.Passengers = new List<Person>();
    }
}

MaxWeight, MaxPersons and MaxFloors should be clear. The Queue Persons contains the People you want to drive around. Passengers are the People which are in this cycle in the elevator.

Now you can calculate the number of stops very easy:

public int CalculateNumberOfStops()
{
    int stops = 0;

    while (!this.Persons.IsEmpty())
    {
        while (this.IsOneMorePersonFitting())
        {
            this.Passengers.Add(this.Persons.Dequeue());
        }

        stops += this.Passengers.GroupBy(x => x.TargetFloor).Count();
        this.Passengers.Clear();

        // Drive to Floor Zero
        stops++;
    }

    return stops;
}

private bool IsOneMorePersonFitting()
{
    return !this.Persons.IsEmpty() &&
           this.Passengers.Sum(x => x.Weight) + this.Persons.Peek().Weight < this.MaxWeight &&
           this.Passengers.Count < this.MaxPersons;
}

I am shifting the People from the Queue into the List as long the cap of the elevator is not full and the Queue is not empty. The number of stops are calculated with the number of Groups in the List. If you have 2 Passengers and Pass 1 wants to Floor 1 and Pass 2 wants to Floor 2 then you will have two groups. But if both want to the same Floor then you will only have one group.


You can add persons and error check with a helper function like this:

public void AddPersons(IEnumerable<Person> persons)
{
    foreach (var person in persons)
    {
        // Check if person is valid:
        if (person.TargetFloor > this.MaxFloors ||
            person.Weight > this.MaxWeight)
        {
            throw new ArgumentException();
        }

        this.Persons.Enqueue(person);
    }
}

I extended the Methods of Queue with the IsEmpty function to make is a little easier to read:

public static class ExtensionHelper
{
    public static bool IsEmpty<T>(this Queue<T> queue)
    {
        return queue.Count == 0;
    }
}

Using the elevator:

static void Main(string[] args)
{
    var elevator = new Elevator(5, 200, 2);
    elevator.AddPersons(new[] { new Person(60, 2), new Person(80, 3), new Person(40, 5) });
    var stops = elevator.CalculateNumberOfStops();

    Console.WriteLine(stops);
    Console.ReadKey();
}

For better readability you could define an empty constructor and then use it as

var elevator = new Elevator() { MaxWeight = 200, MaxPersons = 2 };

but then you can't use a readonly field and the programmer must know what is needed for the instance.

  • Like the solution. If at max weight but not max person you could look forward for a person under weight going to a floor already stopping at. – paparazzo Apr 28 '17 at 19:43
class Solution

So you have a class named Solution so I guess this class will represent a solution to a given problem.
I assume that this class is a abstract class, because the term Solution is very abstract to me. Oops, it isn't abstract and (ooops again) it doesn't represent a solution to a given problem.

Do you see how relevant it is to name things in a meaningful and descriptive way ?

    public int solution(int[] A, int[] B, int M, int X, int Y)   

So we know that Solution isn't a good name for this class but solution as a methodname is worse. A methodname should be made out of a verb or a verbphrase. The best naming of this method would make the XML documentation "redundant". So let us take a look at the documentation:

    /// <summary>
    /// Return total stops used
    /// </summary>  

So GetTotalStops or CalculateTotalStops are for sure better names for that method, although they might not be the best.

    /// <param name="A">weight of people</param>
    /// <param name="B">floors they need to get down</param>
    /// <param name="M">total floors in the building</param>
    /// <param name="X">Max people to carry at a time</param>
    /// <param name="Y">max weight to carry at a time</param>

Although the problem statement is mentioning Let Array A be the weight of people to be considered one shouldn't use this a method parameters. There will be to much guessing and scrolling involved while digging through the code.

Maybe wheights, floors, totalFloors, maxTotalPeople, maxTotalWeight would be much better names.

So let us take a look at what we have now

public int GetTotalStops(int[] wheights, int[] floors, int totalFloors, int maxTotalPeople, int maxTotalWeight)
{

}  

This seems much better, but without a context aka a class name it isn't worth anything.


Now let us dig into the method. The first thing I noticed is this noise

// initialize variables  

which doesn't add any value to the code. Comments shouldn't describe what is done but why something is done in the way it is done.

//If curr person is last person then start the lift  

this comment is way better but seeing where this comment is written we see some more things

 //If curr person is last person then start the lift
 if (currPerson == A.Length - 1)
     startLift = true;  

 currPerson++;

For each iteration where the weight is inside the valid range you are checking this condition by accessing the Length of the int A[] and substract 1. By having a variable lastPerson (not the best name) we could eleminate that comment because it would be read like

 if (currPerson == lastPerson)
     startLift = true;  

 currPerson++;

but it still has a problem which is the omitting of braces {}. You shouldn't omit braces although they might be optional. By omitting them your code will be prone to errors and the intent will not be as clear as possible.

A problem which can arise is that a person who wants to use the elevater is overweight and exceeds the maximim weight the elevator can carry. In such a case the currPerson would never be incremented and the code would be struck in a infinite loop. This could be avoided if currPerson will be incremented outside of that if block which would arise another problem namely the last person problem. This can be avoided by having another check outside of the loop wether the elevator should start.


You are using a List<int> to store the floors where the persons want to exit the elevator. To determine the total stops you use Distinct().Count() + 1. If you would use the right tool for this job like a HashSet<int> which Add() method won't throw if the item to be added is already in the set, you could just use the Count property for adding to totalStops.


If this method we are speaking about would live in a class named Elevator we could store the totalFloors, maxTotalPeople and maxTotalWeight values as class level variables which would enable us to have some private "helper" methods like (bad naming coming) DoesExceedWeight(int weight) and we could reduce the count of the method arguments.


if ((totalWeightPerRound + A[currPerson]) <= Y && (maxPersonsCount+1) <= X)

If we change the last condition (maxPersonsCount+1) <= X) (after changing the name of X) to maxPersonsCount < maxTotalPeople) its intent is more clear. In addition if we switch the conditions the calculation and check for the maxTotalWeight aka Y won't sometimes be not needed.

As stated you should have classes (person and elevator) that includes the logic.

Your test case cannot be overweight.

If overweight should look forward and see if there is a weight that is under and preferably on the same floor.

totalStops += lstFloors.Distinct().Count() is wrong if you take multiple trips to the same floor

Terrible naming public int solution(int[] A, int[] B, int M, int X, int Y)

  • This is a codility question, which is why the method signature is like that. – John61590 Jun 6 '17 at 21:14
  • @John61590 Codility is a word? – paparazzo Jun 7 '17 at 0:43
  • codility.com – John61590 Jun 8 '17 at 20:48
  • @John61590 Does not not make it a word. Cool not looking to get into a fight. – paparazzo Jun 8 '17 at 20:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.