Facebook hiring questions

solution.java

import java.util.*;
public class Solution{
	public final static int MAX_NUMBER_OF_STATES = 390625;//5^8
	
	class State{
		int steps;
		int[] conf;
		int peg1, peg2;
		int prev;
		
		State(int steps, int[] conf, int peg1, int peg2, int prev){
			this.steps = steps;
			this.conf  = conf.clone();
			this.peg1  = peg1;
			this.peg2  = peg2;
			this.prev  = prev;
		}
	}
	
	Comparator<int[]> cmp;
	
	State[] queue;
	
	int nQ, sol;
	
	int N, K;
	
	int[] initial, target;
	
	
	void read(){
		Scanner in = new Scanner(System.in);
		
		N = in.nextInt();
		K = in.nextInt();
		
		initial = new int[K+1];
		target = new int[K+1];
		
		for(int i=1; i<=N;++i){
			int x = in.nextInt();
			initial[x] |= (1<<i);
		}
		
		for(int i=1; i<=N;++i){
			int x = in.nextInt();
			target[x] |= (1<<i);
		}
		
		in.close();
	}
	
	
	int getFirstBit(int conf){
		for(int bit=1; bit <= N; ++bit)
			if((conf & (1<<bit)) > 0)
				return bit;
		return 0;
	}
	
	void solve(){
		queue = new State[MAX_NUMBER_OF_STATES];
		
		cmp = new Comparator<int[]>(){
			@Override
			public int compare(int[] arg0, int[] arg1) {
				for(int i=0; i<arg0.length; ++i)
					if(arg0[i] != arg1[i])
						return arg0[i] - arg1[i];
				return 0;
			}};
		
		Set<int[]> used = new TreeSet<int[]>(cmp);
		
		queue[nQ = 0] = new State(0, initial, 0, 0, -1);
		used.add(initial);
		
		int conf[] = new int[K+1];
		for(int p=0; p<=nQ; ++p){
			if(cmp.compare(queue[p].conf, target) == 0){
				sol = p;
				return;
			}
			
			for(int i=1; i<=K; ++i)
				for(int j=1; j<=K; ++j){
					conf = queue[p].conf.clone();
					
					int disk1 = getFirstBit(conf[i]);
					int disk2 = getFirstBit(conf[j]);
					
					if(disk1 == 0 || (disk1 > disk2 && disk2 != 0) || i == j)
						continue;
					
					conf[i] -= (1<<disk1);
					conf[j] |= (1<<disk1);
					
					if(used.contains(conf))
						continue;
					
					queue[++nQ] = new State(queue[p].steps + 1, conf, i, j, p);
					used.add(conf);
				}
		}
	}
	
	
	void print(int i){
		if(i == 0)
			return;
		
		print(queue[i].prev);
		
		System.out.println(queue[i].peg1 + " " + queue[i].peg2);
	}
	
	Solution(){
		read();
		solve();
		System.out.println(queue[sol].steps);
		print(sol);
	}
	
	public static void main(String[] args){
		new Solution();
	}
}