Last men standing using circular linked list

The “Last man standing” is also called “Josephus problem” or “circle of death problem”. Given a number n people standing in a circle, eliminate every kth one until the last one remain. This problem can be solved with circular linked list. First, we build a circular Linked List by adding n nodes. The number starts from 1 (not 0). Use two pointers prev and p to keep track previous and current node. Then a while loop is used to remove every kth node until the last man remaining.

We can extend the solution to find last two men standing. We declare a variable left to check whether there are two left. If there are two left, return the prev‘s data which is the second to last. The implementation is in Java, JavaScript and Python.

last man standing

Amazon Interview Question:
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





last two men standing doodle

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)

Download LastMenStanding.js
Java Coding Interview Pocket Book

Comments are closed