Amazon Interview Question SDE1s
Country: United States
Code
#include <iostream>
#include <vector>
bool CheckPathFromPoint(const std::vector<std::vector<int>>& data, size_t y, size_t x, int prevVal)
{
if(y == 0 && x == 0)
return data[0][0] != prevVal;
if(y < 0 || x < 0)
return false;
if(data[y][x] == prevVal)
return false;
auto res = CheckPathFromPoint(data, y-1, x, data[y][x]);
if(res)
return res;
return CheckPathFromPoint(data, y, x-1, data[y][x]);
}
bool CheckPath(const std::vector<std::vector<int>>& data)
{
auto res = false;
if(data.size() > 2 && data[0].size() > 1)
res = CheckPathFromPoint(data, data.size()-2, data[0].size()-1, data[data.size()-1][data[0].size()-1]);
if(res)
return res;
if(data.size() > 1 && data[0].size() > 2)
return CheckPathFromPoint(data, data.size()-1, data[0].size()-2, data[data.size()-1][data[0].size()-1]);
}
The solution is not optimized - its complexity is O(2 in power of N+M) where N and M are the matrix's dimensions. To optimize it the dynamic programming approach should be used - it gives O(N+M) complexity;
The path length is always N+M, if N+M is even the number of 1s and 0s is equal.
#include <stdio.h>
#define ARR_SZ 4
void printPath(int parray[ARR_SZ][ARR_SZ])
{
int i, j;
for (i = 0; i < ARR_SZ; i++)
{
for (j = 0; j < ARR_SZ; j++)
printf("%d ", parray[i][j]);
printf("\n");
}
}
int IsPathExist(int mat[ARR_SZ][ARR_SZ], int r, int c, int prev_val)
{
if ((0 <= r && ARR_SZ > r) && (0 <= c && ARR_SZ > c) && (mat[r][c] != prev_val))
return 1;
return 0;
}
int checkPathUtil(int mat[ARR_SZ][ARR_SZ], int r, int c, int parray[ARR_SZ][ARR_SZ], int prev_val)
{
if ((ARR_SZ-1 == r) && (ARR_SZ-1 == c)){
parray[r][c] = mat[r][c];
return 1;
}
if (IsPathExist(mat, r, c, prev_val)) {
parray[r][c] = mat[r][c];
if (checkPathUtil(mat, r+1, c, parray, mat[r][c]))
return 1;
if (checkPathUtil(mat, r, c+1, parray, mat[r][c]))
return 1;
}
return 0;
}
void checkPath(int mat[ARR_SZ][ARR_SZ])
{
int parray[ARR_SZ][ARR_SZ] =
{ {-1, -1, -1, -1},
{-1, -1, -1, -1},
{-1, -1, -1, -1},
{-1, -1, -1, -1}
};
if (checkPathUtil(mat, 0, 0, parray, -1)) {
printf("Path Exist!!\n");
printPath(parray);
}
else {
printf("Path Not Exist!!\n");
printPath(parray);
}
return;
}
int main()
{
int barray[ARR_SZ][ARR_SZ] =
{ {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
checkPath(barray);
return 0;
}
Below I present the exhaustive search recursion solution and the much improved top-bottom solution using memoization.
Exhaustive Search using Recursion
# Recursion. Time Complx:- 2^(n+m)
def printPath(matrix):
def isSafe(i, j, prevValue):
return 0 <= i < len(matrix) and \
0 <= j < len(matrix[0]) \
and matrix[i][j] != prevValue
def findHelper(i, j, prevValue, path):
if i == len(matrix) - 1 and j == len(matrix[0]) - 1 \
and prevValue != matrix[i][j]:
path.append(str((i, j)))
return True
if isSafe(i, j, prevValue):
path.append(str((i, j)) + '-> ')
if findHelper(i, j+1, matrix[i][j], path):
return True
if findHelper(i+1, j, matrix[i][j], path):
return True
path.pop()
return False
return False
path = []
res = findHelper(0, 0, -1, path)
if len(path) == 0:
print('No path found from source to destination')
else:
print('Path found and the path is %s' % (''.join(path)))
Recursion + Memoization (Aka Top-Down Approach)
# Recursion + Memoization. Takes O(n+m).
# Use dictionary to store all the path's values
def printPathWithMemoization(matrix):
pathMemo = {}
def isSafe(i, j, prevValue):
return 0 <= i < len(matrix) and 0 <= j < len(matrix[0]) \
and matrix[i][j] != prevValue
def findHelper(i, j, prevValue, path):
if (i, j) in pathMemo:
return pathMemo[(i, j)]
if i == len(matrix) - 1 and j == len(matrix[0]) - 1 \
and prevValue != matrix[i][j]:
path.append(str((i, j)))
pathMemo[(i, j)] = True
return True
if isSafe(i, j, prevValue):
path.append(str((i, j)) + '-> ')
if findHelper(i, j+1, matrix[i][j], path):
pathMemo[(i, j)] = True
return True
if findHelper(i+1, j, matrix[i][j], path):
pathMemo[(i, j)] = True
return True
path.pop()
pathMemo[(i, j)] = False
return False
return False
path = []
res = findHelper(0, 0, -1, path)
if len(path) == 0:
print('No path found from source to destination')
else:
print('Path found and the path is %s' % (''.join(path)))
Test code:
matrix = \
[
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
matrix2 = \
[
[1, 0, 0],
[0, 1, 1],
[0, 0, 0],
]
matrix3 = \
[
[1, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 1, 0]
]
from pprint import pprint
pprint(matrix)
printPath(matrix)
printPathWithMemoization(matrix)
printPath(matrix2)
printPathWithMemoization(matrix2)
printPath(matrix3)
printPathWithMemoization(matrix3)
public static boolean hasPath(int[][] m) {
// Assuming m has at least one row
boolean[][] visited = initVisited(m.length, m[0].length);
return hasPath(m, 0, 0, visited);
}
private static boolean[][] initVisited(int r, int c) {
boolean[][] visited = new boolean[r][c];
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
visited[i][j] = false;
return visited;
}
private static boolean hasPath(int[][] m, int r, int c, boolean[][] visited) {
if (r == m.length - 1 && c == m[0].length - 1) return true;
else if (visited[r][c]) return false;
final int value = m[r][c];
final boolean right = c < m[0].length-1 && m[r][c+1] != value ? hasPath(m, r, c+1, visited) : false;
final boolean bottom = r < m.length-1 && m[r+1][c] != value ? hasPath(m, r+1, c, visited) : false;
visited[r][c] = !right && !bottom;
return right || bottom;
}
public boolean hasPath(int[][] m, int r, int c) {
if(r == m.length-1 && c == m[0].length-1)
return true;
boolean right = false, down = false;
int value = m[r][c];
if(c+1 < m[0].length && m[r][c+1] != value)
right = hasPath(m, r, c+1);
if(r+1 < m.length && m[r + 1][c] != value)
down = hasPath(m, r+1, c);
return (right || down);
}
from functools import partial
from random import randint
matrix = [[randint(0, 1) for x in range(5)] for y in range(5)]
isValidRange = partial(lambda size, point: point < size, len(matrix))
isFound = partial(lambda size, x, y: x == size and y == size, len(matrix))
def memorized(func):
visited = [[False for x in range(5)] for y in range(5)]
def inner(matrix, location):
│ x, y = location
│ if visited[x][y]:
│ │ return False
│ visited[x][y] = True
│ return func(matrix, location)
return inner
@memorized
def hasPath(matrix, location):
x, y = location
if isValidRange(x + 1) and matrix[x][y] != matrix[x + 1][y]:
│ if findPath(matrix, (x + 1, y)):
│ │ return True
if isValidRange(y + 1) and matrix[x][y] != matrix[x][y + 1]:
│ if findPath(matrix, (x, y + 1)):
│ │ return True
if isFound(x, y):
│ return True
return False
hasPath(matrix, (0, 0))
from functools import partial
from random import randint
matrix = [[randint(0, 1) for x in range(5)] for y in range(5)]
isValidRange = partial(lambda size, point: point < size, len(matrix))
isFound = partial(lambda size, x, y: x == size and y == size, len(matrix))
def memorized(func):
visited = [[False for x in range(5)] for y in range(5)]
def inner(matrix, location):
│ x, y = location
│ if visited[x][y]:
│ │ return False
│ visited[x][y] = True
│ return func(matrix, location)
return inner
@memorized
def hasPath(matrix, location):
x, y = location
if isValidRange(x + 1) and matrix[x][y] != matrix[x + 1][y]:
│ if findPath(matrix, (x + 1, y)):
│ │ return True
if isValidRange(y + 1) and matrix[x][y] != matrix[x][y + 1]:
│ if findPath(matrix, (x, y + 1)):
│ │ return True
if isFound(x, y):
│ return True
return False
hasPath(matrix, (0, 0))
from functools import partial
from random import randint
matrix = [[randint(0, 1) for x in range(5)] for y in range(5)]
isValidRange = partial(lambda size, point: point < size, len(matrix))
isFound = partial(lambda size, x, y: x == size and y == size, len(matrix))
def memorized(func):
visited = [[False for x in range(5)] for y in range(5)]
def inner(matrix, location):
│ x, y = location
│ if visited[x][y]:
│ │ return False
│ visited[x][y] = True
│ return func(matrix, location)
return inner
@memorized
def hasPath(matrix, location):
x, y = location
if isValidRange(x + 1) and matrix[x][y] != matrix[x + 1][y]:
│ if findPath(matrix, (x + 1, y)):
│ │ return True
if isValidRange(y + 1) and matrix[x][y] != matrix[x][y + 1]:
│ if findPath(matrix, (x, y + 1)):
│ │ return True
if isFound(x, y):
│ return True
return False
hasPath(matrix, (0, 0))
#include <iostream> #include <vector> bool CheckPathFromPoint(const std::vector<std::vector<int>>& data, size_t y, size_t x, int prevVal) { if(y == 0 && x == 0) return data[0][0] != prevVal; if(y < 0 || x < 0) return false; if(data[y][x] == prevVal) return false; auto res = CheckPathFromPoint(data, y-1, x, data[y][x]); if(res) return res; return CheckPathFromPoint(data, y, x-1, data[y][x]); } bool CheckPath(const std::vector<std::vector<int>>& data) { auto res = false; if(data.size() > 2 && data[0].size() > 1) res = CheckPathFromPoint(data, data.size()-2, data[0].size()-1, data[data.size()-1][data[0].size()-1]); if(res) return res; if(data.size() > 1 && data[0].size() > 2) return CheckPathFromPoint(data, data.size()-1, data[0].size()-2, data[data.size()-1][data[0].size()-1]); }The solution is not optimozed - it has O(2 in power of N+M) where N and M are the matrix's demensions.
- Yehorov March 06, 2018In order not to check each path several times the dynamic programming approach should be used - it gives O(N+M) complexity.
If the path exists and N+M is even the number of 1s and 0s will be equal.