## Microsoft Interview Question for SDE1s

• 1
of 1 vote

Interview Type: In-Person

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

This is not a very good question because it is not clear. By that I mean the function that gives you all the positions that the horse can reach, it is not clear the cost to a particular position. Is it always going to be 1 or it can be something else? If it is always 1, then all you need to do is use BFS. And once you reach the ending point, you are done. If it give you the associate cost for the reachable position and they are always positive cost, then you can use Dijkstra algorithms. Otherwise, it is going to be too hard for an interview question to think and code. Especially this is only SDE1 position

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

The cost is just move and every move always cost 1 according to the context. The important thing here is to show how to do BFS and return the path with the function which returns the next possible positions.

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

An algorithm using BFS.

``````#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct pos {
int x, y;
};

namespace std {

// hash function for unordered_map<pos,pos>
template <>
struct hash<pos> : private hash<long long> {
size_t operator()(const pos& val) const {
return hash<long long>::operator()(((long long)val.x << 32) | val.y);
}
};

// equality function for unordered_map<pos,pos>
bool operator==(const pos& pos1, const pos& pos2) {
return pos1.x == pos2.x && pos1.y == pos2.y;
}

bool operator!=(const pos& pos1, const pos& pos2) {
return !(pos1 == pos2);
}

ostream& operator<<(ostream& os, const pos& val) {
os << "(" << val.x << "," << val.y << ")";
return os;
}

}

auto find_shortest_path = [](int N, pos spos, pos epos) {
vector<vector<bool>> visited(N, vector<bool>(N, false));
// Here I assume horse can move up/down/left/right at each position
auto get_next_pos = [&](pos cpos) {
vector<pos> npos;
if (cpos.x-1 >= 0 && !visited[cpos.x-1][cpos.y]) {
npos.push_back({cpos.x-1, cpos.y});
}
if (cpos.x+1 < N && !visited[cpos.x+1][cpos.y]) {
npos.push_back({cpos.x+1, cpos.y});
}
if (cpos.y-1 >= 0 && !visited[cpos.x][cpos.y-1]) {
npos.push_back({cpos.x, cpos.y-1});
}
if (cpos.y+1 < N && !visited[cpos.x][cpos.y+1]) {
npos.push_back({cpos.x, cpos.y+1});
}
return npos;
};
auto get_path = [&]() {
queue<pos> q;
q.push(spos);
visited[spos.x][spos.y] = true;
// map to save path
unordered_map<pos,pos> path;
while (!q.empty()) {
auto cpos = q.front();
// arrive end position
if (cpos == epos) {
vector<pos> ret;
ret.push_back(cpos);
// path can be composed by following a path
// from end position to start position
while (cpos != spos) {
auto ppos = path[cpos];
ret.push_back(ppos);
cpos = ppos;
}
// finally reverse it
reverse(ret.begin(), ret.end());
return ret;
}
q.pop();
for (auto npos : get_next_pos(cpos)) {
q.push(npos);
visited[npos.x][npos.y] = true;
path[npos] = cpos;
}
}
return vector<pos>();
};

return get_path();
};

int main() {
for (auto pos : find_shortest_path(5, {0,0}, {4,4})) {
cout << pos << " ";
}
cout << endl;
return 0;
}``````

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

Horse moves in L shape, accordingly your get_next_pos function changes. Rest looks fine.

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

``````// a java implementation of bfs for this problem.

class Position {
int location;  // number the squares on the board from 1 to 64.
Position pred;  // the previous square in BFS.  initialized to null.

public List<Position> getMoves(); // given in problem statement
}

public static List<Position> minPath(Position start, Position end) {
q.enqueue(start);
while (!q.isEmpty() ) {
Position p = q.dequeue();
for (Position x : p.getMoves() ) {
if (x.pred == null) {
x.pred = p;
q.enqueue(x);
}
if (x  == end) {
return getPath(start, end);
}
}
}
return null; // there was an error if this return statement gets called
}

