Coding problems and simulations can be a formidable tool in determining the quality of software developer candidates.  Recently, we have retired several of our greatest hits that do this. The Josephus question is one of those. It is well documented and discussed on the internet.  In fact, this question has helped us at FloCareer to close hundreds of positions by helping assess candidate viability and recommended next steps. High achievers on Josephus have gone on to be hired for roles as Senior Developers, Java Developer, Python Developer, for example.

Our Philosophy

We tend to add questions in our question bank that are not purely based on computer science concepts concerning data structures and algorithms etc., but that pose a real life scenario to our candidates.  That assesses a candidates' ability to comprehend a real life problem statement and then translate it into programming requirements and ultimately a solution.  While you can find many programming questions which can be more difficult and directly test candidates' data structure and/or algorithm knowledge, what businesses find more relevant is candidates' ability to model a real life problem statement into a programming question and pursue the answer. 

Our approach is that questions have a significant impact on the overall candidate experience and that an interview should be a fun learning experience.  There is a distinct advantage to combining technology with the human touch. When people leave the table from  a FloCareer interview, they have ideas to ponder. As a result, we provide a positive candidate experience.

"The interviewer has a very good manner. I liked very much his way of talking, asking questions and suggestions at the end of the interview. I need to improve my knowledge and I learnt some knowledge through this interview. Thanks to the Flocareer team". - Sridhar H.

 Questions like Josephus are incorporated into the interview structure that helps drive the interview in our Interview as A Service Platform. The specifics of the problem and the recommended solution are below.

Description:

There was a group of 41 Jewish soldiers surrounded by Roman army, and they didn't want to get caught. So, they sat down in a circle and came up with an algorithm. Everybody had a sword, and starting from person #1 in the circle, everybody will kill the next living person on the left. So, #1 will kill #2. #3 will kill #4, #5 will kill #6 and so on. The last living person will have to commit suicide to avoid getting caught by Romans.

The soldier called Josephus preferred to be caught over committing suicide. So, in the group of 41 soldiers, he chose the location where he will be the last person living.

Question:

Write a program to figure out, in a group of given N people, where should Josephus sit to live at the end of all internal killing.

There is a mathematical solution to this problem (check out www.youtube.com/watch?v=uCsD3ZGzMgE). But, your program should use the brut force method to find the position. The output of the program may look like this:

Solving Josephus problem for 5 soldiers:
1 kills 2
3 kills 4
5 kills 1
3 kills 5
Josephus should sit on position# 3

At FloCareer, we grade each candidate answer on a scale of 1 (worst) to 5 (ideal) stars.

Ideal Answer (5 Star)
Solution approach:
- Create an array or list of given N integers for N positions
- Initialize with all 1's. 1 on position k simulates that soldier at position k is living; 0 denotes dead soldier.
- Now, in loop, simulate soldier killing immediate next living soldier.

Here's the Python code for the same:

'''
Josephus' Problem
'''

def incr_num(n, size):
n += 1
if n == size:
n = 0
return n

solds = []
num_solds = int(input("Total number of soldiers > "))
for i in range(num_solds):
solds.append(1)

# Now we have an array of solders, 1 means he's living, 0 means dead
nobody_to_kill = False
pos = 0
nxt = 1

while not nobody_to_kill:
goto_nxt = False
nxt = incr_num(pos, num_solds)
# Find next living sold to kill
while pos != nxt and goto_nxt == False:
if solds[nxt] == 1:
print("%d kills %d" % (pos+1, nxt+1))
solds[nxt] = 0
goto_nxt = True
else:
nxt = incr_num(nxt, num_solds)

# If we are here, we have found a living sold and killed him, OR
# there is nobody to kill
if pos == nxt:
nobody_to_kill = True
print("WINNER IS: ", pos+1)
else:
pos = incr_num(pos, num_solds)
while solds[pos] == 0:
pos = incr_num(pos, num_solds)

At FloCareer coding questions like this one are an integral part of our interview structure.  We integrate both the technical questions and coding assessment right in the Interview as A Service Platform. At the conclusion of the interview, our FloExperts send a detailed recommendation with a feedback report and video clips of the interview for your review. We will miss Josephus as it has been a great soldier in helping us to assess candidates and win the war for talent.  However, we are confident that the new question reinforcements will be just as impactful in talent assessment.