5
\$\begingroup\$

I am working on a survivor problem:

Complete Question Text: Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from One to One Hundred.

At some point in time, the person in chair #1 will be told to leave the room. The person in chair #2 will be skipped, and the person in chair #3 will be told to leave. Next to go is person in chair #6. In other words, 1 person will be skipped initially, and then 2, 3, 4.. and so on. This pattern of skipping will keep going around the circle until there is only one person remaining.. the survivor. Note that the chair is removed when the person leaves the room.

Write a program to figure out which chair the survivor is sitting in.

Below is the code I have:

public class ChairProblem {

    public static void main(String[] args) {
        System.out.println(getSurvivors(100));
    }

    private static int getSurvivors(int numChairs) {
        if (numChairs < 1) {
            return -1;
        }

        // populate chair array list
        ArrayList<Integer> chairs = new ArrayList<Integer>();
        for (int i = 0; i < numChairs; i++) {
            chairs.add(i + 1);
        }

        // removing all but one elements
        int indexOfChair = 0;
        int count = 1;
        while (chairs.size() > 1) {
            chairs.remove(indexOfChair);
            indexOfChair += count;// skip the count number of chairs
            count++; //increase the number of chairs to skip by 1
            indexOfChair %= chairs.size();// loop to beginning if necessary
        }

        return chairs.get(0);
    }
}

How can this be improved? I was asked this question in an interview and I gave this answer, but I'm not sure whether this can be improved in terms of complexity or Java Docs as well.

\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview. I hope you get some fine answers. \$\endgroup\$ – Legato Apr 28 '15 at 3:23
  • 1
    \$\begingroup\$ How much have you tested this code? Are you sure it is correct? \$\endgroup\$ – Simon Forsberg Apr 28 '15 at 9:12
  • \$\begingroup\$ Slightly offtopic: It is the well known josephus problem en.wikipedia.org/wiki/Josephus_problem but not as lethal \$\endgroup\$ – Thomas Junk Apr 30 '15 at 13:55
  • \$\begingroup\$ @ThomasJunk (definitely not off-topic) It is a variant of the Josephus problem indeed, but with a much more varying amount of skips. Additionally, in this case the first person is always the first to go, which is not the common version in the Josephus problem. \$\endgroup\$ – Simon Forsberg Apr 30 '15 at 14:03
7
\$\begingroup\$

Basics

In Java, since version 7, there is no need to specify the generic type of a generic class on the right-hand side of the initializer. Instead, you can use the "diamond operator". The following:

    ArrayList<Integer> chairs = new ArrayList<Integer>();

should be:

    ArrayList<Integer> chairs = new ArrayList<>();

Additionally, unless you have a specific need, you should use the highest level of abstraction that's useful for your variables. There is no need to declare chairs as an ArrayList, when a List would be fine:

    List<Integer> chairs = new ArrayList<>();

Data Types

Here you have used an ArrayList, but this is a bad choice. Performance in ArrayLists is poor when you add or remove items from the middle of the list. A LinkedList is generally better for that type of operation.

Alternate solution

A linked list is a great option for this problem, because it can be made to behave like a circle. What we do, is start with a populated list, and then "walk the list". We remove the first member, then take the next member, and move them to the end of the list. Then we remove the third member, and the 4th and 5th survive and go to the end. Note that the first, second, and third survivors (chair 2, 4, and 5) are now next to each other at the end.... (after chair 100).

Note that for every member we remove from the list, we add a bunch of survivors to the end. By doing some modulo arithmetic, the amount we shift to the end can be controlled to the size of the remaining members.

We repeat the process until the list is size() == 1

private static int getSurvivorsLL(final int numChairs) {
    Deque<Integer> chairs = new LinkedList<>();
    while (chairs.size() < numChairs) {
        chairs.add(chairs.size() + 1);
    }
    int skip = 0;
    while (chairs.size() > 1) {
        System.out.println("Eliminated " + chairs.removeFirst());
        skip++;
        int shift = skip % chairs.size();
        for (int i = 0; i < shift; i++) {
            chairs.addLast(chairs.removeFirst());
        }
    }
    return chairs.removeFirst().intValue();
}

Note that, because I need the removeFirst() method, I use the Deque personality for the LinkedList.

Update - Neat, Custom, or Fast

This question got me thinking, for both good, and bad reasons. I initially misread the question, and gave a broken answer. Then I "improved" my alternative suggestion to be a more natural language fit than an ArrayList (which does not have O(1) "remove" time).

Unfortunately, for me, I then ran a benchmark against my code, and the OP's code. My code lost, even though the LinkedList is a more natural fit for this problem. It just makes sense that the LinkedList should be faster... all we are doing is shuffling items one-at-a-time to the end of the list. and there's only one item moved each turn. So, why was it slow? To put things in perspective, here are the times of the OP's code:

