2
\$\begingroup\$

I'm working on this exercise:

There is a classroom which has M rows of benches in it. Also, N students will arrive one-by-one and take a seat.

Every student has a preferred row number(rows are numbered 1 to M and all rows have a maximum capacity K. Now, the students come one by one starting from 1 to N and follow these rules for seating arrangements:

Every student will sit in his/her preferred row(if the row is not full). If the preferred row is fully occupied, the student will sit in the next vacant row. (Next row for N will be 1) If all the seats are occupied, the student will not be able to sit anywhere.

Monk wants to know the total number of students who didn't get to sit in their preferred row. (This includes the students that did not get a seat at all)

Input

First line contains 3 integers N, M and K.
N - Number of students and
M - Number of rows and
K - maximum capacity of a row.

Next line contains N space separated integers Ai.
Ai - preferred row of ith student.

Output

Output the total number of students who didn't get to sit in their preferred row.

Constraints:

1≤N,M≤10^5

1≤K≤500

1≤Ai≤M

code:

public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int K = sc.nextInt();
    int[] a = new int[N+1];
    //int[] rows = new int[N+1];
    TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
    //put student preferences in a, ordered as they enter one by one
    for(int i=1;i<=N;i++){
        a[i] = sc.nextInt();
    }
    //put in the tree the available rows as key,value: key:row number, value: available capacity
    for(int i=1;i<=M;i++){
        tree.put(i, K);

    }
    //count of students that didn't get a seat
    int c=0;
    for (int i=1;i<=N;i++){
        //check if prefered row is availbe
        //available capacity
        //case1: preferred seat is available
        if(tree.get(a[i])>0){
            tree.put(a[i], tree.get(a[i])-1);
        }
        else{
            //case 2: preferred seat is full, check next vacant row.
            if(tree.higherKey(a[i])!=null && tree.get(tree.higherKey(a[i]))>0){
                int nextRow = tree.higherKey(a[i]);
                tree.put(nextRow, tree.get(nextRow)-1);
            }
            // if preferred row is M, then check row 1
            if(a[i]==M && tree.get(1)>0){
                tree.put(1, tree.get(1)-1);
            }
            //increment count of students who didn't get to sit in their preferred row 
            //(included those who didn't get a seat at all)
            c++;
        }
    }

    System.out.println(c);

}

I took into account all cases that are stated in the exercise. I want to know if I have anticipated all cases or am I missing a possible corner case.

\$\endgroup\$
  • 1
    \$\begingroup\$ "If all the seats are occupied, the student will not be able to sit anywhere." You do not implement this. You only implement moving to the next row once. But you should keep advancing until the student is seated unless all the seats are full. \$\endgroup\$ – mdfst13 Oct 12 '17 at 19:43
  • \$\begingroup\$ The note 'Next row for N will be 1' possibly ought to be 'Next row for M will be 1', as M is the number of rows. \$\endgroup\$ – CiaPan Oct 13 '17 at 17:01
  • \$\begingroup\$ Are you sure the case 2 is handled properly? Suppose the student wants to sit in a row 4, but the row number 4 is full, as well as the row 5. Will your code assign the student a place in the row 6? \$\endgroup\$ – CiaPan Oct 13 '17 at 17:11
  • \$\begingroup\$ Yes, I missed that case @CiaPan, as also mdfst13 mentioned. I will correct it and put it as an answer. \$\endgroup\$ – SarahData Oct 14 '17 at 6:41
  • \$\begingroup\$ Hints: 1) A student will not take any sit if all sits are used, so there's no need to process more than M×K students records if N exceeds M×K, just count them. 2) Once ''i''-th student is processed you don't need a[i] value anymore, so you may avoid storing them and instead just process a[] values as they come from the input stream. This would save some memory at the cost of mixing input operation with processing operation. And that could violate a single responsibility principle if not implemented carefully. \$\endgroup\$ – CiaPan Oct 14 '17 at 9:43
3
\$\begingroup\$

Thanks for sharing your code!
These are my thoughts on it:

Naming

Naming Conventions

Please read (and follow) the Java Naming Conventions

E.g.: you have variables with upper case names like N, M K. In java identifiers with (all) upper case indicate constants. But in your code these are variables and should therefore be (starting with) lower case letters.

You may have chosen this names including the case because they came from the problem statement. Nevertheless you should always stick to good naming. I would add the abbreviation from the problem statement as a comment to the variable:

    int numberOfStudensExpected = sc.nextInt();  // N
    int numberOfRowsInRoom = sc.nextInt(); // M
    int numberOfSeatsInRow = sc.nextInt(); // K

