## Amazon Interview Question for SDE-2s

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````import 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)``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````import 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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
for i in range(2, n+1):
newCriminalNode = Node(i)
curr.next = newCriminalNode
curr = newCriminalNode

# Go through the circular linked list
# and kill every other criminal by setting
# criminal.next to be criminal.next.next
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]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();
for (int i = 1; i <= n; i++) {
}
while (q.size() > 2) {
int x = q.getFirst();
q.remove(0);
q.remove(0);
}
System.out.println(q.getFirst() + " " + q.getLast());
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
int num = 7;
for(int i = 1; i <=num; 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());
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedList:

void solution(int  num) {

for(int i = 1; i <=num; 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());
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedList:

void solution(int  n) {

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());
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++) {
}
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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.