Task Chairs -> OP: (Unit: MICROSECONDS)
  Count    :   1000000      Average  :    2.3310
  Fastest  :    1.9730      Slowest  : 1878.1240
  95Pctile :    2.7630      99Pctile :    3.9480
  TimeBlock : 2.506 2.323 2.245 2.479 2.268 2.262 2.265 2.262 2.386 2.319
  Histogram : 981012 14462  4176   229    97    13     5     3     1     2

It computes the solution for 100 chairs in under 2 microseconds. But the time for the LinkedList solution I propose is:

Task Chairs -> LL: (Unit: MICROSECONDS)
  Count    :    182906      Average  :   16.4010
  Fastest  :   13.8150      Slowest  : 2252.3280
  95Pctile :   23.6840      99Pctile :   30.7890
  TimeBlock : 20.028 16.870 18.086 16.485 15.615 15.323 15.411 15.385 15.399 15.417
  Histogram : 179027  3537   253    52    15     2    16     4

where the fastest time is in about 14 mircoseconds - 7 times slower than the OP code, even though it in theory does less work!.

Right, so, what would make the code faster? First up, I designed a custom node class that would be simpler than a full Linked List. Here is the code:

private static final class Chair {
    private final int id;
    private Chair next = null;

    public Chair(int id) {
        this.id = id;
    }

}

private static int getSurvivorsCL(final int numChairs) {
    Chair previous = buildCircle(numChairs);
    int size = numChairs;
    while (size > 1) {
        Chair togo = previous.next;
        previous.next = togo.next;
        togo.next = null;
        size--;
        int shift = (numChairs - size) % size;
        while (shift-- > 0) {
            previous = previous.next;
        }
    }
    return previous.id;
}

private static Chair buildCircle(int numChairs) {
    final Chair last = new Chair(numChairs);
    Chair tmp = last;
    while (--numChairs > 0) {
        Chair c = new Chair(numChairs);
        c.next = tmp;
        tmp = c;
    }
    last.next = tmp;
    return last;
}

The above code is a 'clean' version of what I would expect the circular chair arrangement to accomplish. What is the time for that?

Task Chairs -> CL: (Unit: MICROSECONDS)
  Count    :     943355      Average  :     3.1800
  Fastest  :     2.3680      Slowest  : 34884.2530
  95Pctile :     3.5520      99Pctile :     3.9480
  TimeBlock : 3.243 3.098 3.068 3.160 3.478 3.202 3.241 3.047 3.127 3.137
  Histogram : 936200  2336  4519   169    84    29     3     1     2     4     4     2     1     1

This is 4 times faster than the LinkedList, but, it is still 50% slower than the OP's code? The 4-times faster than LinkedList is impressive, but there's still something that does not make sense to me.... it should be faster than ArrayList.

So, to experiment, I used an even simpler approach of a static array, where none of the data is moved at all. The only thing updated is a "pointer" to the next chair. In other words, the index in the array is essentially the chair number, and the value in the array is the "next" chair. This way we can create a logical circle, and just change a pointer each time a chair is removed. Here is the code:

private static int getSurvivorsAN(final int numChairs) {
    int[] chairs = new int[numChairs];
    for (int i = 1; i <= numChairs; i++) {
        chairs[i - 1] = i % numChairs;
    }
    int current = numChairs - 1;
    int skip = 0;
    int size = numChairs;
    while (current != chairs[current]) {
        int remove = chairs[current];
        chairs[current] = chairs[remove];
        size--;
        skip++;
        int loopskip = skip % size;
        while (--loopskip >= 0) {
            current = chairs[current];
        }
    }
    // chairs are 0-based, we need to return 1-based, so add 1.
    return current + 1;
}

How fast was that?

Task Chairs -> AN: (Unit: MICROSECONDS)
  Count    :     939602      Average  :     3.1920
  Fastest  :     2.7620      Slowest  : 18780.0630
  95Pctile :     3.5530      99Pctile :     3.9470
  TimeBlock : 3.271 3.145 3.127 3.181 3.195 3.141 3.140 3.152 3.175 3.401
  Histogram : 934304   761  4360   114    47     9     3     2     0     1     0     0     1

About the same as the Chair node version above... but, still slower than the OP.