Choose you names from the problem domain, not from the technical solution.

You have identifier names like tree which refers to the type of the variabe. You should give it a name from your problem domain. Since it hols the capacity per row you decrement during processing it might be better named remainingCapacityPerRow.

Avoid single character names / abbreviations

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable. And/or you have to "reuse" variable names in different contexts. Both makes your code hard to read and understand for other persons. (keep in mind that you are that other person yourself if you look at your code in a few month!) The same is true for (uncommon) abbreviations. You might find them being obvious today, while you're actively dealing with the problem, but You might have to "relearn" them if you worked on something else for a while.

On the other hand in Java the length of identifier names names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

So your variable a should better be named preferedRowOfStudent. And your variable c should be named studentsWithoutSeat.

Along with the previous suggestion your code:

 if (tree.get(a[i]) > 0) {
     tree.put(a[i], tree.get(a[i]) - 1);

would change to:

 if (remainingCapacityPerRow.get(preferedRowOfStudent[i]) > 0) {
     remainingCapacityPerRow.put(preferedRowOfStudent[i], remainingCapacityPerRow.get(preferedRowOfStudent[i]) - 1);

As usual there are some exceptions for this suggestion. E.g. the running index of loops is usually held in a single letter named variable like i in:

for(int i =0; i<SOME_CONSTANT; i++)

But even there you should use more problem oriented names to support your readers, especially in nested loops like this:

for(int rowInRoom =0; rowInRoom <numberOfRowsInRoom; rowInRoom ++)
   for(int seatInRow =0; seatInRow<numberOfSeatsInRow; seatInRow++)

Use of language

Use temporary variable to simplify the code

within your for loop you access the same element of array a several times. You should assign this element to a temporary variable before the first use.
Some may say you should do this for performance, but at least for Java performance is not affected.

along with the Avoid single character names / abbreviations suggestion your code would change to this:

 int studentsPreferedRow = preferedRowOfStudent[i];
 // ...
 int rowsRemainigCapacity = remainingCapacityPerRow.get(studentsPreferedRow );
 if (rowsRemainigCapacity  > 0) {
     remainingCapacityPerRow.put(studentsPreferedRow , rowsRemainigCapacity--);

doesn't this read much better?

Avoid odd ball solutions

You store the list of students in an array while you store the list of banks and their capacities in a Collection object rather than in an array too. This is called an odd ball solution because you use different approaches for the same thing.

avoid comments

Your solution has some comments which somehow structure your method into "sections". You should better extract these "sections" into methods with names derived from your comments:

public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);        
    // read NMK
    int[] a = initialiseStudentRowPreferences(sc);
    TreeMap<Integer, Integer> tree = initializeRoom(N,K);
    int c = countStudentThatDidNotGetASeat(tree, a)
    System.out.println(c);
} 
// ...
private int countStudentThatDidNotGetASeat(TreeMap<Integer, Integer> tree,int[] a){
   // do method extraction at all levels:
    int c = 0;
    for (int i = 1; i <= N; i++) {
      int studentsPreferedRow =  a[i];       
      if(isPreferedRowAvailable(tree, studentsPreferedRow ))
        reduceCapacity(tree, studentsPreferedRow);
      } else {
         c += placeStudentInOtherRow(tree, studentsPreferedRow ))
      }
    }
    return c;
}
// ...

However, Comments should explain why the code is like it is, not what the code does. When ever you feel you need to explain your code try to find better names for your identifiers (variables and methods).

OOP

Your code is a procedural approach to the problem.

There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.

OOP doesn't mean to "split up" code into random classes.

The ultimate goal of OOP is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (among others):

  • information hiding / encapsulation
  • single responsibility
  • separation of concerns
  • KISS (Keep it simple (and) stupid.)
  • DRY (Don't repeat yourself.)
  • "Tell! Don't ask."
  • Law of demeter ("Don't talk to strangers!")
\$\endgroup\$
  • \$\begingroup\$ Very informative! Thank you. I used variables which aren't long because in case of coding interview, I have to write fast. Thus, I didn't opt for using names from the problem domain. Otherwise, can you tell me what short keyboard command that can be used to avoid writing a name of an already declared variable each time you use it? (considering that I use Eclipse) \$\endgroup\$ – SarahData Oct 13 '17 at 15:05
  • 1
    \$\begingroup\$ eclipse raises the code insight with <ctrl><space>, But keep in mind. even if you try to hurry your typing speed is not the limiting factor... \$\endgroup\$ – Timothy Truckle Oct 13 '17 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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