Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 4 vote

This looks like "Tower of Hanoi" algorithm. h t t p://en.wikipedia.org/wiki/Tower_of_Hanoi

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

This is taken from Facebook's demo puzzles.
You can see it on Facebook. This is not an interview question.
This is a coding puzzle intended to be solved at home.

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

Why -1 to this, when I read this it looks like Tower of Hanoi. If not please provide the answer why it is not?

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

i think that's not helpful. Tower of Hanoi is a recursion 101 program. This one, on the other hand, is far more complex. It probably requires generating a graph of all positions that take from the start to the end and find the one with shortest length.

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

i solved it using array of stacks and traversing the stacks with ID-DFS so give it a try guys i think it works .. i passed all the test cases 2 + 4 hidden on interviewstreet

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FB_test1
{
class Program
{
int N_numberOfDiscs = 0, K_numberOfPegs = 0;
int inputLines = 2;
int[][] data;
Stack<int>[] initStack;
Stack<int>[] FinalStack;
int reclimit = 7;
List<string> res = new List<string>();

{
N_numberOfDiscs = int.Parse(firstLineArgs[0]);
K_numberOfPegs = int.Parse(firstLineArgs[1]);
data = new int[inputLines][];
for (int i = 0; i < inputLines; i++)
{
data[i] = parseStringArr(line);
}
initStack = new Stack<int>[K_numberOfPegs];
stackBuilder(ref initStack, data[0]);
FinalStack = new Stack<int>[K_numberOfPegs];
stackBuilder(ref FinalStack, data[1]);
}
void stackBuilder(ref Stack<int>[] stack, int[] numbers)
{
for (int i = 0; i < stack.Length; i++)
{
stack[i] = new Stack<int>();
}
for (int i = numbers.Length - 1; i >= 0; i--)
{
int col = numbers[i];
stack[col - 1].Push(i + 1);
}
}
int[] parseStringArr(string[] arr)
{
int[] ret = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
try
{
ret[i] = int.Parse(arr[i]);
}
catch (Exception e)
{
int x = 0;
}
}
return ret;
}

bool jumping(string moving, int from, int to)
{
if (string.IsNullOrEmpty(moving))
return false;
char[] c = { '\n' };
var numbers = moving.Split(c, StringSplitOptions.RemoveEmptyEntries).Last().Split(' ').Select(x => int.Parse(x));
if (numbers.ElementAt(0) == to && numbers.ElementAt(1) == from)
return true;
return false;
//return (from == oldTo && to == oldFrom && to != 0 )? true : false;
}

void move(Stack<int>[] init, Stack<int>[] final, int from, int to, string moving, int max, List<int[]> validmoves)
{
if (reclimit <= max)
{
return;
}
if (needsWork(init, final))
{
for (int i = 0; i < validmoves.Count; i++)
{
Stack<int>[] temp = copyStacks(init);
validmoves = validMoves(temp);
if (i < validmoves.Count)
{
from = validmoves.ElementAt(i)[0];
to = validmoves.ElementAt(i)[1];
//if (jumping(moving, from, to))
//     continue;
moveDisc(temp, from, to);
string str = moving + from + " " + to + "\n";
//Console.WriteLine(str);
move(temp, final, from, to, str, max + 1, validmoves);
}
}
}
else
{
return;
}
}
Stack<int>[] copyStacks(Stack<int>[] init)
{
Stack<int>[] ret = new Stack<int>[init.Length];
int i = 0;
foreach (Stack<int> s in init)
{
ret[i++] = new Stack<int>(s.Reverse());
}
return ret;
}
void moveDisc(Stack<int>[] init, int from, int to)
{
int popped = init[from - 1].Pop();
init[to - 1].Push(popped);
}
bool needsWork(Stack<int>[] init, Stack<int>[] final)
{
for (int i = 0; i < init.Length; i++)
{
if (init[i].Count != final[i].Count)
return true;
for (int j = 0; j < init[i].Count; j++)
{
if (init[i].ElementAt(j) != final[i].ElementAt(j))
return true;
}
}
return false;
}
List<int[]> validMoves(Stack<int>[] stacks)
{
List<int[]>[] ret = new List<int[]>[stacks.Length];
for (int i = 0; i < stacks.Length; i++)
{
if (stacks[i].Count() != 0)
{
int toMove = stacks[i].Peek();
ret[i] = new List<int[]>();
for (int j = 0; j < stacks.Length; j++)
{
if (j != i)
{
int[] subarr = { i + 1, j + 1 };
if (stacks[j].Count != 0)
{
int targetPeek = stacks[j].Peek();
if (targetPeek - 1 == toMove && FinalStack[j].Count != 0 && FinalStack[j].Peek() <= toMove)
{
ret[i].Clear();
break;
}
if (toMove < targetPeek)
{
}
}
else
{
}
}
}
}
}
List<int[]> append = new List<int[]>();
foreach (List<int[]> l in ret)
{
if (l != null)
}
return append;
}
void move()
{
int i = 1;
while (res.Count==0)
{
reclimit = i++;
move(initStack, FinalStack, 0, 0, "", 0, validMoves(initStack));
}
}
void writeRes(List<string> sorted)
{
string[] x = sorted.ElementAt(0).Split('\n');
Console.WriteLine(x.Length - 1);
foreach (string s in x)
{
Console.WriteLine(s);
}
}
static void Main(string[] args)
{
Program p = new Program();
p.move();
p.res = p.res.OrderBy((x) => x.Length).ToList();
p.writeRes(p.res);
}
}
}``````

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

