2
\$\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\$
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 form 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\$
  • \$\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\$ – Peter Taylor Jun 19 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 at 16:55
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\$
0
\$\begingroup\$

This problem is famously called the "Josephus Problem", read up on google.

Does the interview question specifically ask you to write code representing the given situation? Because there is a simpler way to get the person who will remain, by doing some paperwork before writing a simple mathematical equation.

By tabulating n and k upto a small number like 6 or 8, it's easy to observe that when n is a power of 2, the person with k = 1 wins. Between powers of two, k equals successive odd numbers. That is, when n is one more than a power of 2, 3 wins. When n is two more than a power of two, 5 wins.

It can be inferred that when n is of the form 2M + q , the (q+1)th odd number wins. Since every odd number is of the form 2X - 1, the desired winner is k = 2(q+1) - 1 => k = 2q + 1 ....... (1)

Since n is of the form 2M + q, we can solve for q in terms of n as, q = n - 2floor(log2 n )

So the code will simply be the mathematical statement (1) above, written in language of choice.

\$\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.