3
\$\begingroup\$

I don't know why in most of the interviews, interviewers are asking this question commonly.

The question is: There are n number of persons standing in a circle. The first person has a gun and he kills the very next person who is alive and hands over the gun to the next person. Who will remain?

Here is my code for the above scenario. It works, if anyone needs to ask.

public static void void main(String ar[]) {

    int numberOfGuys = 10000;
    List<Integer> list = new ArrayList<>();
    for ( int i = 1; i <= numberOfGuys; i++ ) {
        list.add( i );
    }
    boolean isNeighbour = false;

    System.out.println( list );
    Iterator<Integer> i = list.iterator();
    list = new ArrayList<>();
    boolean isTrue = true;
    while ( isTrue ) {
        int k = i.next();
        if ( isNeighbour )
            i.remove();
        else {
            list.add( k );
        }
        if ( !i.hasNext() ) {
            System.out.println( list );
            i = list.iterator();
            if ( list.size() == 1 )
                isTrue = false;
            list = new ArrayList<>();
        }
        isNeighbour = !isNeighbour;
    }
}
\$\endgroup\$
0

4 Answers 4

2
\$\begingroup\$

Style review

  • I think numberOfGuys should be a parameter obtained in the main args, so that you respect the possibility to obtain n from an external source.

  • As pointed in the comments, don't do isTrue = false, that's... weird. True is always true, period. You could rename it hasRemainingGuys or something like that.

Data structure

Using an ArrayList probably isn't the best data structure for your problem. This data structure is fast when it comes to obtaining data, but removing elements from it, which you do a lot, is slower. You'd want a structure where Remove is an \$O(1)\$ operation and, obviously, where it's easy to navigate from one element to the next. The LinkedList sounds like a good idea, as I'll point out below.

Alternative algorithm

I'd recommend creating some sort of circular linked list, so you wouldn't need to recreate the iterator when you reach the end of the list and to simplify some conditions. The idea is to have a linked list, where the last node's "next node" is the first one. This way, your generator could run until there's no next values.

Iterator<Integer> iterator = circularLinkedList.iterator();
//To start with the "first guy"
int k = -1;
while (iterator.hasNext()) {

    //Move on to the next shooter
    k = iterator.next();

    if (!iterator.hasNext()) {
        break;
    }

    //Move to the next shoot...ee?
    iterator.next();
    iterator.remove();
}

And... yeah, that's all. k contains the last guy standing.

Now, you need to implement a circular linked list and create an iterator that works with it. There are many examples on internet on how to do this.

You could also explore an option where you don't actually remove the element from the list, but simply keep a boolean where an index is flagged as dead or not. This might also be faster.

\$\endgroup\$
2
  • \$\begingroup\$ That's still way more complicated than it needs to be. The optimal solution doesn't use any arrays or lists at all; but even if you want to tackle it explicitly rather than mathematically, since each shot reduces the number of people present by 1 there will be n-1 shots fired, so you just need an array of length 2n-1 looped once. \$\endgroup\$ Jun 19, 2019 at 16:40
  • \$\begingroup\$ @PeterTaylor I agree that there're much faster solutions, it's a pretty simple problem, but I wanted to keep an algorithm similar to the one OP posted. \$\endgroup\$
    – IEatBagels
    Jun 19, 2019 at 16:55
2
\$\begingroup\$

I realize that this is old, but I happened to look at it today.

Linear

I would tend to agree with those that say a List and iterator are the wrong tools for this job. You can implement pretty much the same algorithm with a Queue with less code:

public static int findSurvivor(int n) {
    final Queue<Integer> people = new ArrayDeque<>(n);
    for (int i = 0; i < n; i++) {
        people.add(i);
    }

    while (people.size() > 1) {
        // remove the shooter and add back to the end of the list
        people.add(people.remove());
        // remove the victim
        people.remove();
    }

    return people.remove();
}

This is linear in time, as you have to insert each person in the list in the first loop and then remove each person from the list (we also move \$n - 1\$ people to the end of the list).

