Last man standing with Circular Linked List – Code

The “Last man standing” is also called “Josephus problem”. Give a number n people standing in a circle, eliminate every kth one until the last one remain.

We usually circular linked list to solve Josephus problem. First, we build a Circular Linked List by adding n nodes. Then use a while loop to remove the kth node until only one left.

Please note in this particular question the k is 2. We need to find the last two men alive in stead of last man.

Amazon Interview Question (CareerCup):
Last Man Standing: A king gathers all the men in the kingdom who are to be put to death for their crimes, but because of his mercy, he will pardon one. He gathers the men into a circle and gives the sword to one man. The man kills the man to his left, and gives the sword to the man to the dead man’s left. The last man alive is pardoned.
With 5 men, the 3rd is the last man alive.
Write a program that accepts a single parameter: a number N that represents the number of criminals to start with. The program should output the number of the last two men alive.
Example #1: myProgram 5
would output:
5, 3
Example #2: myProgram 7
would output:
3, 7

Java Code:

With 5 men, the last two standing are:
Second to last: 5, last: 3

With 7 men, the last two standing are:
Second to last: 3, last: 7

O Notation:
Time complexity: O(n)
Space complexity: O(n)

Action items:
The complete list of coding interview questions
Josephus problem solution using recursion

Comments are closed