Amazon Interview Question SDE-2s
Country: United States
This popular problem is known as the Josephus Problem. If the problem asked us to find the last person standing, it could in fact be solved in constant O(1) time using a mathematical formula. However, since the problem asks us for the last TWO people remaining, we have to capture the intermediate results. To perform this, I construct a circular linked list which represents the circle in which the criminals stand and then simulate the killing.
Finally, I capture intermediate results in a stack and then to pop the last two results to obtain the last two men standing alive. The time complexity of this algorithm would be O(N) where N = the number of criminals. The space complexity would O(N/2) roughly since we capture the results of approximately half of the criminals using the stack.
Solution code in Python below :
class Node:
def __init__(self, data):
self.data = data
self.next = None
def josephusCircle(n):
# Simple Cases
if n == 1: return [1]
if n == 2: return [1, 2]
# Create circular linked list
# for n >= 3
head = Node(1)
curr = head
for i in range(2, n+1):
newCriminalNode = Node(i)
curr.next = newCriminalNode
curr = newCriminalNode
curr.next = head
# Go through the circular linked list
# and kill every other criminal by setting
# criminal.next to be criminal.next.next
curr = head
resultStack = []
while curr.next != curr:
resultStack.append(curr.data)
curr.next = curr.next.next
curr = curr.next
lastCriminal = resultStack.pop()
penultimateCriminal = resultStack.pop()
return [penultimateCriminal, lastCriminal]
Test code:
print(josephusCircle(5)) # [5,3]
print(josephusCircle(6)) # [1, 5]
print(josephusCircle(7)) # [3,7]
print(josephusCircle(10)) # [9, 5]
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
LinkedList<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
q.add(i);
}
while (q.size() > 2) {
int x = q.getFirst();
q.remove(0);
q.remove(0);
q.add(x);
}
System.out.println(q.getFirst() + " " + q.getLast());
}
}
import java.util.LinkedList;
public static void main(String[] args) {
int num = 7;
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 1; i <=num; i++)
list.add(i);
int start = 0;
while(list.size() > 2) {
start = Math.min(start+1, (start+1)%list.size());
list.remove(start);
}
System.out.println(list.size() + " value="+list.getFirst());
}
import java.util.LinkedList:
void solution(int num) {
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 1; i <=num; i++)
list.add(i);
int start = 0;
while(list.size() > 2) {
start = Math.min(start+1, (start+1)%list.size());
list.remove(start);
}
System.out.println("first="+list.getFirst() + " last="+list.getLast());
}
import java.util.LinkedList:
void solution(int n) {
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i = 1; i <= n; i++) list.add(i);
int i = 0;
while(list.size() > 2) {
i = (i + 1) % list.size();
list.remove(i);
}
System.out.println("Last 2 survivors: " + list.getFirst() + " and " + list.getLast());
}
import java.util.*;
public class CyclicExecution {
public static void main(String... arg) {
CyclicExecution execution = new CyclicExecution();
System.out.println(execution.process(5));
System.out.println(execution.process(7));
}
public List<Integer> process(int N) {
List<Integer> integers = new ArrayList<>();
for (int i = 0; i < N; i++) {
integers.add(i + 1);
}
return popBy(integers, 2, 0);
}
private List<Integer> popBy(List<Integer> ints, int i, int j) {
if (ints.size() == 2) {
return ints;
}
if (ints.size() == (j + 1)) {
ints.remove(0);
return popBy(ints, i, 0);
} else {
ints.remove(j + 1);
return popBy(ints, i, j + 1);
}
}
}
import java.util.Arrays;
import java.util.List;
public class CirculaarCriminalDeath {
public static void main(String[] args) {
System.out.println(lastTwoCriminalsInCircle(4));
System.out.println(lastTwoCriminalsInCircle(-4));
System.out.println(lastTwoCriminalsInCircle(Long.MAX_VALUE));
}
/**
* N people form a circle, in each cycle they keep killing the one[alive] to
* their immediate left i.e. next element; When n is even, man at end changes by
* power of 2^pow; when n is odd, man at front changes by power of 2^(pow+1);
* With each cycle pow increases by 1.
*
* @param n
* @return
*
*/
/**
* Odd
* 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37
* -> n odd
*
* Cycle 1: 3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37 -> since prev n
* was odd, front = front + 2; n = n/2, we get n = 18, i.e. even, deleted n/2 +
* 1 = 19
*
*
* Cycle2: 3,7,11,15,19,23,27,31,35 -> since prev n was even, back = back - 2; n
* = n/2 we get n = 9, i.e. odd, deleted n/2 = 9
*
*
* Cycle3: 11,19,27,35 -> since prev n was odd, front = front + 8; n = n/2 we
* get n = 4, i.e. even; deleted n/2 + 1 = 5
*
*
* Cycle4: 11,27 -> since prev n was even, back = back - 8; n = n/2 we get n = 2
* even; deleted n/2 = 2
*
* if(n == 2) -> answer is front , back i.e 11,27
*
*
* Even
* 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28 ->
* n even
*
*
* Cycle1: 1,3,5,7,9,11,13,15,17,19,21,23,25,27 -> since prev n was even, back =
* back - 1; n = n/2, we get n = 14, i.e. even, deleted n/2 = 14
*
* Cycle2: 1,5,9,13,17,21,25 -> since prev n was even, back = back - 2; n = n/2,
* we get n = 7, i.e. odd, deleted n/2 = 7
*
*
* Cycle: 9,17,25 -> since prev n was odd, front = front + 8; n = n/2, we get n
* = 3, i.e. odd, deleted n/2 + 1 = 4
*
* if(n == 3) -> answer is front, back i.e 9,25
*
*/
static List<Long> lastTwoCriminalsInCircle(long n) {
if (n <= 1) {
System.out.println("Please enter a positive Intger between 2 and " + Long.MAX_VALUE);
return Arrays.asList(n);
}
long front = 1l;
long back = n;
double power = 0;
double base = 2;
while (n > 3) {
long f = (long) Math.pow(base, (power + 1));
long b = (long) Math.pow(base, power);
if (n % 2l == 0) {
back = back - b;
}
if (n % 2l != 0) {
front = front + f;
}
n = n / 2l;
power++;
}
return Arrays.asList(front, back);
}
}
package com.sammeta.dsa.lists;
/**
* Created by laxmikumar on 24/02/20.
*/
public class LastManStanding {
public static void main(String[] args) {
// int i = 7;
for (int i=1; i< 20; i++) {
int survivor = findLastManStanding(i);
System.out.println(i +"="+survivor);
}
}
/**
* n = 2 ^ n + l
* w(n) = 2l+1
*/
private static int findLastManStanding(int n) {
int l = 0;
int twoPower = 1;
int twoPowerNext = 2;
int x =0;
for (int i=1; twoPower < n ; i++) {
twoPower = (int) Math.pow(2, i);
twoPowerNext = (int) Math.pow(2, i+1);
if (twoPower <= n && n < twoPowerNext) {
x = twoPower;
break;
}
}
l = n - x;
return (int) (2*l+1);
}
}
- Pilgrim March 09, 2018import sys n = int(sys.argv[1]) turn = 1 first = 1 last = n while n > 3: if n % 2 != 0: first += turn * 2 else: last -= turn turn *= 2 n = n // 2 print(first, last)