Bloomberg面经准备: Josephus problem

Given a circular single linked list.Write a program that deletes every kth node until only one node is left. 
After kth node is deleted, start the procedure from (k+1)th node. 
e.g.list is 1->2->3->4->5->1 
k=3 
1. You are at 1, delete 3. 
List is: 1->2->4->5->1 
2. You are at 4, delete 1 
List is: 2->4->5->2 
3. You are at 2,delete 5 
List is: 2->4->2 
4. You are at 2, delete 2 
List is: 4 
Return 4. 

How efficient you can do it?

Solution 1: Math

Let f(n,k) denote the position of the survivor. After the kth person is killed, we're left with a circle of n-1, and we start the next count with the person whose number in the original problem was (k mod n)+1. The position of the survivor in the remaining circle would be f(n-1,k), if we start counting at 1; shifting this to account for the fact that we're starting at (k mod n)+1 yields the recurrence

f(n, k) = ((f(n-1, k) + k - 1) mod n) + 1,

f(1, k) = 1

这样理解：

新数组len = n-1，其中1th num在原数组的位置是 (k mod n)+1, 也就是 (1 + (k-1))mod n+ 1

2nd num 在原数组位置是（2 + （k-1））mod n + 1

3rd num 在原数组位置是（3 + （k-1））mod n + 1

After the first person (kth from begining) is killed, n-1 persons are left. So we call josephus(n – 1, k) to get the position with n-1 persons. But the position returned by josephus(n – 1, k) will consider the position starting from k%n + 1. So, we must make adjustments to the position returned by josephus(n – 1, k).

Following is simple recursive implementation of the Josephus problem. The implementation simply follows the recursive structure mentioned above.

Time Complexity, O(N), DP

 1 #include <stdio.h>
 2  
 3 int josephus(int n, int k)
 4 {
 5   if (n == 1)
 6     return 1;
 7   else
 8     /* The position returned by josephus(n - 1, k) is adjusted because the
 9        recursive call josephus(n - 1, k) considers the original position 
10        k%n + 1 as position 1 */
11     return (josephus(n - 1, k) + k-1) % n + 1;
12 }
13  
14 // Driver Program to test above function
15 int main()
16 {
17   int n = 14;
18   int k = 2;
19   printf("The chosen place is %d", josephus(n, k));
20   return 0;
21 }

Solution 2: Simulate the process

Singly LinkedList

先扫一遍，确定有环，并且找到head上一跳节点，然后loop直到head.next == head

 1 package bloomberg;
 2 
 3 public class Josephus {
 4     public class ListNode {
 5         ListNode next;
 6         int val;
 7         public ListNode(int val) {
 8             this.val = val;
 9             this.next = null;
10         }
11     }
12     
13     public int survive(ListNode head, int k) {
14         if (head == null) return -1;
15         ListNode prev = head;
16         while (prev!=null && prev.next!=head) {
17             prev = prev.next;
18         }
19         if (prev == null) return -1; //not a loop
20         //now prev is the previous node of head
21         int count = 1;
22         while (head.next != head) {
23             if (count == k) {
24                 prev.next = head.next;
25                 head = head.next;
26                 count = 1;
27             }
28             else {
29                 head = head.next;
30                 prev = prev.next;
31                 count++;
32             }
33         }
34         return head.val;
35     }
36     
37     public static void main(String[] args) {
38         Josephus sol = new Josephus();
39         ListNode node1 = sol.new ListNode(1);
40         ListNode node2 = sol.new ListNode(2);
41         ListNode node3 = sol.new ListNode(3);
42         ListNode node4 = sol.new ListNode(4);
43         ListNode node5 = sol.new ListNode(5);
44         ListNode node6 = sol.new ListNode(6);
45         node1.next = node2;
46         node2.next = node3;
47         node3.next = node4;
48         node4.next = node5;
49         node5.next = node6;
50         node6.next = node1;
51         int res = sol.survive(node1, 2);
52         System.out.println(res);
53     }
54 }

Doubly LinkedList

可以一边loop一边确定是不是有环，while loop结束条件是 head.next != null && head.next != head, 如果出现head.next == null说明无环，如果

head.next == head说明仅剩一个元素，正常结束