## Microsoft Interview Question for SDE-2s

• 0

Country: United States
Interview Type: Phone Interview

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

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:

- 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.

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

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 != tpc.s)
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 != pc.s)
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.length; c++) {
switch (l) {
case 0:
System.out.print(" " + b[r][c].s + " ");
break;
case 1:
System.out.print(b[r][c].s + " " + b[r][c].s);
break;
case 2:
System.out.print(" " + b[r][c].s + " ");
}
}
System.out.println();
}
}
}
}``````

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

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

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.length;
int c = pos % b.length;
if (r < 0 || r >= b.length || c < 0 || c >= b.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;
}
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 != tpc.s)
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 != pc.s)
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.length; c++) {
switch (l) {
case 0:
System.out.print(" " + b[r][c].s + " ");
break;
case 1:
System.out.print(b[r][c].s + " " + b[r][c].s);
break;
case 2:
System.out.print(" " + b[r][c].s + " ");
}
}
System.out.println();
}
}
}
}``````

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

//// 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" },
{ 4, "Club" }
};

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

This solution doesn't match the picture?
i.e. The piece in your solution: 7 D 2, R 1, U -3, L -4
Cannot be seen in the photo, yours has an edge with each shape, but no such piece is visible in the photo...

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

1/u= ka solution chahiye

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.