Microsoft Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
Bruteforce solution through recursion: O(N!) (I dont think given board has a solution)
for each row and each col from left to right, through recursion checks all the possible pieces
Through recursion takes each piece for rach
List<PuzPc> list = new ArrayList<>(pcs);
PuzPc tpc;
// check piece above
if (r - 1 >= 0) {
tpc = b[r - 1][c];
// filter the bottom part of above piece
for (PuzPc pc : pcs)
if (pc.s[0] != tpc.s[2])
list.remove(pc);
}
//check piece to the left
if (c - 1 >= 0) {
Iterator<PuzPc> iter = list.iterator();
PuzPc pc;
tpc = b[r][c - 1];
while (iter.hasNext()) {
pc = iter.next();
if (tpc.s[1] != pc.s[3])
iter.remove();
}
}
return list;
}
public void printBoard(PuzPc b[][]) {
for (int r = 0; r < b.length; r++) {
for (int l = 0; l < 3; l++) {
for (int c = 0; c < b[0].length; c++) {
switch (l) {
case 0:
System.out.print(" " + b[r][c].s[0] + " ");
break;
case 1:
System.out.print(b[r][c].s[3] + " " + b[r][c].s[1]);
break;
case 2:
System.out.print(" " + b[r][c].s[2] + " ");
}
}
System.out.println();
}
}
}
}
Bruteforce solution through recursion: O(N!) (I dont think given board has a solution)
for each row and each col from left to right, through recursion checks all the possible pieces
public class SolvePuzzle {
public static void main(String[] args) {
SolvePuzzle sp = new SolvePuzzle();
List<PuzPc> pcs = new ArrayList<>();
int r = 3, c = 3;
//for each piece start from the top in clock wise
pcs.add(new PuzPc('d', 'h', 'h', 'd'));
pcs.add(new PuzPc('s', 'h', 'c', 's'));
pcs.add(new PuzPc('c', 'd', 'd', 'c'));
pcs.add(new PuzPc('h', 'c', 'h', 's'));
pcs.add(new PuzPc('h', 'c', 'c', 'd'));
pcs.add(new PuzPc('d', 'h', 'c', 'c'));
pcs.add(new PuzPc('d', 's', 'h', 's'));
pcs.add(new PuzPc('d', 's', 'd', 'h'));
pcs.add(new PuzPc('s', 's', 'c', 'h'));
PuzPc b[][] = new PuzPc[r][c];
if (sp.recFind(b, new boolean[r][c], 0, pcs))
sp.printBoard(b);
else
System.out.println("cannot solve puzzle");
}
public boolean recFind(PuzPc b[][], boolean filled[][], int pos,
List<PuzPc> pcs) {
int r = pos / b[0].length;
int c = pos % b[0].length;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length
|| filled[r][c])
return true;
List<PuzPc> list = findFits(b, r, c, pcs);
if (list.isEmpty())
return false;
filled[r][c] = true;
for (PuzPc fpc : list) {
pcs.remove(fpc);
b[r][c] = fpc;
if (recFind(b, filled, pos + 1, pcs))
return true;
b[r][c] = null;
pcs.add(fpc);
}
filled[r][c] = false;
return false;
}
public List<PuzPc> findFits(PuzPc b[][], int r, int c, List<PuzPc> pcs) {
List<PuzPc> list = new ArrayList<>(pcs);
PuzPc tpc;
// check piece above
if (r - 1 >= 0) {
tpc = b[r - 1][c];
// filter the bottom part of above piece
for (PuzPc pc : pcs)
if (pc.s[0] != tpc.s[2])
list.remove(pc);
}
//check piece to the left
if (c - 1 >= 0) {
Iterator<PuzPc> iter = list.iterator();
PuzPc pc;
tpc = b[r][c - 1];
while (iter.hasNext()) {
pc = iter.next();
if (tpc.s[1] != pc.s[3])
iter.remove();
}
}
return list;
}
public void printBoard(PuzPc b[][]) {
for (int r = 0; r < b.length; r++) {
for (int l = 0; l < 3; l++) {
for (int c = 0; c < b[0].length; c++) {
switch (l) {
case 0:
System.out.print(" " + b[r][c].s[0] + " ");
break;
case 1:
System.out.print(b[r][c].s[3] + " " + b[r][c].s[1]);
break;
case 2:
System.out.print(" " + b[r][c].s[2] + " ");
}
}
System.out.println();
}
}
}
}
//// Solution!!
//// 7 D 2, R 1, U -3, L -4 8 D 3, R 3, U -4, L -1 9 D 2, R 3, U -1, L -3
//// 4 D 2, R -1, U -2, L 3 5 D 4, R -1, U -3, L 1 6 D 3, R -3, U -2, L 1
//// 1 D 1, R 2, U -2, L -1 2 D 2, R 4, U -4, L -2 3 D 1, R 3, U -3, L -4
// negative int is a hole with that shape
// puzzle is assumed to end up a 3 by 3 square
public static Dictionary<int, string> Mapping = new Dictionary<int, string>
{
{ 1, "Heart" },
{ 2, "Diamond" },
{ 3, "Spade" },
{ 4, "Club" }
};
This problem provides a good opportunity to prove skill with simple data structures and trying permutations via recursion.
Here's a pseudocode outline for a recursive solution:
Board FindSolution(Board board, IList<Piece> remainingPieces, int x, int y) { // base case: if there are no remaining pieces, we've filled the board, // so return it as a solution if (!remainingPieces.Any()) return board; // iterate over the set of remaining pieces that fit in the first empty space foreach (var p in remainingPieces.Where(p => PieceFits(p, board, x, y))) { // recurse by placing p at x,y var boardWithPlacedPiece = PlacePiece(p, board, x, y); var newRemainingPieces = remainingPieces.Where(z => z.id != p.id); var solution = FindSolution(boardWithPlacedPiece, newRemainingPieces, GetNextPosition(x, y); // this implementation stops as soon as we find any solution if (solution != null) return solution; } return null; }A few notes about things not shown:
- N July 02, 2015- A key observation is that the shapes on each side of each piece are symmetrical, meaning that each piece has 8 possible orientations (4 rotations for each piece as shown, and 4 more with the piece flipped over). In this solution, a Piece has four Sides, each one consisting of a Shape and a bool called IsConvex, and also has a unique identifier. This is because the set of available pieces includes duplicates of each actual piece - one for each orientation. Each time we recurse, we remove all instances of a given piece ID from the set of available pieces.
- PieceFits simply checks neighboring x,y positions. A piece fits if each neighboring spot is empty, is out of bounds of the puzzle, or if the two facing sides have matching shapes and opposite IsConvex values.
- All data structures are immutable, and PlacePiece returns a new Board object (which I implemented as a Piece[3,3]). This makes managing values within the recursion very simple and also makes the solution trivially parallelizable - the foreach could be swapped out for a Parallel.ForEach with very little work.