Last men standing – code

The “Last man standing” is also called “Josephus 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 index starts from 1 (not 0). Then use two pointers prev and p to keep track previous and current node. A while loop is used to remove every kth node until the last one remained.

The following question is a little twist, find Last man standing and second to last man 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, JavaScrit and Python.


last man standing

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

JavaScript

Python

Doodle

last two men standing doodle

Output:
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.java
Java Coding Interview Pocket Book (2nd Edition)
Josephus problem solution using recursion

Comments are closed