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

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