Amazon Interview Question
SDE1sCountry: United States
Interview Type: Written Test
You can't just calculate those costs, you need to calculate the cost of transitioning from the given states to one of the four uniform states, of which there are many.
ex: Given NWNSN, you can transition to either SSSSS, NNNNN, WWWWW, or EEEEE, and you need to compute costs for every possible transition.
First start with setting statue 4, as there is only one option to set statue 4. After that there is only one option to set statue 6. Until now everything is optimal as you have no other options. BTW if now statue 0 and 1 are not at the same place, there is no final solution.
Now it starts to get difficult. If 0 and 1 are set to the same direction, there is always a solution. But how to find the optimal one?
Start setting statue number 7:
Use operation F until statue 3 is in the right direction. If that is working you just need to operate operations D,B,A in that order.
If 3 is on the correct position and 6 not, use G until it is on position.
Than u can use D,B,A again in this order.
I wan to know if this can be solved by set of equations or BFS ?
Here I am not concerned with this particular input but generic input and moves.
use breath first expension here is the code
package com.amz;
import static org.junit.Assert.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import org.junit.Test;
/**
* @author tim
*
*/
public class Puzzle {
/**
* breath first moves.
* @param status
* @return
*/
public Status breathMove(String status) {
if(done(status.toCharArray()))
return new Status(status, new ArrayList<Move>());
Queue<Status> sQueue = new LinkedList<Status>();
sQueue.add(new Status(status, new ArrayList<Move>()));
while(!sQueue.isEmpty()) {
Status s = sQueue.remove();
for(Move m : Move.values()) {
String newState = transform(s.status, m);
List<Move> moves = new ArrayList<Move>(s.moves);
moves.add(m);
Status newStatus = new Status(newState, moves);
if(done(newState.toCharArray()))
return newStatus;
sQueue.add(newStatus);
}
}
return null;
}
private String transform(String s, Move m) {
int[] pos = m.getPositions();
char[] status = s.toCharArray();
for(int i : pos) {
status[i] = transform(status[i]);
}
return String.valueOf(status);
}
private enum Move {
A(new int[]{0,1}),
B(new int[]{0,1,2}),
C(new int[]{1,4,5,6}),
D(new int[]{2,5}),
E(new int[]{3,5}),
F(new int[]{3,7}),
G(new int[]{5,7}),
H(new int[]{6,7});
int[] positions;
Move(int[] pos) {
positions = pos;
}
public int[] getPositions() {
return positions;
}
}
private class Status {
String status;
List<Move> moves;
Status(String s, List<Move> moves) {
this.status = s;
this.moves = moves;
}
}
private char transform(char c) {
switch(c) {
case 'N':
return 'E';
case 'E':
return 'S';
case 'S':
return 'W';
case 'W':
return 'N';
}
return c;
}
private boolean done(char[] status) {
char c = status[0];
for(int i = 1; i < status.length; i++) {
if(c!=status[i])
return false;
}
return true;
}
@Test
public void testCompass() {
Puzzle c = new Puzzle();
String s = "NNSEWSWN";
Status end = c.breathMove(s);
System.out.println("Final label: " + end.status + " Moves: " + end.moves.size() + " the moves: " + Arrays.toString(end.moves.toArray()));
assertNotNull(end);
}
}
First start with setting statue 4, as there is only one option to set statue 4. After that there is only one option to set statue 6. Until now everything is optimal as you have no other options. BTW if now statue 0 and 1 are not at the same place, there is no final solution.
Now it starts to get difficult. If 0 and 1 are set to the same direction, there is always a solution. But how to find the optimal one?
Start setting statue number 7:
Use operation F until statue 3 is in the right direction. If that is working you just need to operate operations D,B,A in that order.
If 3 is on the correct position and 7 not, use G until it is on position.
Than u can use D,B,A again in this order.
Constraints :
The statue 0 & 1 should face the same direction. Else the solution to this not possible.
Lets start with the statue 4.
Since the statue 4 can be moved by only one step, i.e. step C, why not take the statue 4 as our base direction i.e. all other statues facing in same direction as 4.
Now since we know in which our statue should face ( i.e. the direction in which statue 4 is facing ), lets take greedy approach.
By greedy approach we mean to say that, lets start making the statues one by one in the direction of statue 4.
Now which one to choose first ?
Firstly we can go for 2 i.e. the step D to make it 90 degree anti clockwise to direction of 4.
next do the step A to a number of times such that both 0 and 1 are facing the same direction as 2.
next do B. Now 0,1,2 are facing the same as 4.
Similarly we can do the same for rest of statues.
1) hash all states (8^4 = 4096) into 4 separate arrays
2) mark a different solution state (all Ns, Es, Ss, Ws) in each of the four arrays
3) start a loop
4) for each array, going backward from the solution as the root, build one level adjacency (to include all MOVEs)
5) if the input state is visited, return loop count
6) continue loop
Optimize by excluding states already visited when building adjacency sets
Sequence is possible when 1, 4th positions are of the same or 0, 1 positions are same.
Approach for sequence based on the moves given here:
Checking if a single position can be corrected or not.
By using few moves of A and few moves of B such that total moves is 4 we can achieve any moves on position 2. (A3 times and B1 time - moving 2 one time without changing anything else.)
Now we know that 2 can be changed independent of other positions. Using this and move D we can change 5 independent of others.
similarly.. using 5 and E change 3
Using 3 and F change 7
using 7 and H change 6.
Using 5, 6 and C we can change 1,4 together.
With A we can change 0,1 at the same time and using above 1, 4 at the same time.
If there is change in 0, 1 then we can use 1, 4 moves to match 0, 1 -- But only possible if 1, 4 are same here. Similarly matching 1, 4 possible by using A, with constrain that 0, 1 are same.
Lowest moves?
Don't have an approach but would see which side is present max in 8 positions and remove those.
If I need to correct 2 and 2 has to move 2 times to match to most common I write it as
(2A + 2B)
If 5 has to be changed 1 time then I will write it as three 2' (3A+B) moves and one D
Now for 2 moving two times + 5 moving 1 time. (2A+2B) + 3 * (3A+B) + D= 11A + 5B + D.
Any move multiplied by 4 can be removed.
So total moves for example taken is 3A+ B + D.
Does someone has better approach for finding low moves.
def distance(start, end):
dirs = "NESWNES"
si = dirs.index(start);
di = dirs.index(end, si);
return di-si;
def makeMove(move, state):
for x in range(8):
state[x] = state[x] + move[x];
if(state[x] == 4 ): state[x] = 0;
def codedistance(target, state):
dist = 0;
for x in range(8):
if target[x] == 0 :
dist = dist + 3 * state[x];
else:
dist = dist + abs(target[x] - state[x]);
return dist;
def choseNextDir(dirs):
dircount = {'N':0, 'E':0, 'W':0, 'S':0};
for x in dirs:
dircount[x] = dircount[x] + 1;
for y in sorted(dircount, key=dircount.get, reverse=True):
if(dircount[y] != 0):
yield y;
def MoveOrder(moves, distary):
movesorted = {};
orderedMoves = [];
for y in range(len(moves)):
move = moves[y];
sum = 0;
for x in range(8):
sum = sum + move[x] * distary[x];
movesorted[y] = sum;
for y in sorted(movesorted, key=movesorted.get, reverse=True):
if movesorted[y] != 0 :
orderedMoves.append(moves[y]);
return orderedMoves;
def play(orderedMoves, distary, state, moves):
moves1 = [];
for move in orderedMoves:
for x in range(4):
if (x > 0) :
makeMove(move, state);
moves.append(move)
if state == distary :
if(len(moves1) != 0 and len(moves1) < len(moves)):
return moves1;
else:
return moves;
else:
#based on an rough assumption that a wrong move will cost you 15 in distance -
#the codedistance function should be tuned further . this is just to optimize.
if(codedistance(distary, state) > 15 ):
break;
moves2 = play( orderedMoves[1:], distary, state[:], moves[:]);
if(len(moves2) > 0):
if(len(moves1) == 0 ):
moves1 = moves2;
elif len(moves1) > len(moves2):
moves1 = moves2;
return moves1;
def findMinMoves(dirSelector, moves, statueinit):
for target in dirSelector:
distary = [0,0,0,0,0,0,0,0];
for x in range(8):
distary[x] = distance(statueinit[x], target);
orderedMoves = MoveOrder(moves, distary );
state = [0,0,0,0,0,0,0,0];
mymoves = [];
mymoves = play(orderedMoves, distary, state, mymoves);
if(len(mymoves) > 0):
return mymoves;
#-------------------------------------------------------------
statueinit = "NNSEWSWN";
dirSelector = choseNextDir(statueinit);
moves =[[1,1,0,0,0,0,0,0],
[1,1,1,0,0,0,0,0],
[0,1,0,0,1,1,1,0],
[0,0,1,0,0,1,0,0],
[0,0,0,1,0,1,0,0],
[0,0,0,1,0,0,0,1],
[0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,1,1]];
print findMinMoves(dirSelector, moves, statueinit);
Assume the input : NNNEESSW
We will first find out the maximum occurrence of the direction, in our case it is N.
We will then put N =0 and find the number of moves to reach to north in clock-wise direction.
Hence making the array as : 00033221. Find the sum which comes out to be 11.
Now, if we look closely we can see that this actually is the worst case scenario of our approach, when the "farthest" statue (with value 3) holds second highest number.
And hence we don't need to put every direction as 0 and count correspondingly as the numbers will be rotating.
Lets say our algo of assuming N as 0 was wrong, lets consider E to be 0.
If 2 occurrences of 3 becomes 0 , we will loose 6 moves but then all other six positions will gain 1 move , making it +6. Hence we the result still remains 11.
For other scenarios as well the result can increase but will not decrease and hence we dont need BFS.
This solves the problem in O(n).
Brute force BFS solution in Java:
int minNumberOfMoves(String initialPosition) {
if (isSolved(initialPosition)) {
return 0;
}
List<boolean[]> actions = new LinkedList<boolean[]>();
actions.add(new boolean[] { true, true, false, false, false, false, false, false});
actions.add(new boolean[] { true, true, true, false, false, false, false, false});
actions.add(new boolean[] {false, true, false, false, true, true, true, false});
actions.add(new boolean[] {false, false, true, false, false, true, false, false});
actions.add(new boolean[] {false, false, false, true, false, true, false, false});
actions.add(new boolean[] {false, false, false, true, false, false, false, true});
actions.add(new boolean[] {false, false, false, false, false, true, false, true});
actions.add(new boolean[] {false, false, false, false, false, false, true, true});
Set<String> seenPositions = new HashSet<String>();
Set<String> currentPositions = new HashSet<String>();
Set<String> nextPositions = new HashSet<String>();
seenPositions.add(initialPosition);
currentPositions.add(initialPosition);
for (int moveCounter = 1; currentPositions.size() > 0; ++moveCounter) {
for (String current : currentPositions) {
for (boolean[] action : actions) {
String next = performAction(current, action);
if (!seenPositions.contains(next)) {
if (isSolved(next)) {
return counter;
}
seenPositions.add(next);
nextPositions.add(next);
}
}
}
currentPositions = nextPositions;
nextPositions = new HashSet<String>();
}
return -1;
}
String performAction(String position, boolean[] action) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < position.length(); ++i) {
if (action[i]) {
switch (position.charAt(i)) {
case 'N':
result.append('E');
break;
case 'E':
result.append('S');
break;
case 'S':
result.append('W');
break;
case 'W':
result.append('N');
break;
}
} else {
result.append(position.charAt(i));
}
}
return result.toString();
}
boolean isSolved(String s) {
for (int i = 1; i < s.length(); ++i) {
if (s.charAt(0) != s.charAt(i)) {
return false;
}
}
return true;
}
Implemented using Breadth-First Search in c#
static void Main(string[] args)
{
var moves = Moves(new Node(Console.ReadLine(), string.Empty, null));
if (moves != null)
{
foreach (var message in moves)
{
Console.WriteLine(message);
}
}
else
{
Console.WriteLine("-1");
}
}
private static IList<string> Moves(Node inputChars)
{
var possibleMoves = new Dictionary<string, int[]> {
{ "A", new int[] { 0, 1 } },
{ "B", new int[] { 0, 1, 2 } } ,
{ "C", new int[] { 1,4,5,6 } },
{ "D", new int[] { 2,5 } },
{ "E", new int[] { 3,5 } },
{ "F", new int[] { 3,7 } },
{ "G", new int[] { 5,7 } },
{ "H", new int[] { 6,7 } }
};
var BFSQueue = new Queue<Node>();
BFSQueue.Enqueue(inputChars);
while (BFSQueue.Count > 0)
{
if (AllCharsSame(inputChars.Value))
{
return inputChars.Path;
}
foreach (var key in possibleMoves.Keys)
{
var inputString = moveChars(inputChars.Value, possibleMoves[key]);
if (!BFSQueue.Any(node => node.Value == inputString))
{
BFSQueue.Enqueue(new Node(inputString, key, inputChars.Path));
}
}
inputChars = BFSQueue.Dequeue();
}
return null;
}
private static bool AllCharsSame(string inputChars)
{
for (int i = 1; i < inputChars.Length; i++)
{
if (inputChars[0] != inputChars[i])
{
return false;
}
}
return inputChars.Length > 0; // Incase inputChars is empty, return false, else true
}
private static string moveChars(string inputChars, int[] positions)
{
var inputCharArray = inputChars.ToCharArray();
for (int i = 0; i < positions.Length; i++)
{
inputCharArray[positions[i]] = Move90DegreeRight(inputCharArray[positions[i]]);
}
return new String(inputCharArray);
}
private static char Move90DegreeRight(char position)
{
var positions = new Dictionary<char,char>() { {'N', 'E'},{'E','S'},{'S','W'},{'W','N'}};
return positions[position];
}
public class Node
{
public Node(string value, string path, IList<string> parentPath = null)
{
if (Path == null)
{
Path = parentPath == null ? new List<string>() : new List<string>(parentPath);
}
Value = value;
if (!string.IsNullOrWhiteSpace(path))
{
Path.Add(path);
}
}
public string Value { get; set; }
public IList<string> Path { get; set; }
}
Similar to algolearner's answer. But use layer deep first. Also skipped circles.
package gao.zone.study;
import java.util.HashSet;
import java.util.Set;
import org.junit.Assert;
public class DirectionPuzzle {
private static enum Move {
A(new int[] {0, 1 }),
B(new int[] {0, 1, 2 }),
C(new int[] {1, 4, 5, 6 }),
D(new int[] {2, 5 }),
E(new int[] {3, 5 }),
F(new int[] {3, 7 }),
G(new int[] {5, 7 }),
H(new int[] {6, 7 });
final int[] positions;
Move(int[] pos) {
positions = pos;
}
}
private static class State {
final String directions;
State(String directions) {
this.directions = directions;
}
State move(Move m) {
char[] directions = this.directions.toCharArray();
for (int pos : m.positions) {
directions[pos] = rotate(directions[pos]);
}
return new State(new String(directions));
}
@Override
public String toString() {
return "State [" + directions + "]";
}
public boolean isSynchonized() {
return directions.matches("N+|E+|W+|S+");
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((directions == null) ? 0 : directions.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (directions == null) {
if (other.directions != null)
return false;
} else if (!directions.equals(other.directions))
return false;
return true;
}
}
public static void main(String[] args) {
Assert.assertEquals(0, moveCount("SSSSSSSS"));
Assert.assertEquals(1, moveCount("WWNNNNNN"));
Assert.assertEquals(6, moveCount("NNSEWSWN"));
}
public static char rotate(char direction) {
switch (direction) {
case 'N':
return 'E';
case 'E':
return 'S';
case 'S':
return 'W';
case 'W':
return 'N';
default:
throw new AssertionError();
}
}
private static int moveCount(String directions) {
State state = new State(directions);
if (state.isSynchonized()) {
return 0;
}
int step = 0;
Set<State> befores = new HashSet<State>();
Set<State> visited = new HashSet<State>();
befores.add(state);
visited.add(state);
while (true) {
if (befores.isEmpty()) {
return -1;// never possible.
}
State[] array = befores.toArray(new State[0]);
befores.clear();
for (State before : array) {
for (Move m : Move.values()) {
State next = before.move(m);
if (next.isSynchonized()) {
return ++step;
}
if (visited.add(next)) {
// not visited before.
befores.add(next);
}
}
}
++step;
}
}
}
This is a linear algebra problem with a bit of a twist.
Let North=0, East=1, South=2, West=3.
Then construct a vector V from the original orientations of the statues. E.g. NNN is the vector <0,0,0>.
Each of the allowed "moves" now corresponds to a vector. E.g. turning statues 1 and 2 "clockwise" can be thought of as adding the vector <1,1,0>.
The catch is that we must work modulo 4.
So we want to find an integers solution to the system
V+c0*M0+c1*M1+c2*M2+...+=W,
where V is the vector of original orientations, the Mi's are the vectors of the allowed moves, the ci's are the coefficients of the Mi's, and W is the vector <4x0+k,4x1+k,4x2+k,...>, where the xi's are any positive integers, and k is 0, 1, 2, or 3.
It can be solved more easily right. Result can be one of the following "ssss" or "eeee" or "nnnn" or "wwww". Cost for all these can be easily calculated and the solution is nothing but the min of these costs
- beginner August 19, 2014