Facebook Interview Question
SDE1sCountry: United States
int shortestStepsWCheese(int[][] m, int[] target) {
List<List<int[]>> ans = new ArrayList<>();
List<int[]> partial = new ArrayList<>();
int cheeseCount = 0;
dfsCheese(m, target, new int[] {0, 0}, partial, ans, cheeseCount);
int min = Integer.MAX_VALUE;
for (List l : ans) {
min = Math.min(min, l.size());
}
return min;
}
private void dfsCheese(
int[][] m,
int[] target,
int[] source,
List<int[]> partial,
List<List<int[]>> ans,
int cheeseUsed) {
if (source == target) {
if (cheeseUsed == 0) {
ans.add(new ArrayList<>(partial));
}
return;
}
if (m[source[0]][source[1]] == 1) {
return;
}
if (m[source[0]][source[1]] == 2) {
cheeseUsed--;
}
// dfs(m, target, source)
for (int dir[] : dirs) {
int nextR = source[0] + dir[0];
int nextC = source[1] + dir[1];
if (nextR >= 0 && nextR < m.length && nextC >= 0 && nextC < m[0].length) {
partial.add(new int[] {nextR, nextC});
dfsCheese(m, target, new int[] {nextR, nextC}, partial, ans, cheeseUsed);
partial.remove(partial.size() - 1);
}
}
}
dfs with backtracking
int shortestStepsWCheese(int[][] m, int[] target) {
List<List<int[]>> ans = new ArrayList<>();
List<int[]> partial = new ArrayList<>();
int cheeseCount = 0;
dfsCheese(m, target, new int[] {0, 0}, partial, ans, cheeseCount);
int min = Integer.MAX_VALUE;
for (List l : ans) {
min = Math.min(min, l.size());
}
return min;
}
private void dfsCheese(
int[][] m,
int[] target,
int[] source,
List<int[]> partial,
List<List<int[]>> ans,
int cheeseUsed) {
if (source == target) {
if (cheeseUsed == 0) {
ans.add(new ArrayList<>(partial));
}
return;
}
if (m[source[0]][source[1]] == 1) {
return;
}
if (m[source[0]][source[1]] == 2) {
cheeseUsed--;
}
// dfs(m, target, source)
for (int dir[] : dirs) {
int nextR = source[0] + dir[0];
int nextC = source[1] + dir[1];
if (nextR >= 0 && nextR < m.length && nextC >= 0 && nextC < m[0].length) {
partial.add(new int[] {nextR, nextC});
dfsCheese(m, target, new int[] {nextR, nextC}, partial, ans, cheeseUsed);
partial.remove(partial.size() - 1);
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
just for completeness, here the animated (console, take PS cons on windows) just to demonstrate how the solution would actually look like. Note that the Traveling Salesman part is implemented naive, so just adding 9 cakes will be already slow as it checks 362'000 routes. Of course there are much better implementations. But this shows the problem and a naive solution. It's fun, the real fun is optimizing it...
#include <vector>
#include <unordered_set>
#include <queue>
#include <cassert>
#include <list>
#include <iostream>
#include <string>
#include <thread>
using namespace std;
struct Point
{
int x_, y_;
bool operator== (const Point& rhs) const { return rhs.x_ == x_ && rhs.y_ == y_; }
bool operator!= (const Point& rhs) const { return !(*this == rhs); }
};
constexpr char toLower(char c) { return c >= 'A' && c <= 'Z' ? c - 'A' + 'a' : c; }
void clearScreen() { cout << "\033[2J\033[" << 1 << ";" << 1 << "H"; }
void printAt(int c, int r, const string& str) { cout << "\033[" << r << ";" << c << "H" << str; }
class CockieSolver
{
string field_;
int m_; // matrix number of columns (x)
int n_; // matrix number of rows (y)
// coordinate of all destinations, destinations are {start, all cookies, end=friend}
vector<Point> destinations_;
vector<vector<int>> destDist_; // all pair distances of paths among destinations
// paths between all pair of destinations (memory wasting, due to lazy programmer)
vector<vector<list<Point>>> destPath_;
const pair<int, int> MOVES[4]{ {0, 1}, { 1,0 }, { 0,-1 }, { -1,0 } }; // Manhatten moves
public:
// 'c' denotes a cookie, ' ' moveable, '#' wall, 'F' friend to finish,
// 'S' start (0,0) in the problem statement
CockieSolver(string&& field) : field_(field)
{
parseField();
}
void solveAndPrint()
{
if (!findAllPairShortesPath()) {
cout << "there are cookies I can't get, abort" << endl;
return;
}
auto bestRoute = findShortestRoute();
clearScreen();
cout << "solved the matrix with path length " << bestRoute.first << endl;
cout << field_ << endl;
for (int i = 1; i < bestRoute.second.size(); i++) {
int from = bestRoute.second[i-1];
int to = bestRoute.second[i];
for (const Point& p : destPath_[from][to]) {
printAt(p.x_ + 1, p.y_ + 2, "*");
this_thread::sleep_for(200ms);
}
}
printAt(0, n_ + 2, "press any key");
getchar();
}
private:
// crazy O((destinations_.size() - 2)!) solution that tries all possible routes to
// get all cheese cakes
pair<int, vector<int>> findShortestRoute()
{
unordered_set<int> usedDests;
vector<int> bestRoute;
vector<int> curRoute;
int bestRouteLen = numeric_limits<int>::max();
curRoute.push_back(0); // "start at start"
usedDests.insert(0); // can't take start anymore
findShortestRouteRec(curRoute, 0, usedDests, bestRoute, bestRouteLen);
return{ bestRouteLen, bestRoute };
}
void findShortestRouteRec(vector<int>& curRoute, int curRouteLen, unordered_set<int>& usedDests,
vector<int>& bestRoute, int& bestRouteLen)
{
if (curRoute.size() == destinations_.size() - 1) {
curRouteLen += destDist_[curRoute.back()][destDist_.size() - 1]; // end is fixed
if (curRouteLen < bestRouteLen) {
bestRoute = curRoute;
bestRoute.push_back(destDist_.size() - 1);
bestRouteLen = curRouteLen;
}
}
for (int next = 1; next < destinations_.size() - 1; ++next) {
if (usedDests.find(next) != usedDests.end()) continue; // can't use it
usedDests.insert(next);
curRouteLen += destDist_[curRoute.back()][next];
curRoute.push_back(next);
findShortestRouteRec(curRoute, curRouteLen, usedDests, bestRoute, bestRouteLen);
curRoute.pop_back();
curRouteLen -= destDist_[curRoute.back()][next];
usedDests.erase(next);
}
}
// most primitive implementation, after this step, the distance between each
// destination is known as well as the path (how ever primitive this is, the bottle
// neck is to build the route
bool findAllPairShortesPath()
{
// in a undirected sparse graph, allpair shortest path can be done using |V| times
// BFS. That's okay, there are improvements although, using dual source BFS,
// A* etc. It will limit the number of vertices we need to discover for each pair
int destCt = destinations_.size();
destDist_ = vector<vector<int>>(destCt, vector<int>(destCt, numeric_limits<int>::max()));
destPath_ = vector<vector<list<Point>>>(destCt, vector<list<Point>>(destCt));
for (int start = 0; start < destCt; start++) { // for all destination nodes
// this is shortest path on the map between the coordinates of start
// and all fields of the map. This will tell us, how far are the other
// destinations from that start destination
vector<vector<int>> mapDist(m_, vector<int>(n_, numeric_limits<int>::max()));
vector<vector<Point>> mapParent(m_, vector<Point>(n_, { -1, -1 }));
Point startPt = destinations_[start];
mapDist[startPt.x_][startPt.y_] = 0; // start with 0 distance on map
deque<Point> q({ destinations_[start] });
while (!q.empty()) {
Point cur = q.back(); q.pop_back();
int curDist = mapDist[cur.x_][cur.y_]; // distance of curPt from start
for (const auto& move : MOVES) {
Point next = Point{ cur.x_ + move.first, cur.y_ + move.second };
if (canMove(next) && mapDist[next.x_][next.y_] == numeric_limits<int>::max()) { // not yet visited
mapParent[next.x_][next.y_] = cur;
mapDist[next.x_][next.y_] = curDist + 1;
q.push_front(next);
}
}
}
// read out for all pairs (start, end) the distance from start to end
// backtrack the path as well (total memory nonsense of course, but
// for simplicity to later print the path)
for (int end = 0; end < destCt; ++end) {
Point destPt = destinations_[end];
destDist_[start][end] = mapDist[destPt.x_][destPt.y_];
if (mapDist[destPt.x_][destPt.y_] == numeric_limits<int>::max()) {
return false; // can't reach this point, no solution
}
list<Point> path;
while (destPt != startPt) {
path.push_front(destPt);
destPt = mapParent[destPt.x_][destPt.y_];
}
destPath_[start][end] = move(path);
}
}
}
inline bool canMove(const Point& pt) const {
return pt.x_ >= 0 && pt.y_ >= 0 && pt.x_ < m_ && pt.y_ < n_ && field_[pt.y_ * (m_+1) + pt.x_] != '#';
};
// parse string field
void parseField() {
m_ = -1;
n_ = 0;
destinations_.clear();
destinations_.push_back({-1,-1}); // start
Point end{ -1, -1 };
int pos = 0;
int j = 0;
while (pos < field_.length()) {
int i = 0;
while (pos < field_.length() && field_[pos] != '\n') { // only \n, no \n\r etc...
switch (toLower(field_[pos])) {
case 'c': // cookie
destinations_.push_back({ i, j });
break;
case 's':
destinations_[0] = { i, j };
break;
case 'f':
end = { i, j };
break;
}
pos++;
i++;
}
assert(m_ == -1 || m_ == i); // each j must contain same # of iums
m_ = i;
n_++;
j++;
pos++;
}
destinations_.push_back(end); // end is the last destination
assert(destinations_.front().x_ >= 0 && destinations_.back().x_ >= 0); // start and end must be set
}
};
int main()
{
CockieSolver cs(
"S C \n"
"### ######### \n"
" C # \n"
" # \n"
" C C## # F \n"
"## #### # \n"
" C # C \n"
" ##### # \n"
" C \n");
cs.solveAndPrint();
}
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
public class CheeseMaze
{
public static void main(String args[])
{
int width = 10;
int height = 20;
int[][] cheeseCells = { { 5, 3 }, { 4, 3 }, { 7, 11 } };
int[][] blockCells = { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } };
int[] anotherPerson = { 8, 17 };
CheeseMaze c = new CheeseMaze();
int[][] grid = c.createGrid(width, height, cheeseCells, blockCells, anotherPerson);
Result result = c.findCheese(grid, anotherPerson);
System.out.println(result);
}
public Result findCheese(int[][] grid, int[] anotherPerson)
{
boolean[][] visited = new boolean[grid.length][grid[0].length];
return findCheeseHelper(grid, visited, anotherPerson);
}
private Result findCheeseHelper(int[][] grid, boolean[][] visited, int[] anotherPerson)
{
int[] x = {0, 0, -1, 1};
int[] y = {-1, 1, 0, 0};
Queue<Integer[]> next = new LinkedList<>();
Queue<Integer[]> curr = null;
next.offer(new Integer[]{0,0});
int stepsCount = 0;
int globalStepsCount = 0;
int cheeseCount = 0;
int[] lastCheese = new int[2];
while(!next.isEmpty())
{
curr = next;
next = new LinkedList<>();
while(!curr.isEmpty())
{
Integer[] temp = curr.poll();
if(!visited[temp[0]][temp[1]])
{
visited[temp[0]][temp[1]] = true;
if(grid[temp[0]][temp[1]]==2)
{
globalStepsCount += stepsCount;
stepsCount = 0;
cheeseCount++;
lastCheese[0] = temp[0];
lastCheese[1] = temp[1];
next = new LinkedList<>();
curr = new LinkedList<>();
}
for(int i=0;i<x.length;i++)
{
int r = temp[0] + x[i];
int c = temp[1] + y[i];
if(isSafe(grid, r, c, visited, anotherPerson))
{
next.offer(new Integer[]{r, c});
}
}
}
}
stepsCount++;
}
System.out.println(cheeseCount + " : "+ stepsCount + " : "+globalStepsCount);
Result r = new Result();
r.totalSteps = Math.abs(lastCheese[0]-anotherPerson[0])+Math.abs(lastCheese[1]-anotherPerson[1]) + globalStepsCount;
r.cheeseCount = cheeseCount;
return r;
}
private boolean isSafe(int[][] grid, int row, int col, boolean[][] visited, int[] anotherPerson)
{
//System.out.println(row + " : " + col );
if(row < 0 ||
row >= grid.length ||
col < 0 ||
col >= grid[row].length ||
grid[row][col]==0 ||
visited[row][col] ||
(row==anotherPerson[0]&&col==anotherPerson[1]))
{
return false;
}
return true;
}
private int[][] createGrid(int width,
int height,
int[][] cheeseCells,
int[][] blockCells,
int[] anotherPerson)
{
int[][] grid = new int[width][height];
for(int i=0;i<grid.length;i++)
{
Arrays.fill(grid[i], 1);
}
for(int i=0;i<cheeseCells.length;i++)
{
grid[cheeseCells[i][0]][cheeseCells[i][1]] = 2;
}
for(int i=0;i<blockCells.length;i++)
{
grid[blockCells[i][0]][blockCells[i][1]] = 0;
}
grid[anotherPerson[0]][anotherPerson[1]]=3;
for(int i=0;i<grid.length;i++)
{
System.out.println(Arrays.toString(grid[i]));
}
return grid;
}
}
class Result
{
int totalSteps;
int cheeseCount;
public String toString()
{
return "totalSteps: "+ totalSteps + " cheeseCount: " + cheeseCount;
}
}
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
public class CheeseMaze
{
public static void main(String args[])
{
int width = 10;
int height = 20;
int[][] cheeseCells = { { 5, 3 }, { 4, 3 }, { 7, 11 } };
int[][] blockCells = { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } };
int[] anotherPerson = { 8, 17 };
CheeseMaze c = new CheeseMaze();
int[][] grid = c.createGrid(width, height, cheeseCells, blockCells, anotherPerson);
Result result = c.findCheese(grid, anotherPerson);
System.out.println(result);
}
public Result findCheese(int[][] grid, int[] anotherPerson)
{
boolean[][] visited = new boolean[grid.length][grid[0].length];
return findCheeseHelper(grid, visited, anotherPerson);
}
private Result findCheeseHelper(int[][] grid, boolean[][] visited, int[] anotherPerson)
{
int[] x = {0, 0, -1, 1};
int[] y = {-1, 1, 0, 0};
Queue<Integer[]> next = new LinkedList<>();
Queue<Integer[]> curr = null;
next.offer(new Integer[]{0,0});
int stepsCount = 0;
int globalStepsCount = 0;
int cheeseCount = 0;
int[] lastCheese = new int[2];
while(!next.isEmpty())
{
curr = next;
next = new LinkedList<>();
while(!curr.isEmpty())
{
Integer[] temp = curr.poll();
if(!visited[temp[0]][temp[1]])
{
visited[temp[0]][temp[1]] = true;
if(grid[temp[0]][temp[1]]==2)
{
globalStepsCount += stepsCount;
stepsCount = 0;
cheeseCount++;
lastCheese[0] = temp[0];
lastCheese[1] = temp[1];
next = new LinkedList<>();
curr = new LinkedList<>();
}
for(int i=0;i<x.length;i++)
{
int r = temp[0] + x[i];
int c = temp[1] + y[i];
if(isSafe(grid, r, c, visited, anotherPerson))
{
next.offer(new Integer[]{r, c});
}
}
}
}
stepsCount++;
}
System.out.println(cheeseCount + " : "+ stepsCount + " : "+globalStepsCount);
Result r = new Result();
r.totalSteps = Math.abs(lastCheese[0]-anotherPerson[0])+Math.abs(lastCheese[1]-anotherPerson[1]) + globalStepsCount;
r.cheeseCount = cheeseCount;
return r;
}
private boolean isSafe(int[][] grid, int row, int col, boolean[][] visited, int[] anotherPerson)
{
//System.out.println(row + " : " + col );
if(row < 0 ||
row >= grid.length ||
col < 0 ||
col >= grid[row].length ||
grid[row][col]==0 ||
visited[row][col] ||
(row==anotherPerson[0]&&col==anotherPerson[1]))
{
return false;
}
return true;
}
private int[][] createGrid(int width,
int height,
int[][] cheeseCells,
int[][] blockCells,
int[] anotherPerson)
{
int[][] grid = new int[width][height];
for(int i=0;i<grid.length;i++)
{
Arrays.fill(grid[i], 1);
}
for(int i=0;i<cheeseCells.length;i++)
{
grid[cheeseCells[i][0]][cheeseCells[i][1]] = 2;
}
for(int i=0;i<blockCells.length;i++)
{
grid[blockCells[i][0]][blockCells[i][1]] = 0;
}
grid[anotherPerson[0]][anotherPerson[1]]=3;
for(int i=0;i<grid.length;i++)
{
System.out.println(Arrays.toString(grid[i]));
}
return grid;
}
}
class Result
{
int totalSteps;
int cheeseCount;
public String toString()
{
return "totalSteps: "+ totalSteps + " cheeseCount: " + cheeseCount;
}
}
This sounds like the Knight Chess problem. To solve this:
* Build a graph. Each cell is connected to its adjacent cells marked with 0 or 2 (we can't move to 1s).
* Use BFS to traverse the *entire* graph (we don't know where the cheeses are located nor how many we have, so we need to check them all).
* When we hit the other person cell we keep track for how many steps we needed to get from him to the end of the maze.
So in theory its O(m*n)
And here is a C++ implementation of the above description:
#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string.h>
#include <queue>
#include <functional>
#define CAN_MOVE 0
#define BLOCKED_PATH 1
#define CHEESE 2
#define OTHER_PERSON 3
struct DimNode {
int _x;
int _y;
int _value;
std::string _key;
std::vector<DimNode*> _adjacents;
DimNode* _origin;
bool _visited;
DimNode() {}
DimNode(int x, int y)
: _x(x)
, _y(y)
, _value(CAN_MOVE)
, _key(std::to_string(x) + "," + std::to_string(y))
, _origin(NULL)
, _visited(false)
{
}
};
std::unordered_map<std::string, DimNode> G;
DimNode* GetNode(int x, int y)
{
std::string key = std::to_string(x) + "," + std::to_string(y);
if(G.count(key) == 0) {
G.insert(std::make_pair(key, DimNode(x, y)));
}
return &G[key];
}
std::vector<DimNode*> GetAdjacents(DimNode* node, int m, int n)
{
int x = node->_x;
int y = node->_y;
std::vector<DimNode*> result;
if((x + 1) < m) {
// valid index
result.push_back(GetNode(x + 1, y));
}
if((x - 1) >= 0) {
// valid index
result.push_back(GetNode(x - 1, y));
}
if((y - 1) >= 0) {
// valid index
result.push_back(GetNode(x, y - 1));
}
if((y + 1) < n) {
// valid index
result.push_back(GetNode(x, y + 1));
}
return result;
}
enum eState { kNormal, kOtherPersonFound };
void calculate_steps(int m, int n, const std::vector<std::pair<int, int> >& cheeseCells,
const std::vector<std::pair<int, int> >& blockedCells, const std::pair<int, int>& otherPerson)
{
// build m*n graph
for(int x = 0; x < m; ++x) {
for(int y = 0; y < n; ++y) {
DimNode* node = GetNode(x, y);
node->_adjacents = GetAdjacents(node, m, n);
}
}
std::for_each(blockedCells.begin(), blockedCells.end(),
[&](const std::pair<int, int>& coords) { GetNode(coords.first, coords.second)->_value = BLOCKED_PATH; });
std::for_each(cheeseCells.begin(), cheeseCells.end(),
[&](const std::pair<int, int>& coords) { GetNode(coords.first, coords.second)->_value = CHEESE; });
GetNode(otherPerson.first, otherPerson.second)->_value = OTHER_PERSON;
// Now that we have the graph, loop over it
std::queue<DimNode*> q;
q.push(GetNode(0, 0));
GetNode(0, 0)->_visited = true;
int cheesCounter = 0;
eState state = kNormal;
std::string otherPersonCoords;
int steps = 0;
DimNode* currentNode = NULL;
while(!q.empty()) {
currentNode = q.front();
q.pop();
steps++;
switch(currentNode->_value) {
case CAN_MOVE:
// Traverse
break;
case CHEESE:
// Increase the cheese counter
cheesCounter++;
break;
case OTHER_PERSON:
// Found the other person cell, start tracking to this location
state = kOtherPersonFound;
otherPersonCoords = currentNode->_key;
break;
default:
break;
}
std::for_each(currentNode->_adjacents.begin(), currentNode->_adjacents.end(), [&](DimNode* adj) {
if(!adj->_visited && (adj->_value != BLOCKED_PATH)) {
q.push(adj);
adj->_visited = true;
if(state == kOtherPersonFound) {
adj->_origin = currentNode;
}
}
});
}
std::cout << "Found " << cheesCounter << " cheese caked" << std::endl;
std::cout << "Other person is found at " << otherPersonCoords << std::endl;
if(currentNode) {
DimNode* runner = currentNode;
std::cout << "Path from last position to other-person:" << std::endl;
while(runner) {
steps++;
std::cout << runner->_key << " ";
runner = runner->_origin;
}
std::cout << std::endl;
}
std::cout << "Total steps walked: " << steps << std::endl;
}
int main(int argc, char** argv)
{
calculate_steps(10, 20, { { 5, 3 }, { 4, 3 }, { 7, 11 } }, { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } }, { 8, 17 });
return 0;
}
This will output:
Found 3 cheese caked
Other person is found at 8,17
Path from last position to other-person:
9,19 9,18 9,17
Total steps walked: 199
@ChrisK not really a travelling salesman: all the steps have the same weight (one step for each direction), you don't know the locations of the cheeses, so you must visit each cell once. Notice that in my code I am using this condition:
if(!adj->_visited && (adj->_value != BLOCKED_PATH))
i.e. we don't visit each cell more than once.
The solution is O(m*n)
@ChrisK i think that we only disagree on the initial matrix traverse time. You ignore it, while I take it into consideration. If you ignore this step, then yes, this is a traveling salesman problem. I think that we can't ignore the initial matrix traverse time (and this is what my code does). This debate can be solved only by asking the interviewer these kind of questions...
FYI: I also notice that other people assumed the same assumption as I did
Hum, it's travelling salesman: shortest path to collect all cheese cakes.
- Chris September 09, 20171) find all cakes: O(n*m)
2) do all pair shortest path among all pairs of {cheese cakes, start, end}.
3) find optimal route (np hard problem): you can try all routes which is O(n!) or accept an error an do linear optimization (or solve it in P and prove p=np and get famous and watch the world turn upside down)
There are two problems to solve here, the pairs shortest path wich demands for a quadratic amount of shortest path, so the shortest path algos it self should be fast. The graph is sparse and directed, so with classical algos the best is dual source bfs, since it's a map, a* will outperform it if the blocking fields do not introduce a complex maze...
The other is traveling salesman, where the best is linear optimization, e.g. simplex. Focus on the subproblem you feel most comfortable in the 40 Minutes and mention the other briefly or does anyone code both well in 20 min?