Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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());
}
}
}
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)
- montu March 10, 2017