I was able to write a program with a recursive "move" method which moves disks starting from the largest to the smallest to its corresponding target keg. But in that method, several other disks need to be moved as well. How can we tell which move will result in minimum moves? and how to not run into an infinite loop of moves?

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

Well here is the solution...plz explain this solution in the link given below :
" blog.csdn.net/maqingli20/article/details/7361057 "

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

That's amazing. Went through it once. No idea if it works.

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

the code given works correctly...

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

the complexity of problem seems to be (N*K^2)^7. I don't think its right

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

This problem can be seen as a search problem -- searching for the optimal solution (minimal number of steps leading to the final state). We can search all possible states using either depth first search (recursion) or breadth first search. The problem with the dfs is that it will take a significant amount of time because it will first find the worst possible solution (the furthest from the initial state) and then go back to the optimal, so we pretty much have to find all possible solutions, using recursion, and return the one that is completed in the minimum number of steps.
With the bfs approach, however, we can return the first solution we find, because we know that every other solution will involve at least one additional step, hence it is not the optimal solution. This approach is much faster.

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

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

Here is the solution. I solved it using backtracking and a modification of breath first search.

``````import java.util.*;

public class Solution{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
StringBuffer start = new StringBuffer();
for(int i=0;i<N;i++)start.append(sc.next()).append(" ");
StringBuffer end = new StringBuffer();
for(int i=0;i<N;i++)end.append(sc.next()).append(" ");
String prev = null;
LinkedList<String> result = movesTrack(start.toString().trim(), end.toString().trim(), N, K);
System.out.println(result.size()-1);
for(String s : result)
{
if(prev!=null)System.out.println(Solution.deltaMove(s, prev));
prev=s;
}
}
public static LinkedList<String> movesTrack(String start, String end, int N, int K)
{
Set<String> visitedSet = new HashSet<String>();
Map<String, String> backtrackMap = new TreeMap<String, String>();

while(!actionQ.isEmpty())
{
String source = actionQ.poll();
for(String next : Solution.getNextMoves(source, N, K))
{
if(next.equals(end))
{
while(source!=null)
{
source = backtrackMap.get(source);
}
return list;
}
if(!visitedSet.contains(next))
{
backtrackMap.put(next, source);
}
}
}
return null;
}
public static Set<String> getNextMoves(String pos, int N, int K)
{
Set<String> moves = new TreeSet<String>();
String[] discPositions = pos.split(" ");
for(int disc=1; disc<=N; disc++)
{
int peg = Integer.parseInt(discPositions[disc-1]);
if(Solution.topOfPeg(discPositions, peg) == disc)
{
for(int targetPeg=1; targetPeg<=K; targetPeg++)
{
int targetTop = Solution.topOfPeg(discPositions, targetPeg);
if(targetPeg!=peg & (targetTop>disc || targetTop==0))
{
String state = pos;
}
}
}
}
return moves;
}
public static int topOfPeg(String[] discPositions, int peg)
{
for(int i=1; i<=discPositions.length; i++)
if(Integer.parseInt(discPositions[i-1]) == peg)
return i;
return 0;
}
public static String deltaMove(String curr, String prev)
{
String[] start = prev.split(" ");
String[] end = curr.split(" ");
for(int i=1;i<=start.length;i++)
if(!start[i-1].equals(end[i-1]))
return (start[i-1]+" "+end[i-1]);
return null;
}
}``````

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

