## Facebook Interview Question for SDE1s

Country: United States

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

I assume, target is the sum of all fields visited by traveling from an arbitrary start to an arbitrary end coordinate using any possible path in the matrix.

The question needs clarifications like:
- which movements to form a path (what is adjacent to a field, e.g. left, right, top, down)
- can a field be visited more than once e.g. by going forth and back between two fields
- are there negative values in the matrix

approaches I thought of:
1) think about visiting all fields in a zig zag pattern, then start by looking for a sub-array in this array.

This would be possible in O(n*m) but it would reduce allowed paths

2) if the elements are unique, it's a sub-set sum problem, which is NP complete, how ever, not every sub set will form a path. There is a pseudo exponential algo to solve the subset problem, but then one would need to check if any of the subsets summing up to target would form a path. Feasible but dirty to code.

3) try all the paths that cover the whole field and then find a sub-array in the path that results in the desired sum. The problem here is there are many path's roughly 3^n*m from a single starting point and all starting points must be tried. So there are O(3^(n*m)*n*m) paths to explore. I'd go for that one although I'm not happy with it...

Since not the whole path is used but only a sub-path of it, the below code does check continuously whether any sub-path of the currently explored path will satisfy the target. The method is known as finding a sum in a sub-array and can be done in O(length(array)).
Its logic is that to achieve a target value within a sub-array, one has a part of the array on the left that is not used (maybe empty-array) to sum up a sub array in range (0, i) to target. if I continuously collect the running sum and put it into a HT, I'll find that left part if it exists:

``````run_sum = 0
sums = set([0])
for i in range(0, n):
run_sum += array[i]
if run_sum - target in sums:
return True

the rest is dfs using recursion, a stack implementation is possible (was actually my first attempt) but I found it slightly difficult to read

in python 3

``````def find_sum_in_matrix(matrix, target):
def dfs(pos, run_sum):
# visit matrix at pos and check if the sum needed to reach target was encountered
run_sum += matrix[pos[0]][pos[1]]
if run_sum - target in sums:
return True

# check if a new sum has been built that is a sub-array on the left of the current path
new_sum = run_sum not in sums
if new_sum:

# I can't visit that node again, since I only check paths that visit a given node only once
for move in [(1,0), (-1,0), (0, 1), (0, -1)]:
next = (pos[0] + move[0], pos[1] + move[1])
if next[0] >= 0 and next[1] >= 0 and next[0] < m and next[1] < n and next not in visited:
if dfs(next, run_sum):
return True

# if the runing sum was added on this level, need to remove it
if new_sum:
sums.remove(run_sum)

# this branch of the DFS is finished, so I free up this node
visited.remove(pos)
return False

n = len(matrix)
m = len(matrix[0]) if n > 0 else 0
if m == 0: return False
sums = set([0])
visited = set([(0, 0)])
for x in range(0, m):
for y in range(0, n):
if dfs((x, y), 0):
return True
return False

print(find_sum_in_matrix(\
[[1,1,1],\
[1,1,1],\
[1,1,1]],\
10)) # False

print(find_sum_in_matrix(\
[[1,1,1],\
[1,1,1],\
[1,1,1]],\
9)) # True

print(find_sum_in_matrix(\
[[1, 5, 10],\
[1, 1, -1],\
[1, 1,  5]],\
20)) # True

print(find_sum_in_matrix(\
[[1, 5, 10],\
[1, 2, -2],\
[1, 1,  5]],\
25)) # True     (must start at (2,2) or (0, 2))``````

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

Do we need to do DFS from every start point? I was thinking that since the matrix is fully connected, just doing dfs from {0,0} would suffice, since all the possible subpaths would have been explored. Am I missing something?

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

@axg What if the solution set doesn't contain {0,0}?

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

``````vector<queue<pair<int,int > > > PathesAddToX(int** M, int n, int m, int x)
{
return FollowPath(M, n, m, x, 0, 0, queue<pair<int,int> >(), 0);
}

