## Amazon Interview Question for SDE1s

• 1
of 1 vote

Country: United States

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

``````#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.
In 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.

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.