Try this input

``````7 4
2 2 4 3 1 1 4
3 3 3 3 2 2 1``````

Your code returns 8 moves. I don't think its correct.
Also, in your approach, which seems correct, how do you avoid getting in to infinite loop?

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

I think the code is correct, but facebook judge will not give questions which involve more than 6 movements. Because it clearly states that... The thing is, I was unable to figure out the solution to your test case manually, can you tell me the solution set involving "less than" 7 moves?

Cheers!

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

Dude how do u even write such a long code?? I mean this entire thing is so complex. How do u make it simple? Please tell...

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

even I am stuck, especially with the test case like

``````7 4
2 2 4 3 1 1 4
3 3 3 3 2 2 1``````

you can check out my code in PHP nishantarora.in/?p=846 , but still I am unable to solve for cases like the one mentioned above. I might be wrong! Please keep me updated

``````<?php
\$ip     = fopen('php://stdin', "r");
\$op     = fopen('php://stdout',"w");

function search_peg(\$disk, \$pegs){
foreach(\$pegs as \$key1=>\$val1){
foreach(\$pegs[\$key1] as \$key2=>\$val2){
if(\$val2 == \$disk){
return \$key1;
}
}
}
}

function is_on_top(\$num, \$peg){
\$comp = count(\$peg)-1;
foreach(\$peg as \$key=>\$val){
if(\$val == \$num && \$key == \$comp){
return true;
}
}
return false;
}

function what_is_on_top(\$peg){
return \$peg[count(\$peg)-1];
}

function best_peg(\$not, \$peg, \$tobe){
foreach(\$peg as \$key=>\$val){
if(\$key !== \$not){
\$temp = count(\$val);
if(\$temp ==0){
return \$key;
}
}
}
foreach(\$peg as \$key=>\$val){
if(\$key !== \$not){
\$temp = \$val[count(\$val)-1];
if(\$temp < \$tobe){
if(empty(\$ret) || \$temp<\$ret){
\$ret = \$temp;
}
}
}
}
return \$ret;
}

\$init = explode(" ", trim(fgets(\$ip)));
\$n = \$init[0];
\$k = \$init[1];
\$vals = explode(" ", trim(fgets(\$ip)));
\$i = \$n;
while(\$i>0){
if(!is_array(\$peg[\$vals[\$i-1]])){
\$peg[\$vals[\$i-1]] = array();
}
array_push(\$peg[\$vals[\$i-1]], \$i);
\$i--;
}
//protective
for(\$i=1;\$i<=\$k;\$i++){
if(!is_array(\$peg[\$i])){
\$peg[\$i] = array();
}

}
//print_r(\$peg);
\$config = explode(" ", trim(fgets(\$ip)));
\$i = \$n;
while(\$i>0){
if(!is_array(\$conf[\$config[\$i-1]])){
\$conf[\$config[\$i-1]] = array();
}
array_push(\$conf[\$config[\$i-1]], \$i);
\$i--;
}
//print_r(\$conf);

/*
foreach(\$conf as \$key=>\$val){
foreach(\$conf[\$key] as \$key1=>\$val1){
if(\$conf[\$key][\$key1] !== \$peg[\$key][\$key1]){
echo \$conf[\$key][\$key1] ." is on not on the right position\n";
}else{
echo \$conf[\$key][\$key1] ." is on the right position\n";
}
}
}
*/

