Facebook Interview Question for SDE1s


Country: United States




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

Hum, it's travelling salesman: shortest path to collect all cheese cakes.
1) 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?

- Chris September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
      }
    }
  }

- bottomcoder September 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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}};

- bottomcoder September 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- Chris September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- Anonymous September 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- noob September 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- PenChief September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just traverse the matrix... with recurrence function and return the shortest path back... when you have multiple paths return the least span path

- Deepan September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- PenChief September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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)

- PenChief September 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@ChrisK Once you have visited each cell once, you have all the cakes AND you also have the coordinates of the "other person" so you can simply use backtracking to its location ( I have implemented this using the "_origin" member in my code)

- PenChief September 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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

- PenChief September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@ChrisK we need to "walk" ~25 steps to cover the entire maze + steps needed to walk back from the last position we reached back to the "other-person" cell.

- PenChief September 11, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More