Mr. Muffin's ball-passing game

Question

I have an assignment to solve this problem. There are a total of 18 test case files, 5 of which I have failed due to exceeding some time limit on the script and I am unable to verify if there are any logic errors thereafter.

Question Description

Mr. Muffin is an orientation group leader and sets up a simple ice breaking game. N students initially sit in a circle with one of them holding a ball. Every time Mr. Muffin shouts “NEXT”, the student holding the ball passes it to the next student clockwise. The student that receives the ball will have to shout their name.

Occasionally, the student holding the ball might want to “LEAVE” the circle (going to the toilet for example). In that case, the student will pass the ball to the next student clockwise in the circle and leave. The student receiving the ball will shout their name as well.

New students might also arrive and want to “JOIN” the circle. In this case, the new student will sit at the position such that they will be the next student to receive the ball. The ball will then be immediately passed to the new student and the new student will have shout their name.

As the number of students increases, Mr. Muffin finds it very difficult to keep track of all the students and their names. Thus, given the list of events that happen (either NEXT, LEAVE or JOIN), he wants you to code a program to tell him what name will be shouted at each time.

Even though the students are sitting in a circle which is non-linear, Rar the Cat suggests that clever usage of Java API Linear Data Structures would be sufficient to solve this task. (i.e. You do not need to implement your own data structure for this task.)

Input

The first line contains a single integer N, the number of students initially in the circle.

The second line contains N strings, representing the names of the students in the circle in a clockwise manner. The first name in the list is the name of the student currently holding the ball.

The third line contains a single integer Q, the number of events that happen.

The next Q lines represent the events that happen in chronological order. The first string of each line will either be NEXT, LEAVE or JOIN, representing the event. If the event is JOIN, then that line will contain a second string representing the name of the student that joined.

Output

The output should contain Q lines, representing the names that are shouted in the order of the events.

Limits

• 3≤N,Q≤200,000

• It is guaranteed that every student’s name will consist of only English letters and be at most 10 characters long. However, the names of students might not be distinct. For instance, there can be more than 1 student with the name ‘Bob’.

• It is also guaranteed that there will be at least 3 people in the circle at any point in time.

Sample input

3
Alice Bob Charlie
4
NEXT
JOIN Donald
NEXT
LEAVE

Sample output

Bob
Donald
Charlie
Alice

Does anyone have a solution to my problem? Do inform me if any more information is needed.

import java.util.*;

public class Ballpassing {
    private void run() {
        //implement your "main" method here
        LinkedList<String> lst = new LinkedList<>();
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        for (int i = 0; i < length; i++) {
            String name = sc.next();
            lst.add(name);
        }
        int idx = 0;
        int count = sc.nextInt();
        for (int i = 0; i < count; i++) {
            int nextIdx = (idx + 1)%lst.size();
            String cmd = sc.next();
            //handles the case where going to the head of the list is required, by moving the list rightwards    
            if (nextIdx == 0) {
                LinkedList<String> shifted = (LinkedList<String>) lst.clone();
                String element = shifted.getLast();
                shifted.remove(idx);
                shifted.addFirst(element);
                idx = 0;
                nextIdx = 1;
                lst = shifted;

            }

            if (cmd.equals("LEAVE")) {
                System.out.println(lst.get(nextIdx));
                lst.remove(idx);
                continue;
            } else if (cmd.equals("JOIN")) {
                String name = sc.next();
                lst.add(nextIdx,name);
            }
            idx = nextIdx;
            System.out.println(lst.get(idx));
        }


    }

    public static void main(String[] args) {
        Ballpassing newBallpassing = new Ballpassing();
        newBallpassing.run();
    }
}

Answer 1

Re-thinking the problem & re-working your code (unfortunately I have only the basic test case), please see following solution (comments inline):