Logarithmic

As previously noted, it is possible to do better than that. Each time we loop through, we shoot \$\lceil\frac{n}{2}\rceil\$ people, halving the survivors. If \$n\$ is now even, the first person survives. If odd, the first shooter is the last person shot. On the first iteration, 0 is the first person and shoots 1, an interval of 1. The interval doubles in size each iteration. If the first person is not shot, that same person is the first person for the next round. If the first person is shot, the person that the first person handed the gun becomes the next first person. So

public static int findSurvivor(int n) {
    int first = 0;
    int interval = 2;

    while (n > 1) {
        if (n % 2 == 1) {
            // the first person was shot, so update the first person
            first += interval;
        }
        interval *= 2;

        n = (int)Math.floor(n / 2.0);
    }

    return first;
}

This is slightly more code but considerably faster asymptotically. This is \$\mathcal{O}(\log n)\$. I tested it against the first algorithm and it gave the same answer from 1 to 100,000.

Basically we loop until we only have one person left. The interval doubles in size each iteration because half the people get shot. The number of people remaining (n) halves each time.

Concrete example with 10000.

n first interval
10,000 0 1
5000 0 2
2500 0 4
1250 0 8
625 0 16
312 32 32
156 32 64
78 32 128
39 32 256
19 544 512
9 1568 1024
4 3616 2048
2 3616 4096
1 3616 8192

Note that the 10,000, 0, 1 line occurs before the loop starts. Also, the first person changes four times.

My code is zero-indexed, so the 3616 means the 3617th person in the circle.

Constant

We can do even better though. It turns out that there is a constant time solution (assuming that taking the logarithm is a constant time operation). See here.

Porting that to Java gives

public static int findSurvivor(int n) {
    return 2 * n - (1 << (Integer.SIZE - Integer.numberOfLeadingZeros(n)));
}

This gives the same answer as far as I was willing to run the logarithmic solution sequentially: 100,000,000. The linear solution gives the same answer through 100,000. Integer.MAX_VALUE (thirty-two bit) gives a solution of 2,147,483,646 (the last person) under both this and the logarithmic solution. The linear solution can't allocate memory for the queue and throws a "java.lang.OutOfMemoryError: Java heap space" (didn't try to play with Java configuration to see if that was fixable).

Note: this too is zero-indexed, so if you compare to a one-indexed solution, the answers may be off.