//    fwrite(\$op, sprintf("%d\n", \$cand));
//echo search_peg(0, \$peg);
//echo search_peg(0, \$conf);
for(\$i=\$n;\$i>0;\$i--){
\$init_peg = search_peg(\$i, \$peg);
\$fina_peg = search_peg(\$i, \$conf);
if(\$init_peg !== \$fina_peg){
//echo \$i." => ". what_is_on_top(\$peg[\$fina_peg]). "\n";
while(what_is_on_top(\$peg[\$fina_peg]) < \$i && !empty(\$peg[\$fina_peg])){
\$best = best_peg(\$fina_peg, \$peg, \$i);
if(!is_array(\$peg[\$best])){
\$peg[\$best] = array();
}
array_push(\$peg[\$best], array_pop(\$peg[\$fina_peg]));
\$movem[] = \$fina_peg.' '.\$best;
}
if(is_on_top(\$i, \$peg[\$init_peg])){
array_push(\$peg[\$fina_peg], array_pop(\$peg[\$init_peg]));
\$movem[] = \$init_peg.' '.\$fina_peg;
}else{
while(!is_on_top(\$i, \$peg[\$init_peg])){
\$best = best_peg(\$fina_peg, \$peg, \$i);
if(!is_array(\$peg[\$best])){
\$peg[\$best] = array();
}
array_push(\$peg[\$best], array_pop(\$peg[\$init_peg]));
\$movem[] = \$init_peg.' '.\$best;
}
array_push(\$peg[\$fina_peg], array_pop(\$peg[\$init_peg]));
\$movem[] = \$init_peg.' '.\$fina_peg;
}
}
}
//print_r(\$peg);
echo count(\$movem)."\n";
foreach (\$movem as \$moves){
echo \$moves ."\n";
}
?>``````

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

can anyone explain
blog.csdn.net/maqingli20/article/details/7361057

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

basically this is a depth-first-search over all possible moves.
its getting the start and end configuration and then initializes the pegs in the way that each peg holds its smallest disc number (respectively the top-most disc).
then it iterates over all combinations of 2 pegs.
if it is possible to move the disc from peg i to j it does so, and checks, if this is already the desired configuration.
if so then set the minDepth(which i would call maxDepth because its the maximal depth until where a better/equal solution can be found), to the current depth, so any calls with higher depths are now simply returned, because we already found a better solution. additionally memorize the steps done to this point.
if we dont have the desired configuration, we "start" with the current configuration the whole thing again.
on return of the recursion, it reconstructs the old configuration(before the last iteration) and iterates again(tries another move at this depth).

rest is output.

well explaining code literally is really hard for me, but i hope you could get at least an idea how it actually works...

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

... I think it's just a BFS problem ...

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

This code in ruby is working fine...

``````require 'set'

class Node

def initialize(situation, moves = [])
@situation = situation
@moves     = moves
end

def ==(other)
situation == other.situation
end
end

gets.strip.split(' ').map(&:to_i)
end

queue         = Array.new
visited_nodes = Set.new

loop do
available_pegs = (1..k).to_a

current_node.situation.each_with_index do |orig_peg, index|
if available_pegs.include? orig_peg
available_pegs.delete orig_peg

break if available_pegs.empty?

available_pegs.each do |dest_peg|
new_situation        = current_node.situation.dup
new_situation[index] = dest_peg

new_moves            = current_node.moves.dup
new_moves            << "#{ orig_peg } #{ dest_peg }"

new_node = Node.new(new_situation, new_moves)

if new_node == final_node
puts new_node.moves.count, new_node.moves
exit
end

queue << new_node unless visited_nodes.include?(new_node) || queue.include?(new_node)
end
end
end

current_node = queue.shift
end``````

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

``````import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;

/**
* @author thiagogenez
*
*
*         There are K pegs. Each peg can hold discs in decreasing order of
*         radius when looked from bottom to top of the peg. There are N discs
*         which have radius 1 to N; Given the initial configuration of the pegs
*         and the final configuration of the pegs, output the moves required to
*         transform from the initial to final configuration. You are required
*         to do the transformations in minimal number of moves.
*
*         A move consists of picking the topmost disc of any one of the pegs
*         and placing it on top of anyother peg. At anypoint of time, the
*         decreasing radius property of all the pegs must be maintained.
*
*         Constraints: 1<= N<=8 3<= K<=5
*
*         Input Format: N K 2nd line contains N integers. Each integer in the
*         second line is in the range 1 to K where the i-th integer denotes the
*         peg to which disc of radius i is present in the initial
*         configuration. 3rd line denotes the final configuration in a format
*         similar to the initial configuration.
*
*         Output Format: The first line contains M - The minimal number of
*         moves required to complete the transformation. The following M lines
*         describe a move, by a peg number to pick from and a peg number to
*         place on. If there are more than one solutions, it's sufficient to
*         output any one of them. You can assume, there is always a solution
*         with less than 7 moves and the initial confirguration will not be
*         same as the final one.
*
*         Sample Input #00:
*
*         2 3
*         1 1
*         2 2
*
*         Sample Output #00:
*
*         3
*         1 3
*         1 2
*         3 2
*
*         Sample Input #01:
*
*         6 4
*         4 2 4 3 1 1
*         1 1 1 1 1 1
*
*         Sample Output #01:
*
*         5
*         3 1
*         4 3
*         4 1
*         2 1
*         3 1
*
*         NOTE: You need to write the full code taking all inputs are from
*         stdin and outputs to stdout If you are using "Java", the classname is
*         "Solution"
*
*/
public class Solution {

public Solution() {
try {
System.in));

@SuppressWarnings("unused")
int n = Integer.parseInt(input[0]);
int k = Integer.parseInt(input[1]);

end_config);

