Microsoft Interview Question SDE1s
Interview Type: In-Person
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;
}
// 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) {
LinkedList<Position> q = new LinkedList<Position>();
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) {
thing.add(p);
}
return thing;
}
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;
}
});
moveList.add(new Move(start, null, 0, 0));
Move solution = null;
while(!moveList.isEmpty()){
Move thisMove = moveList.poll();
int[] thisMovePos = thisMove.position;
if(thisMovePos[0] == end[0] && thisMovePos[1] == end[1]){
solution = thisMove;
break;
}
for(int[] nextPos : getNextMoves(thisMovePos)){
moveList.add(new Move(nextPos, thisMove, thisMove.gCost+1, computeHCost(nextPos, end) );
}
}
if(solution != null){
LinkedList<int[]> results = new LinkedList<int[]>();
while(solution != null){
results.addFront(solution.position);
solution = solution.lastMove;
}
return results;
}
return null;
}
private static int computeHCost(int[] pos1, int[] pos2){
return ( Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]) ) >>> 1;
}
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>()));
Console.Read();
}
// 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());
p.Add(position);
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)
{
possibleMoves.Add(currentPosition + 2 + ChessBoardDimension);
possibleMoves.Add(currentPosition + 2 - ChessBoardDimension);
}
}
if (columnPosition > 1)
{
possibleMoves.Add(currentPosition - 1 + (2 * ChessBoardDimension));
possibleMoves.Add(currentPosition - 1 - (2 * ChessBoardDimension));
if (columnPosition > 2)
{
possibleMoves.Add(currentPosition - 2 + ChessBoardDimension);
possibleMoves.Add(currentPosition - 2 - ChessBoardDimension);
}
}
return possibleMoves.Where(p => p > 0 && p <= (ChessBoardDimension * ChessBoardDimension)).ToList();
}
}
}
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[0]):
if nextpos in visited: continue
visited.add(nextpos)
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.
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;
}
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.
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
- hiuhchan December 12, 2014