\$\endgroup\$
4
  • \$\begingroup\$ I get different results. What am I doing wrong ? Say you start with 5 and 1 has the gun 1 2 3 4 5 -> 3 4 5 1 -> 5 1 3 -> 3 5 -> 3. With 6 it is 1 2 3 4 5 6 -> 3 4 5 6 1 -> 5 6 1 3 -> 1 3 5 -> 5 1 -> 5 \$\endgroup\$ Jul 30, 2022 at 2:04
  • \$\begingroup\$ @RohitGupta Have you adjusted from my zero-indexed values to your one-indexed values? I also get the 3rd from 5 (which is #2 in mine) and the 5th from 6 (which is #4 in mine). I.e. my code will return 2 and 4 to mean the 3rd and 5th respectively. Or my code will return 0 for 8 (or for 1, 2, 4, 16, 32, etc.). \$\endgroup\$
    – mdfst13
    Jul 30, 2022 at 2:14
  • \$\begingroup\$ I am refuting the assumption that the solution is as simple as odd and even. My code is in Delphi and written from scratch. It gives a different result. It has nothing to do with 0 based or 1 based. Use a piece of paper to see. OR I am totally confused. \$\endgroup\$ Jul 30, 2022 at 2:34
  • \$\begingroup\$ I was misunderstanding what you said about odd and even - thinking you meant the end result rather than the first iteration. And when I look at my code using a queue, its almost identical to yours, despite it being in a different language. Therefore upvoting your answer. \$\endgroup\$ Jul 30, 2022 at 4:15
2
\$\begingroup\$

I think the existing reviews are alright, but as it is an interview question, start to seek some intelligence for a solution. Often this will short-circuit evaluation with the use of differences, modulo and so on.

So as a review criticism: take a step back and take a simpler route. Show intelligence.

In a first round of shooting only the even people shoot and survive. The winner is in binary xxxx0.

public int solve(int n) {
    return solve("", n, true);
}

private int solve(String binary, int n, boolean startAt0) {
    if (n == 0 && binary.isEmpty()) {
        return -1;
    }
    if (n <= 1) {
        return Integer.parseInt(binary, 2);
    }
    String digit = startAt0 ? "0" : "1";
    if (n % 2 == 0) {
        return solve(digit + binary, n / 2, startAt0);
    } else {
        return solve(digit + binary, n / 2, !startAt0);
    }
}

I did not test it, but I think this is more impressive. In fact it even requires less thought and coding effort. Even if the result is wrong (I cannot entirely believe it is correct), the logic is persuasive.

Add some comments afterwards (// every second dies.).

If the solution came fast, do:

for (int i = 0; i < 20; ++i) {
    int survivor = solve(i);
    System.out.printf("n = %d, survivor = %d%n", i, survivor);
}
System.out.printf("n = %d, survivor = %d%n", 1000, solve(1000)); // Speed!

You can manually check a solution.

You might even add a dumb solution too, and check against that one in the for loop.

\$\endgroup\$
1
\$\begingroup\$

Bug

This code doesn't compile. That's a really low bar which you should be sure you cross before submitting it for review.

Structure

The main method should at most handle I/O. The calculation should be in a separate method which takes an argument (the number of people in the circle) and returns the solution. There shouldn't be any debug printing.

Looking at the guard on the while loop, I would conclude that you don't know the break keyword. As an interviewer, that would be a red flag unless the job was advertised as open to people who don't know programming on the expectation that the company will train them. (Actually even break is unnecessary: the loop just needs to check the break condition).

Names

isTrue has been mentioned in comments and another answer. isNeighbour also warrants inspection: everyone is a neighbour. What matters is whether the person is a shooter or not.

Code complexity

There's no need to keep discarding list and refilling it.

Refactoring your code, we get down to

public static int josephus2(int numberOfGuys) {
    List<Integer> list = new ArrayList<>();
    for ( int i = 1; i <= numberOfGuys; i++ ) {
        list.add( i );
    }

    boolean isShooter = true;
    Iterator<Integer> i = list.iterator();
    while (list.size() > 1) {
        int k = i.next();
        if ( !isShooter ) i.remove();
        if ( !i.hasNext() ) i = list.iterator();
        isShooter = !isShooter;
    }

    return list.get(0);
}

As mentioned in another answer, LinkedList would be much more efficient for this than ArrayList because of all of the calls to Iterator.remove().

Even this is more complex than an approach which appends to a longer array and does one loop, trading memory for simplicity:

public static void flat(int numberOfGuys) {
    int[] pos = new int[numberOfGuys * 2 - 1];
    for (int i = 0; i < numberOfGuys; i++) pos[i] = i + 1;
    for (int shot = 0; shot < numberOfGuys - 1; shot++)
    {
        // Person at position 2*shot shoots person at position 2*shot+1 and goes to end of queue
        pos[numberOfGuys + shot] = pos[2 * shot];
    }
    return pos[numberOfGuys * 2 - 2];
}

Algorithmic complexity

These approaches loop once per shot, and there are \$n - 1\$ shots fired, so it takes \$O(n)\$ time and space. It's possible to solve the problem in \$O(\lg n)\$ time by thinking about who survives an entire turn round the circle.

  • If there's only one person, they survive.
  • If there's an even number of people, those in odd positions (one-indexed) survive and it's person 1's turn to shoot again.
  • If there's an odd number of people, those in odd positions (one-indexed) survive and it's person \$n\$'s turn to shoot.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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