System.out.println(moves.size());
for (String move : moves) {
System.out.println(move);
}
} catch (Exception e) {
System.err.println("Error:" + e.getMessage());
e.printStackTrace();
}
}

private Vector<String> breadthFirstSearch(int k, String begin_config,
String end_config) {

Node node = new Node(null, null, begin_config);

while (!queue.isEmpty()) {
node = queue.remove();
if (!node.isVisited()) {
node.setVisited(true);
if (node.getConfig().equals(end_config))
break;
ArrayList<Node> nextsNodes = node.getNexts(k);
}
}

queue.clear();
queue = null;

Vector<String> moves = new Vector<String>();
while (node.getFather() != null) {
node = node.getFather();
}
Collections.reverse(moves);

return moves;
}

public static void main(String args[]) {
new Solution();
}

private class Node {
private Node father;
private String last_move;
private String config;
private boolean visited = false;

public Node(Node father, String last_move, String config) {
super();
this.father = father;
this.last_move = last_move;
this.config = config;
}

public ArrayList<Node> getNexts(int k) {
ArrayList<Node> nexts = new ArrayList<Solution.Node>();
Vector<Stack<Integer>> pegs = getPegs(k);

for (int from = 0; from < k; from++) {
for (int to = 0; to < k; to++) {
if (from != to) {
if (!pegs.get(from).isEmpty()
&& (pegs.get(to).isEmpty() || pegs.get(from)
.peek() < pegs.get(to).peek())) {

String s[] = this.config.split(" ");
s[pegs.get(from).peek() - 1] = String
.valueOf(to + 1);
String config = "";
for (int i = 0; i < s.length; i++) {
config += s[i] + " ";
}
config = config.trim();
String last_move = String.valueOf(from + 1) + " "
+ String.valueOf(to + 1);

}
}
}
}
return nexts;
}

private Vector<Stack<Integer>> getPegs(int k) {
Vector<Stack<Integer>> pegs = new Vector<Stack<Integer>>(k);
for (int i = 0; i < k; i++) {
}
String s[] = this.config.split(" ");
for (int i = s.length - 1; i >= 0; i--) {
}
return pegs;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + getOuterType().hashCode();
result = prime * result
+ ((config == null) ? 0 : config.hashCode());
result = prime * result
+ ((father == null) ? 0 : father.hashCode());
result = prime * result
+ ((last_move == null) ? 0 : last_move.hashCode());
result = prime * result + (visited ? 1231 : 1237);
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (config == null) {
if (other.config != null)
return false;
} else if (!config.equals(other.config))
return false;
if (father == null) {
if (other.father != null)
return false;
} else if (!father.equals(other.father))
return false;
if (last_move == null) {
if (other.last_move != null)
return false;
} else if (!last_move.equals(other.last_move))
return false;
if (visited != other.visited)
return false;
return true;
}

public Node getFather() {
return father;
}

public String getLast_move() {
return last_move;
}

public String getConfig() {
return config;
}

public boolean isVisited() {
return visited;
}

public void setVisited(boolean visited) {
this.visited = visited;
}

private Solution getOuterType() {
return Solution.this;
}

}
}``````

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

the Constraints:
1<= N<=8
3<= K<=5 ,
The number of pegs are <=5,no chance of infinite loop,the constraint
N can also be
N<=8,as N can disks can never be zero,
and K lies in between 3 and 5....

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

Here is a Java code which prepares the graph with neighboring configurations and solves it. I tried to use Object-Oriented way, but I still feel there might be better hack way to solve this faster. Hope it helps.

``````import FBSample.Node.Move;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;