public List<Position> getPath(Position start, Position end) {
Stack s = new Stack();
s.push(end);
while (s.peek() != null) {
s.push(s.peek().pred);
}
ArrayList<Position> thing = new ArrayList<Position>();
for (Position p : s) {
}
return thing;
}``````

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

Either BFS or A* would work for this.

Implementing A*.
f(x) = g(x) + h(x) where
g(x) = number of moves completed so far
h(x) = half the cardinal distance between checked position and the desired end

``````//assuming this is the method that generates valid moves
public static Collection<int[]> getNextMoves(int[] position);

static class Move{
int[] position;
Move lastMove;
int gCost;
int hCost;
Move(int[] position, Move lastMove, int gCost, int hCost){
this.position = position;
this.lastMove = lastMove;
this.gCost = gCost;
this.hCost = hCost;
}
}

public static List<int[]> getPath(int[] start, int[] end){
if(start == null || end == null){
throw new NullPointerException();
}
if(start.length != 2 || end.length != 2){
throw new IllegalArgumentException();
}

PriorityQueue<Move> moveList = new PriorityQueue<Move>(
new Comparator<Move>(){
public int compare(Move m1, Move, m2){
int fM1 = m1.gCost + m1.hCost;
int fM2 = m2.gCost + m2.hCost;
return fM1-fM2;
}
});

Move solution = null;
while(!moveList.isEmpty()){
Move thisMove = moveList.poll();
int[] thisMovePos = thisMove.position;
if(thisMovePos == end && thisMovePos == end){
solution = thisMove;
break;
}
for(int[] nextPos : getNextMoves(thisMovePos)){
moveList.add(new Move(nextPos, thisMove, thisMove.gCost+1, computeHCost(nextPos, end) );
}
}
if(solution != null){
while(solution != null){
solution = solution.lastMove;
}
return results;
}
return null;
}

private static int computeHCost(int[] pos1, int[] pos2){
return ( Math.abs(pos1 - pos2) + Math.abs(pos1 - pos2) ) >>> 1;
}``````

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

This is a dynamic Problem, it can be solved using the Top Down + memoization

``````namespace ChessBoardKnightMoves
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(GetMinimumMoves(64, 54, 0, new List<int>()));
}

// Define other methods and classes here
static int ChessBoardDimension = 8;
static Dictionary<int, int> memizedData = new Dictionary<int, int>();

static int GetMinimumMoves(int currentPosition, int endPosition, int numberOfMoves, List<int> positionVisited)
{
if (currentPosition == endPosition)
{
return numberOfMoves;
}

if (memizedData.ContainsKey(currentPosition))
return memizedData[currentPosition];

int minMoves = 100000;
var possibleMoves = GetPossibleMoves(currentPosition);

foreach (var position in possibleMoves)
{
if (!positionVisited.Any(p1 => p1 == position))
{
List<int> p = new List<int>(positionVisited.ToArray());
minMoves = Math.Min(minMoves, numberOfMoves + GetMinimumMoves(position, endPosition, 1, p));
}
}

memizedData[currentPosition] = minMoves;
return minMoves;
}

static List<int> GetPossibleMoves(int currentPosition)
{
List<int> possibleMoves = new List<int>();
int columnPosition = 0;

columnPosition = currentPosition % ChessBoardDimension;
if (columnPosition == 0)
columnPosition = ChessBoardDimension;

if (columnPosition < ChessBoardDimension)
{
possibleMoves.Add(currentPosition + 1 + (2 * ChessBoardDimension));
possibleMoves.Add(currentPosition + 1 - (2 * ChessBoardDimension));

if (ChessBoardDimension - columnPosition >= 2)
{
}
}

if (columnPosition > 1)
{
possibleMoves.Add(currentPosition - 1 + (2 * ChessBoardDimension));
possibleMoves.Add(currentPosition - 1 - (2 * ChessBoardDimension));

if (columnPosition > 2)
{
}
}

return possibleMoves.Where(p => p > 0 && p <= (ChessBoardDimension * ChessBoardDimension)).ToList();
}
}
}``````

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

BFS looks ideal.