...
  private void run() {
    // back to LinkedList, since it *is* the "perfect" data structure for this problem/game.
    final LinkedList<String> lst = new LinkedList<>();
    final Scanner sc = new Scanner(System.in);
    final int length = sc.nextInt();
    for (int i = 0; i < length; i++) {
        lst.add(sc.next());
    }
    final int count = sc.nextInt();
    // and we use it via ListIterator, it supports constant time next()(, previous()), remove() and add() operations.
    // ...arrayList offers the same functionality but with more "arraycopy".
    ListIterator<String> it = lst.listIterator();
    // Initialize with (/skip) "Alice" 
    it.next();
    for (int i = 0; i < count; i++) { // <- O(count)
        // command
        final String cmd = sc.next(); // <- O(1)
        // switch (with strings since java7)
        switch (cmd) { // <- O(1)
            case "JOIN": {// join:
                // add "before current next()"
                it.add(sc.next()); // <- O(1)
                // ... and set iterator to "correct" position.
                it.previous();// == name // <- O(1)
                break;
            }
            case "LEAVE": { // leave:
                // remove current player (iterator at correct position)
                it.remove(); // <- O(1)
                break;
            }
            case "NEXT": { // next: (do nothing special, iterator at correct position)
                break;
            }
            default: {
                // throw illegal argument exception...
                break;
            }
        } // end-switch(cmd)
        // checkoverflow
        it = checkOverflow(it, lst); // <- O(1)
        // print next & iterate
        System.out.println(it.next()); // <- O(1)
    } // end-for
  } // end-run()

  /* utility function: resets iterator, when it reached the end of list (!hasNext()) */
  private static ListIterator<String> checkOverflow(ListIterator<String> it, LinkedList<String> lst) {
    return it.hasNext() ? it : lst.listIterator(); // <- O(1)
  }

see: https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html

---

Sure, welcome! :) ...

As we found (in my intial/quick answer), the O(n) complexities were our bottlenecks (to pass the hard test cases).

We need a data structure wich supports the most efficient:

• NEXT (iterate/next())
• JOIN (at current position/add())
• and LEAVE (at current position/remove())

... operations. Looking around (all of the known data structures), all these operations can be accomplished by a "(doubly) linked list iterator" in O(1) (constant) time, which made me comment:

it is the "perfect" data structure for this problem/game.

(until "Q(uantum)List" is found ... :)) (due to my usage to & convenience to java.util.Iterator ... I was blinded and forgot about java.util.ListIterator! ... and the "fine advantages" of its usage (Iterator is the parent/lighter interface))

And this enables us to accomplish the task in O(Q) (Q <= 200,000) steps, without actually ever "enumerating the whole list".

The rest is no rocket science (hopefully):

• final keywords on "final variables".
• save lines/vars (String name = sc.next(), ... , but also DS gives us "new access").
• in intial it.next(); we skip "Alice", as implied by the "expected output".
• each "command iteration" is started by final String cmd = sc.next();
• switch(cmd) case ...
  • in case of JOIN we (it.add() &) have to reset the cursor/iterator back for one position (it.previous();). (In terms of the game and "main iteration")
  • in case of LEAVE it.remove() leaves the cursor in correct position (in terms of the game and "main iteration").
• checkOverflow before ...
• the "main iteration" ("throw ball action" = NEXT ...but also on JOIN and LEAVE = it.next()) happens as last statement of each "command iteration" ...squeezed into System.out.println(it.next()).

I think that's it.

Answer 2

The obvious amount of time/complexity (and memory) you "waste" is here:

 if (nextIdx == 0) {
     // clone a 200k element list, Thanks a lot! :)
     LinkedList<String> shifted = (LinkedList<String>) lst.clone();// <- O(lst.size())!
     String element = shifted.getLast();// <- O(1)
     shifted.remove(idx);// <- O(1) <- wrong, O(n) <- correct
     shifted.addFirst(element);// <- O(1)
     idx = 0;// <- O(1)
     nextIdx = 1;// <- O(1)
     lst = shifted;// <- O(1)
 }

...since this code is equivalent, but with "quadratic" complexity (and linear memory) savings:

if (nextIdx == 0) {
    String tmp = lst.getLast();// <- O(1)
    lst.remove(idx);// <- O(1) <- wrong, O(n) <- correct
    lst.addFirst(tmp);// <- O(1)
    idx = 0;// <- O(1)
    nextIdx = 1;// <- O(1)
}

..welcome & well done so far!

---

Thanks for the feedback! The only bottlenecks I see left are:

• LinkedList.get(int idx) (this is also O(lst.size()/2))

• Scanner is not the best choice for "big data"/performance. (and N=200k is "not really big")

• System.out.print slows things down, but I fear we can't change this.

---

Please "try" (to pass the assignment):

ArrayList<String> lst = new ArrayList<>();
... // with :
       if (nextIdx == 0) { // --> idx == lst.size() - 1
            String tmp = lst.remove(idx);
            lst.add(0, tmp);
            idx = 0;
            nextIdx = 1;
        }
...

see:

• http://www.javacreed.com/comparing-the-performance-of-various-list-implementations/ (LinkedList.get is horrible!)
• https://stackoverflow.com/q/3830694/592355