/**
*
*/
public class FBSample {

public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
//pegs initial config
Node source = readPegsConfiguration(k, n, sc);
Node target = readPegsConfiguration(k, n, sc);
//To keep track what config we visited and avoid cycles
Set<Node> visited = new HashSet<Node>();
try {
minMovesToTarget(source, target, visited);
} catch (Exception ex) {
System.out.println("Exception = " + ex);
}
}

private static void minMovesToTarget(Node source, Node target, Set<Node> visited) throws CloneNotSupportedException {
//Perform BFS
Node current = source;
while (!q.isEmpty()) {
current = q.poll();
if (current.equals(target)) { //found the target configuration
break;
}
List<Node> neighbors = current.neighbors();
if (neighbors.size() > 0) {
for (Node n : neighbors) {
if (!visited.contains(n)) {//if not visited, put it in queue
q.offer(n);
}
}
}
}
//Printing path and moves if target config found
if (current.equals(target)) {
printOutput(current);
}
}

private static Node readPegsConfiguration(int k, int n, Scanner sc) {
Stack<Integer>[] initialState = new Stack[k];
for (int i = 0; i < k; i++) {
initialState[i] = new Stack<Integer>();
}
//reading and reversing the line as we need to put the elements in decresing size
//disc is key and peg is value.
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
map.put(i, sc.nextInt());
}
//prepare pegs
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
initialState[entry.getValue() - 1].push(entry.getKey());
}
return new Node(initialState);
}

static void printOutput(Node target) {
Stack<Move> stack = new Stack<>(); //using stack as we need to print the trail from Source - target config
while (target.parent != null) {
target = target.parent;
}
System.out.println(stack.size());
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}

static class Node implements Cloneable {
//pegs
Stack<Integer>[] state = null;
Node parent = null;  //for backtracking trail
Move move = null; // The move we made to go to next neighbor config

public Node(Stack<Integer>[] st) {
state = st;
}

@Override
protected Node clone() throws CloneNotSupportedException {
Stack<Integer>[] cloneStacks = new Stack[state.length];
for (int i = 0; i < state.length; i++) {
cloneStacks[i] = (Stack) state[i].clone();
}
Node clone = new Node(cloneStacks);
return clone;
}

//returns the neghboring configurations.
//What all configurations we can get based on current config.
public List<Node> neighbors() throws CloneNotSupportedException {
List<Node> neighbors = new ArrayList<>();
int k = state.length;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i != j && !state[i].isEmpty()) {
Node child = this.clone();
//make a move
if (canWeMove(child.state[i], child.state[j])) {
child.state[j].push(child.state[i].pop());
//this is required to backtrack the trail once we find the target config
child.parent = this;
//the move we made to get to this neighbor
child.move = new Move(i, j);
}
}
}
}
return neighbors;
}

public boolean canWeMove(Stack<Integer> fromTower, Stack<Integer> toTower) {
if (toTower.isEmpty()) {// if destination peg is empty, then we can move any disc
return true;
}
int toDisc = toTower.peek();
int fromDisc = fromTower.peek();
if (fromDisc < toDisc) { //we can only place small disc on top
}
}

@Override
public int hashCode() {
int hash = 7;
return hash;
}

@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (!Arrays.deepEquals(this.state, other.state)) {
return false;
}
return true;
}

class Move {

int pegFrom, pegTo;

public Move(int f, int t) {
pegFrom = f + 1;
pegTo = t + 1;
}

@Override
public String toString() {
return pegFrom + " " + pegTo;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

just use a recursive function to do brute force search.. since we have:
1<= N<=8
3<= K<=5
and the problem statement guarantees that the answer will never be greater than 7. So.

Comment hidden because of low score. Click to expand.
-2
of 4 vote

Well, if M not mistaken.. this is last years Amazon question.. Unfortunately, it sounds like this is an NP problem and still the proper answer is under research !!!!!

Anyone can redirect to correct direction here ?

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

How do you tell this is an NP problem?

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

Well, I was solving this last year and was not able to code or hv proper algo. So I was searching some articles , where some researchers were having similar trouble as they have marked it as NP.

Mostly U can use either one as a variable (I mean either pegs or disks) not Both.. Complexity rises as we increase the no of pegs..

I was thinking of looping as well like
for (pegs=0;pegs<=NoofPegs;pegs)
recurse;

Still it won't solve this issue..

Lemme knw if some one has better algo..

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.