Facebook Interview Question Software Developers
Country: United States
public static void main(String[] args){
int x = 1;
int y = 1;
int k = 2;
System.out.println(count(x, y, k));
}
public static int count(int x, int y, int k){
int[][] dp = new int[x+1][y+1];
for(int i = 1; i < dp.length; i++){
dp[i][0] = 1;
dp[0][i] = 1;
}
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp.length; j++){
if(i == x && j == y){
if(dp[i-1][j] == k-1)
dp[i][j] = dp[i-1][j];
if(dp[i][j-1] == k-1)
dp[i][j] += dp[i][j-1];
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[x][y];
}
my idea is starting from (0,0) and try all the possible combinations until it reaches k steps and stop moving forward. Then check how many cases stopped at (x,y)
public class FindPaths {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String input = scan.nextLine();
String[] cmd = input.split(" ");
int x = Integer.parseInt(cmd[0]);
int y = Integer.parseInt(cmd[1]);
int k = Integer.parseInt(cmd[2]);
System.out.println("Starting calculating");
final int w = 10, h = 10;
LinkedList<Path> allPaths = new LinkedList<Path>();
findPath(allPaths, x, y, k, w, h);
int count = 0;
// check how many attempts contain the case that last step stops at the
// target point(x,y)
for (Path path : allPaths) {
if (path.footprints.getLast().getKey() == x && path.footprints.getLast().getValue() == y) {
count++;
System.out.println(path.printFootprints());
}
}
System.out.println("Paths=" + count);
}
// to store all the foot prints
static class Path {
LinkedList<Entry<Integer, Integer>> footprints = new LinkedList<Entry<Integer, Integer>>();
int steps;
public Path() {
}
public Path(int x, int y) {
Entry<Integer, Integer> initial = new AbstractMap.SimpleEntry<Integer, Integer>(x, y);
footprints.add(initial);
steps = 0;
}
public String printFootprints() {
String str = "";
for (Entry<Integer, Integer> print : footprints) {
str += "(" + print.getKey() + "," + print.getValue() + "), ";
}
return str;
}
public Path clone() {
Path cl = new Path();
cl.steps = this.steps;
cl.footprints = new LinkedList<Entry<Integer, Integer>>();
cl.footprints.addAll(footprints);
return cl;
}
}
/**
* start from (0,0) and try all the possible directions/combinations, until
* it reaches max steps and then stop.
*/
private static void findPath(LinkedList<Path> allPaths, int x, int y, int k, int w, int h) {
LinkedList<Path> nextSteps = new LinkedList<Path>();
nextSteps.add(new Path(0, 0));
while (!nextSteps.isEmpty()) {
Path path = nextSteps.poll();
int currentX = path.footprints.getLast().getKey();
int currentY = path.footprints.getLast().getValue();
System.out.println("current step at: (" + currentX + "," + currentY + "), steps: " + path.steps);
if (path.steps >= k) {
// reach the max steps, stop.
allPaths.add(path);
} else {
// try next steps (4 possible directions)
if (currentX + 1 < w) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX + 1,
currentY);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
if (currentX - 1 >= 0) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX - 1,
currentY);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
if (currentY + 1 < h) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX,
currentY + 1);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
if (currentY - 1 >= 0) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX,
currentY - 1);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
}
}
}
}
public class FindPaths {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String input = scan.nextLine();
String[] cmd = input.split(" ");
int x = Integer.parseInt(cmd[0]);
int y = Integer.parseInt(cmd[1]);
int k = Integer.parseInt(cmd[2]);
System.out.println("Starting calculating");
final int w = 10, h = 10;
LinkedList<Path> allPaths = new LinkedList<Path>();
findPath(allPaths, x, y, k, w, h);
int count = 0;
// check how many attempts contain the case that last step stops at the
// target point(x,y)
for (Path path : allPaths) {
if (path.footprints.getLast().getKey() == x && path.footprints.getLast().getValue() == y) {
count++;
System.out.println(path.printFootprints());
}
}
System.out.println("Paths=" + count);
}
// to store all the foot prints
static class Path {
LinkedList<Entry<Integer, Integer>> footprints = new LinkedList<Entry<Integer, Integer>>();
int steps;
public Path() {
}
public Path(int x, int y) {
Entry<Integer, Integer> initial = new AbstractMap.SimpleEntry<Integer, Integer>(x, y);
footprints.add(initial);
steps = 0;
}
public String printFootprints() {
String str = "";
for (Entry<Integer, Integer> print : footprints) {
str += "(" + print.getKey() + "," + print.getValue() + "), ";
}
return str;
}
public Path clone() {
Path cl = new Path();
cl.steps = this.steps;
cl.footprints = new LinkedList<Entry<Integer, Integer>>();
cl.footprints.addAll(footprints);
return cl;
}
}
/**
* start from (0,0) and try all the possible directions/combinations, until
* it reaches max steps and then stop.
*/
private static void findPath(LinkedList<Path> allPaths, int x, int y, int k, int w, int h) {
LinkedList<Path> nextSteps = new LinkedList<Path>();
nextSteps.add(new Path(0, 0));
while (!nextSteps.isEmpty()) {
Path path = nextSteps.poll();
int currentX = path.footprints.getLast().getKey();
int currentY = path.footprints.getLast().getValue();
System.out.println("current step at: (" + currentX + "," + currentY + "), steps: " + path.steps);
if (path.steps >= k) {
// reach the max steps, stop.
allPaths.add(path);
} else {
// try next steps (4 possible directions)
if (currentX + 1 < w) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX + 1,
currentY);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
if (currentX - 1 >= 0) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX - 1,
currentY);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
if (currentY + 1 < h) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX,
currentY + 1);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
if (currentY - 1 >= 0) {
Path clPath = path.clone();
clPath.steps++;
Entry<Integer, Integer> nextPt = new AbstractMap.SimpleEntry<Integer, Integer>(currentX,
currentY - 1);
clPath.footprints.add(nextPt);
nextSteps.add(clPath);
}
}
}
}
}
O(m * n * k) time and space.
int Count(int m, int n, int16_t r, int16_t c, int k, unordered_map<uint64_t, int> &memo)
{
if (k < 0 ||
r < 0 ||
c < 0 ||
r >= m ||
c >= n)
{
return 0;
}
if (k == 0 &&
r == 0 &&
c == 0)
{
return 1;
}
uint64_t memo_key = ((uint64_t)r << 48) | ((uint64_t)c << 32) | k;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
memo[memo_key] = Count(m, n, r - 1, c, k - 1, memo) +
Count(m, n, r + 1, c, k - 1, memo) +
Count(m, n, r, c - 1, k - 1, memo) +
Count(m, n, r, c + 1, k - 1, memo);
return memo[memo_key];
}
ChrisK's solution, improved regarding space. O(m * n * k) time, O(m * n) space.
int Count(int m, int n, int16_t start_r, int16_t start_c, int k) {
int dp[m][n][2];
memset(dp, 0, sizeof(dp));
dp[start_r][start_c][0] = 1;
int current = 1;
int prev = 0;
for (int step = 1; step <= k; ++step) {
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
dp[r][c][current] = 0;
if (r - 1 >= 0) {
dp[r][c][current] += dp[r - 1][c][prev];
}
if (r + 1 < m) {
dp[r][c][current] += dp[r + 1][c][prev];
}
if (c - 1 >= 0) {
dp[r][c][current] += dp[r][c - 1][prev];
}
if (c + 1 < n) {
dp[r][c][current] += dp[r][c + 1][prev];
}
}
}
swap(prev, current);
}
return dp[0][0][prev];
}
How is this not a simple dynamic programming problem?
F(x, y, k) = number of paths to get from x,y to 0,0 in k steps
Then F(x,y,k) can be defined in terms of F(x-1, y, k-1), F(x+1, y, k-1), F(x, y-1, k-1) and F(x, y+1, k-1)
memoize the result so it can be reused in other branches of the search
python code:
C = {}
def F(x, y, k, nRows, nColumns):
if x+y > k or k <0:
return 0
if x == 0 and y == 0 and k == 0:
return 1
if (x, y, k) in C:
return C[(x,y,k)]
f1 = 0; f2 = 0; f3 = 0; f4 = 0
if y-1 >= 0:
f1 = F(x, y-1, k-1, nRows, nColumns)
if y+1 < nRows:
f2 = F(x, y+1, k-1, nRows, nColumns)
if x-1 >=0:
f3 = F(x-1, y, k-1, nRows, nColumns)
if x+1 < nColumns:
f4 = F(x+1, y, k-1, nRows, nColumns)
total = f1 + f2 + f3 + f4
C[(x, y, k)] = total
return total
print F(1,1, 2 ,4,5)
It depends on the exact semantics of "all paths". Can we jump back and forth a field
to extend the path or is the intention for each path we count that path only visits
a field once.
I assume the first, no matter how I walk, as long as I can get to (0,0) from
the given start (x,y) in k steps, it's a valid path, even if I pass (0,0) before
and come back to it on the kth step. Further I assume I can go everywhere in the matrix.
There is an obvious solution, that is, try all paths. There are 4^n such paths,
this will result in an O(4^n) (time) solution.
Given the graph problem of finding all paths or finding k-th order path is NP hard,
this isn't much of a surprise.
But here we have a matrix, so I would try to "exploit" the fact that this isn't exactly
a graph and it seems feasible to have some subproblems one can reuse.
I think that's possible by keeping a vector of size k for each cell and in each
iteration I count for each cell in how many ways I can reach it. I do this k times.
This is a O(k*n*m) time and space solution. So it's polynomial and I solved a
special case of an NP-hard problem - not exactly (of course) but it sounds a bit cool...
Space complexity of the later can be reduced to n*m but the code then doesn't look
as neat anymore.
- Chris October 23, 2017#include <vector> #include <unordered_set> #include <iostream> using namespace std; using uint = unsigned int; const uint MOVES[][2]{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; size_t count_paths_bruteforce(size_t m, size_t n, uint sx, uint sy, uint k) { // lazy recursive impl. if (sx + sy > k) return 0; // can't reach {0, 0} no need to further try (to be not totally silly) if (k == 0 && sx == 0 && sy == 0) return 1; // reached {0, 0} in k steps if (sx >= m || sy >= n) return 0; uint sum = 0; for (size_t d = 0; d < sizeof(MOVES) / sizeof(decltype(MOVES[0])); ++d) { // ignore overflow here, should check sum += count_paths_bruteforce(m, n, sx + MOVES[d][0], sy + MOVES[d][1], k - 1); } return sum; } size_t count_paths_poly(size_t m, size_t n, uint sx, uint sy, uint k) { vector<vector<vector<uint>>> dp(m, vector<vector<uint>>(n, vector<uint>(k + 1, 0))); // can optimize space to n*m dp[sx][sy][0] = 1; // start condition for (uint i = 1; i <= k; i++) { for (uint x = 0; x < m; ++x) { // could be optimized to only iterate over visited fields for (uint y = 0; y < n; ++y) { // same optimization as with y for (size_t d = 0; d < sizeof(MOVES) / sizeof(decltype(MOVES[0])); ++d) { uint ox = x + MOVES[d][0]; // go from ox to x uint oy = y + MOVES[d][1]; // go from oy to y if (ox >= m || oy >= n) continue; // in field? dp[x][y][i] += dp[ox][oy][i - 1]; // += 0 doesn't harm } } } } return dp[0][0][k]; } void test(size_t m, size_t n, uint x, uint y, uint k) { cout << "test case (mxn): " << m << "x" << m << " (x,y): " << x << "," << y << " k:" << k << endl; cout << "poly algo: " << count_paths_poly(m, n, x, y, k) << endl; cout << "brute force: " << count_paths_bruteforce(m, n, x, y, k) << endl << endl; } int main() { //test(2, 2, 1, 1, 1); // 0 test(2, 2, 1, 1, 2); test(2, 2, 1, 1, 3); test(2, 2, 1, 1, 4); test(5, 5, 4, 4, 5); test(5, 8, 4, 6, 10); test(5, 8, 4, 6, 16); test(5, 8, 4, 6, 17); test(5, 8, 4, 6, 18); test(5, 8, 4, 6, 20); test(5, 8, 4, 6, 21); // the last few to experience exp vs. poly }