vector<queue<pair<int,int> > > FollowPath(int** M, int n, int m, int Target, int i, int j, queue<pair<int,int> > path, int residualSum)
{
vector<queue<pair<int, int> > > result;
path.push(pair<int, int>(i, j));
residualSum += M[i][j];
while (residualSum > Target)
{
pair<int, int> tmp = path.front(); path.pop();
residualSum -= M[tmp.first][tmp.second];
}
if (residualSum == Target)
result.push_back(path);
if (i + 1 < n)
for (auto path : FollowPath(M, n, m, Target, i + 1, j, path, residualSum))
result.push_back(path);
if (j + 1 < m)
for (auto path : FollowPath(M, n, m, Target, i, j + 1, path, residualSum))
result.push_back(path);
return result;
}``````

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

Time complexity O(n2) i.e. n square
Space complexity O(n) - to store which nodes are traversed.
Solution using simple recursion:

``````import java.util.*;

class Main {
static  int[][] arr = {{1,2,0},{2,-1,2},{1,-2,2}};
static  int[][] trav = new int[arr.length][arr.length];

public static void main(String[] args) {

int sumtofind = 5;
boolean found =false;
for(int i=0;i<arr.length;i++){
found = false;
for(int j=0;j<arr.length;j++){
//refill for traversal
for(int k=0;k<arr.length;k++){
Arrays.fill(trav[k],0);
}
found = findsum(i,j,arr[i][j],sumtofind);
if(found){
//System.out.println("ans:"+found);
break;
}
}
if(found)break;
}
System.out.println("ans:"+found);

}

public static boolean findsum(int r,int c,int currsum,int sum){
//right
if((c+1)<arr.length && trav[r][c+1]!=1){
int newcurrsum=currsum+arr[r][c+1];
trav[r][c+1]=1;
if(newcurrsum==sum)return true;
return findsum(r,c+1,newcurrsum,sum);
}

//bottom
if((r+1)<arr.length && trav[r+1][c]!=1){
int newcurrsum=currsum+arr[r+1][c];
trav[r+1][c]=1;
if(newcurrsum==sum)return true;
return findsum(r+1,c,newcurrsum,sum);
}

return false;

}
}``````

Input:

``````1  2 0
2 -1 4
1 -2 2

sum=5``````

output:

``ans:true``

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

C++ Solution:
1) Change ROW and COL accordingly if you change the size of matrix.
2) Change target variable to change the sum value.

``````#include <iostream>
#include <string.h>
#include <stdio.h>

#define ROW 3
#define COL 3
using namespace std;

bool find_path_sum_equal_target(int a[][COL], int i, int j, bool visited[][COL], int &target)
{
if ((i < 0) || (j < 0) || (i >= ROW) || (j >= COL) || (visited[i][j]))
{
return false;
}

// Mark this cell as visited
visited[i][j] = true;

if (target-a[i][j] == 0)
return true;

target = target-a[i][j];

return (find_path_sum_equal_target(a, i-1, j, visited, target)
|| find_path_sum_equal_target(a, i+1, j, visited, target)
|| find_path_sum_equal_target(a, i, j-1, visited, target)
|| find_path_sum_equal_target(a, i, j+1, visited, target));

}

main()
{
int a[ROW][COL] = {1,2,3,
4,5,6,
7,8,9};

// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];

bool ret = false;
int target = 0;

for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
target = 36;
memset(visited, 0, sizeof(visited));
if (a[i][j] && !visited[i][j])
{
ret = find_path_sum_equal_target(a, i, j, visited, target);
if (ret == true) {
cout << "Find the path" << endl;
break;
}
}
}
if (ret == true) break;
}

}``````

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

``````<?php

\$a=array(4,1,2,1,1,2);

\$k=7;

if(findPathWithSum(\$a,\$k)) echo "YES";
else echo "NO";

function findPathWithSum(\$a,\$k){
\$sum=0;

for(\$i=0;\$i<sizeof(\$a);\$i++){
\$sum+=\$a[\$i];
if(\$sum == \$k) return true;
if(\$sum > \$k) \$sum=0;
}

return false;
}
?>``````

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.