## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

``````def move_between_poles(pole1, pole2):
if not pole1 and not pole2:
return
if not pole1 or (pole1 and pole2 and pole1[-1] > pole2[-1]):
pole1.append(pole2.pop())
elif not pole2 or (pole1 and pole2 and pole1[-1] < pole2[-1]):
pole2.append(pole1.pop())

def toh_iter(n, source, target, aux):
moves = pow(2, n)
if not n%2:
aux,target = target,aux
for i in range(1,moves):
if i % 3 is 1:
move_between_poles(target, source)
if i % 3 is 2:
move_between_poles(aux, source)
if i % 3 is 0:
move_between_poles(target, aux)

def main():
source = [4,3,2,1]
aux = []
target = []
n = len(source)
toh_iter(n, source, target, aux)
print target``````

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

Pretty much the same algorithm as previous answer but with c# not python , I am sure this can be done with less memory complexity.

``````using System;
using System.Collections.Generic;

public class Program
{
public static void Main()
{
int num_of_disks = 3;
Stack<int> Src = new Stack<int>();
Stack<int> Aux = new Stack<int>();
Stack<int> Dest = new Stack<int>();

for (int i = num_of_disks; i >= 1; i--)
Src.Push(i);

Stack<int> Result = HanoiProblem (Src , Aux , Dest);

while (Result.Count > 0)
{
Console.WriteLine(Result.Pop());
}
}

public static Stack<int> HanoiProblem (Stack<int> Src , Stack<int> Aux , Stack<int> Dest)
{
int number_of_moves = (int) Math.Pow(2 , Src.Count) -1;
int number_of_disck = Src.Count;

for (int i = 1 ; i <= number_of_moves ; i++ )
{
if (i%3 == 1)
{
MakeLegalMove(Src , Dest);
Console.WriteLine("move Source and Dest");
}
else if (i % 3 == 2)
{
MakeLegalMove(Src , Aux);
Console.WriteLine("move Source and Aux");
}
else
{
MakeLegalMove(Aux , Dest);
Console.WriteLine("move Aux and Dest");
}

}

if  (number_of_disck%2 == 0)
{
return Aux;
}
else
{
return Dest;
}

}

public static void MakeLegalMove (Stack<int> A , Stack<int> B)
{

if (A.Count == 0  )
{
A.Push(B.Pop());
}
else if (B.Count == 0 || A.Peek() < B.Peek())
{
B.Push(A.Pop());
}
else if (A.Peek() > B.Peek())
{
A.Push(B.Pop());
}
else
{
B.Push(A.Pop());
}

}
}``````

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

``````def tower_of_hanoi_iterative(n_disks):
import collections
call_stack = collections.deque()
call_stack.append([n_disks, "L", "M", "R"])
while call_stack:
item = call_stack.popleft()
if len(item) == 3:
print("moving 1 disk from {left} to {right}".format(left=item[1], right=item[2]))
continue
n_disks, left, middle, right = item
if n_disks == 0:
continue
call_stack.appendleft([n_disks - 1, middle, left, right])
call_stack.appendleft([1, left, right])
call_stack.appendleft([n_disks - 1, left, right, middle])

if __name__ == '__main__':
tower_of_hanoi_iterative(3)``````

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.