So, how to beat the OP? Well, it must boil down to the fact that a System.arrayCopy() of all the "remaining" chairs in the circle (what should be an O(n) operation, where n is the size of the List, is more efficient than looping over each value in the skip. So, for example, on the first iteration, we remove chair 1, it must mean that copying every other chair "back one spot" is faster than just moving 1 chair to the end. To test this, I made an efficient version of ArrayList (i.e. using primitives, not Integer). Here's the code:

private static int getSurvivorsAS(final int numChairs) {
    int[] chairs = new int[numChairs];
    for (int i = 0; i < numChairs; i++) {
        chairs[i] = i + 1;
    }

    int remove = 0;
    int skip = 0;
    int size = numChairs;
    while (size > 1) {
        size--;
        System.arraycopy(chairs, remove + 1, chairs, remove, size - remove);
        chairs[size] = 0;
        skip++;
        remove = (remove + skip) % size; 
    }
    return chairs[0];
}

How does this compare?

Task Chairs -> AS: (Unit: MICROSECONDS)
  Count    :   1000000      Average  :    1.6140
  Fastest  :    1.1840      Slowest  : 1699.3120
  95Pctile :    1.9740      99Pctile :    2.3690
  TimeBlock : 1.653 1.614 1.573 1.689 1.593 1.591 1.592 1.583 1.650 1.606
  Histogram : 970982 26003   384  2495    78    35    17     4     1     0     1

So, what does this all mean?

Well, it means that System.arraycopy() is fast. How do things scale, though?

Here are the scaling charts for three of the code blocks, the OP code, the best Circular List code (with the Chair node), and the ArrayShift code.

All three have a O(n^2) type complexity, so it all washes out, essentially. Note that the array-shift code is fastest for all tested scales (all the way up to more than 100,000 chairs.

Conclusion

The OP's code is better than I expected in terms of performance. The LinkedList code is worse than I expected. The best code from a readability perspective is, I think, the LinkedList code. It best represents the actual problem.

The best code from a performance perspective is a primitive array-of-int which you shift using System.arrayCopy() in order to remove chairs.

\$\endgroup\$
  • \$\begingroup\$ Note to all interested - I significantly updated this answer with performance metrics on multiple different solutions to the problem. My original suggested solutions was not the most efficient... \$\endgroup\$ – rolfl Apr 30 '15 at 13:06
  • \$\begingroup\$ @rofl Would be cool, if your could benchmark my answer in the same environment. I think a primitive array without any copying could be a lot faster. \$\endgroup\$ – Falco Nov 9 '18 at 11:53
  • \$\begingroup\$ You keep on saying that some thing should be faster when it is not faster. Bringing morality into it plainly does not help. You are forgetting two things: (1) asymptotic performance is not relevant if n is small; for small n all problems are O(1) and (2) cache locality dominates most performance problems on in-memory data. Always choose data structures that have good cache locality if you are keen on performance. \$\endgroup\$ – Eric Lippert Nov 9 '18 at 22:28
3
\$\begingroup\$

I think this is an excellent example of a bad instinct in optimization. People like focusing on code, instead of trying to optimize the core algorithm.

In broad strokes, what is your algorithm? It's to create a list of 100 items, and then loop around and delete them one at a time. Same with a lot of the other answers here - it involves dealing with those 100 entries somehow.

Okay, but is there any other way to do this?

Well, picture in your head what happens the first loop around the 100 chairs. You eliminate 1, 3, 5, 7, ... etc. Basically, you're left with a series of even numbered chairs. So when you begin 'Round 2', you're really selecting through 50 numbers - all the evens 2-100. Is the 'answer' to that any different than the answer to 2 x getSurvivors(50)? After all, there's no difference between (2,4,6...100) and 2 x (1,2,3...50).

So at bare minimum, we could do reduce our chair number down until it's odd:

private static int getSurvivors(int numChairs) {
    if (numChairs % 2 == 0) return 2 * getSurvivors(numChairs/2);
    // rest of code goes here
}

So we go from having to create a list of 100 entries and remove 99 of them, to creating a list of 25 entries and removing 24 of them. Much Better!

But... is there any way we could improve it for odd cases as well?

If we've got 101 chairs, we're eliminating all the odds, ending up with 2-100... with one big caveat: we have to skip the first entry next go-around.

Which expands our function into four main cases:

  • We've got an even number of chairs, and we're eliminating the first
  • We've got an even number of chairs, and we're skipping the first (new!)
  • We've got an odd number of chairs, and we're eliminating the first
  • We've got an odd number of chairs, and we're skipping the first

Fortunately, none of the cases are too hard to chart out. So we could use code that looks like this:

    private int getSurvivor(int nums, bool eliminateFirst)
    {
        if (nums < 1) return -1;
        if (nums == 1) return 1;
        if (nums == 2) return (eliminateFirst ? 2 : 1);
        if (nums % 2 == 0)
        {
            if (eliminateFirst) return 2 * getSurvivor(nums / 2, eliminateFirst);
            return 2 * getSurvivor(nums / 2, eliminateFirst) - 1;
        }
        if (eliminateFirst)
            return 2 * getSurvivor((nums - 1) / 2, !eliminateFirst);
        else
            return 2 * getSurvivor((nums + 1) / 2, !eliminateFirst) - 1;
    }

Look at that - no lists, no removals, just a recursive function that is called log2(N) times (for 100 chairs, ~7 times.) Best of all, it's scaleable - the original code will take a lot longer for 1,000,000 chairs; this will run nearly as quickly - multiplying the number of chairs by 1000 will only add 10 more recursive calls.

Now we can focus on code tweaks and optimizations ( (num & 1) instead of num % 2, >> 1 instead of /2, etc).

\$\endgroup\$
  • \$\begingroup\$ This is the far superior solution. I would caution against attempting "optimizations" of turning math into bit twiddling; let the jitter's optimizer figure that out and generate the code. And this algorithm is plenty fast enough already. \$\endgroup\$ – Eric Lippert Nov 9 '18 at 22:42
  • 1
    \$\begingroup\$ Completely agreed, @EricLippert. I can't imagine having to add those optimizations in the last paragraph in any sort of real-world setting; the lack-of-readability alone would likely make it not worth it. :-) \$\endgroup\$ – Kevin Nov 9 '18 at 22:59
2
\$\begingroup\$

Since @rolfl tried to get a very efficient solution, I think fastest is probably a primitive int array:

public class SurvivorChallenge {
public static void main(String[] args) {
    final int chairCount = 100;
    final int lastChair = chairCount - 1;

    // Each chair saves index of next filled chair
    int[] chairs = new int[chairCount];
    for(int i=0; i < lastChair; ++i) {
        chairs[i] = i + 1;
    }
    // This creates a closed ring of chair-indices
    chairs[lastChair] = 0;

    int currentChairIndex = lastChair;
    int skipCount = 0; // We will remove the first chair first

    for(int chairsLeft=chairCount; chairsLeft > 1; --chairsLeft) {
        // Follow linked Indices in Chair list until skipCount
        int previousChairIndex = currentChairIndex;
        for (int i=0; i < skipCount + 1; ++i) {
            previousChairIndex = currentChairIndex;
            currentChairIndex = chairs[currentChairIndex];
        }

        // Let the previous Chair point to the following Chair
        // Thus removing the current Chair from the Ring
        chairs[previousChairIndex] = chairs[currentChairIndex];
        ++skipCount;
    }

    // Normalize Result cause Chairs start at 1 and Arrays at 0
    System.out.println("Result Chair Nr: " + (chairs[currentChairIndex]+1));
}
}

We don't need to copy arrays or create/destroy complex objects. We can use the array to store the index of the next node and just update these index values, ignoring removed entries. This will behave like a Java Linked list, but without Garbage-Collection and with continuous reads in a compact memory range.

\$\endgroup\$
  • \$\begingroup\$ Hey Falco. The logic looks sound, and it will likely beat the performance of the linked list. Having said that, not too long after I wrote my answer, I encountered the "simple" formulaic solution to this, see my answer here: codereview.stackexchange.com/a/104658/31503 - It would take me some time to re-establish an environment with my microbench code.... but feel free to download it yourself and try it: github.com/rolfl/MicroBench \$\endgroup\$ – rolfl Nov 9 '18 at 13:21
1
\$\begingroup\$

Almost another question than an answer, but looking at this question (and related/similar ones) it struck me that rather than removing items from a list we can start with an array of booleans mark them as used until we have only one survivor.

The problem, in my mind, is comparing performance. Without setting up some performance tests (not sure if that is even possible in IdeOne) I am unsure which is better. Any thoughts out there?

public static void main (String[] args) throws java.lang.Exception {
    int count = 100;
    System.out.println("For " + Integer.toString(count) + 
                       " chairs, the surivor = " + findSurvivor(count));
}

private static class Location{
    private int _slotNumber;
    public Location(int slotNumber){
        _slotNumber= slotNumber;
    }
    public int getSlotNumber(){
        return _slotNumber;
    }
    public void setSlotNumber(int value){
        _slotNumber = value;
    }
}

private static int findSurvivor(int count){
    boolean[] allChairs = new boolean[count];
    Location current = new Location(0);
    while(true){
        if (!findNextUsedChair(allChairs, current)) break;
        allChairs[current.getSlotNumber()] = true;
        if (!findNextUsedChair(allChairs, current)) break;
    }
    return current.getSlotNumber();
}

private static boolean findNextUsedChair(boolean[] chairs,
                                         Location location){
    int startPos = location.getSlotNumber();
    int curPos = startPos;
    do {
        curPos = (curPos + 1) % chairs.length;
        if(!chairs[curPos] || (curPos == startPos)) break;
    }while(true);

    location.setSlotNumber(curPos);
    return curPos != startPos;
}
\$\endgroup\$

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.