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)

- Pilgrim March 09, 2018 | Flag Reply
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)

- Pilgrim March 09, 2018 | Flag Reply
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
  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]

- prudent_programmer March 10, 2018 | Flag Reply
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();
        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());
    }

}

- ali_shakhan March 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vmssdkteam March 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Tom March 30, 2018 | Flag Reply
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++) {
            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);
        }
    }
}

- abrahamimohiosen April 14, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More