Interview Query
Back to Data Structures and Algorithms Interview
Data Structures and Algorithms Interview

Data Structures and Algorithms Interview

2 of 20 Completed

Introduction

What Are Data Structures?

What is an Algorithm?

Assessment 1: Tower of Hanoi

Revisiting A Tower of Hanoi

Assessment 1: Tower of Hanoi
Go to question details page

The Tower of Hanoi is a mathematical puzzle that consists of three rods and several discs of different sizes that can slide onto any rod. The puzzle starts with all the discs stacked on a single rod, the smallest disc at the top, making a cone shape.

The object of the puzzle is to move the entire stack to another rod, obeying these rules:

  1. Only one disc can be moved at a time.

    • Each move consists of taking the upper disc from one of the stacks and placing it on top of another stack or an empty rod.09

  2. No larger disc may be placed on top of a smaller disc.

With these rules in mind, how would you approach solving the puzzle if there are three discs on the leftmost rod and your goal is to move them all to the rightmost rod?

Tower of Hanoi is a fun puzzle game that consists of a set of 3 pegs (A, B, C) and n number of disks. You are required to move all disks from the source peg A to destination peg C, under the following conditions:

  • You can only move one disk for each action.
  • You can only move the disk onto the top of another peg; you cannot place it off to the side or under existing disks.
  • You cannot place a larger disk onto a smaller disk.

Initially, all disks are on the source A peg and sorted by decreasing width from bottom to the top (widest on the bottom, smallest on the top).

You must develop an algorithm to move all disks from A to the destination peg C with the optimal solution. Also, return every step made from the starting state to the final state.

alt

alt

Example

Input:

n = 3

Output:

#return list of {"A":[],"B":[],"C":[]} 
tower_of_hanoi_solver(n) -> [
        {"A": [1, 2, 3], "B": [], "C": []},
        {"A": [2, 3], "B": [], "C": [1]},
        {"A": [3], "B": [2], "C": [1]},
        {"A": [3], "B": [1, 2], "C": []},
        {"A": [], "B": [1, 2], "C": [3]},
        {"A": [1], "B": [2], "C": [3]},
        {"A": [1], "B": [], "C": [2, 3]},
        {"A": [], "B": [], "C": [1, 2, 3]}
    ]
What is an Algorithm?
Revisiting A Tower of Hanoi
Good job, keep it up!

10%

Completed

You have 18 sections remaining on this learning path.