Facebook Interview Question SDE1s
Country: United States
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?
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;
}
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
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;
}
}
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 sums.add(run_sum)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
- Chris July 14, 2017def 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: sums.add(run_sum) # I can't visit that node again, since I only check paths that visit a given node only once visited.add(pos) 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))