``````def solution(startpos, endpos):
visited = set()
queue = [ [startpos] ]
while len(queue) > 0:
pos = queue.pop(0) # TODO: not O(1), use doubly-linked lists
for nextpos in next_possible_moves(pos):
if nextpos in visited: continue
if nextpos == endpos:
return reversed([nextpos] + pos)
queue.append([nextpos] + pos)``````

Popping from the head of a native Python list may be O(N), but I'm using the native lists for syntactical sugar. In practice you'd want to use doubly-linked lists for O(1) dequeue.

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

Yeah, looks like I want to use deque

``````from collections import deque

queue = deque()
queue.append([startpos])
# ^ replaces queue = [ [startpos] ]

pos = queue.popleft()
# ^ replaces queue.pop(0)

queue.append([nextpos] + pos)
# ^ replaces queue.append([nextpos] + pos)``````

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

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

C++ solution is made with BFS and memoization. I keep track of the previous move that got me to the current square. I then move backwards from the end to print out the moves that were made.

We have to make sure that we don't make any moves that would cause the arrays to go out of bounds, hence all of the if statements.

``````struct Coord
{
int x = 0;
int y = 0;
Coord(int initX, int initY) :x(initX), y(initY){}
Coord(){}
bool visited = false;
};

void MinMoves(Coord start, Coord end, int size)
{
vector<vector<Coord>> minMoves(size, vector<Coord>(size, Coord()));
queue<Coord> moves;
start.visited = true;
moves.push(start);

while (!moves.empty())
{
Coord move = moves.front();
move.visited = true;
moves.pop();

if (move.x == end.x && move.y == end.y)
break;
if (move.x >= 2 && move.y >= 1 && !minMoves[move.x - 2][move.y - 1].visited)
{
minMoves[move.x - 2][move.y - 1] = move;
moves.push(Coord(move.x - 2, move.y - 1));
}
if (move.x >= 1 && move.y >= 2 && !minMoves[move.x - 1][move.y - 2].visited)
{
minMoves[move.x - 1][move.y - 2] = move;
moves.push(Coord(move.x - 1, move.y - 2));
}

if (move.x >= 2 && move.y <= size - 2 && !minMoves[move.x - 2][move.y + 1].visited)
{
minMoves[move.x - 2][move.y + 1] = move;
moves.push(Coord(move.x - 2, move.y + 1));
}
if (move.x >= 1 && move.y <= size - 3 && !minMoves[move.x - 1][move.y + 2].visited)
{
minMoves[move.x - 1][move.y + 2] = move;
moves.push(Coord(move.x - 1, move.y + 2));
}

if (move.x <= size - 3 && move.y >= 1 && !minMoves[move.x + 2][move.y - 1].visited)
{
minMoves[move.x + 2][move.y - 1] = move;
moves.push(Coord(move.x + 2, move.y - 1));
}
if (move.x <= size - 2 && move.y >= 2 && !minMoves[move.x + 1][move.y - 2].visited)
{
minMoves[move.x + 1][move.y - 2] = move;
moves.push(Coord(move.x + 1, move.y - 2));
}

if (move.x <= size - 3 && move.y <= size - 2 && !minMoves[move.x + 2][move.y + 1].visited)
{
minMoves[move.x + 2][move.y + 1] = move;
moves.push(Coord(move.x + 2, move.y + 1));
}
if (move.x <= size - 2 && move.y <= size - 3 && !minMoves[move.x + 1][move.y + 2].visited)
{
minMoves[move.x + 1][move.y + 2] = move;
moves.push(Coord(move.x + 1, move.y + 2));
}
}

Coord cur = end;
while (cur.x != start.x && cur.y != start.y)
{
cout << cur.x << ", " << cur.y << endl;
cur = minMoves[cur.x][cur.y];
}

cout << cur.x << ", " << cur.y << endl;
}``````

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

Either BFS, or DP works. Should be noted that both are O(N^2) where N is the side length of the board. BFS actually gives the exact same effect as doing a bottom-up DP approach. Top-down DP might not be (easily) doable since the provided function gives all locations reachable from a given position, and not the other way around.

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

Simple application of BFS.

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.