Amazon Interview Question Quality Assurance Engineers
Team: Ring
Country: India
import java.util.*;
public class PathInMatrix {
public static boolean utilityPath(int x,int y,int m,int n,int[][] mat,List<List<Integer>> path)
{
if(x==m-1 && y==n-1)
{
path.add(Arrays.asList(x,y));
path.forEach((p)->System.out.println(p.get(0)+","+p.get(1)));
return true;
}
if(x>=0 && x<m && y>=0 && y<n && mat[x][y]==1)
{
path.add(Arrays.asList(x,y));
if(utilityPath(x+1,y,m,n,mat,path) || utilityPath(x,y+1,m,n,mat,path))
return true;
path.remove(path.size()-1);
}
return false;
}
public static void getPath(int[][] mat)
{
boolean path=utilityPath(0,0,mat.length,mat[0].length,mat,new ArrayList<>());
}
public static void main(String[] args) {
int[][] mat={{1,0,0,0},{1,1,0,0},{0,1,1,0},{1,1,1,1}};
getPath(mat);
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class T2 {
private static ArrayList<ArrayList<Integer>> twoDimen = new ArrayList<>();
public static void main(String[] args) {
init();
int col = -1;
int row = -1;
Stack<Map<Integer, Integer>> result = new Stack<>();
Map<Integer, Integer> getPrev = new HashMap<>();
boolean firstRow = true;
for (int i = 0; i < twoDimen.size(); i++) {
ArrayList<Integer> getA = twoDimen.get(i);
for (int j = 0; j < getA.size(); j++) {
if (getA.get(j) == 1) {
if (firstRow) {
row = i;
col = j;
} else {
getPrev = result.peek();
if (getPrev.isEmpty() || getPrev == null)
continue;
else {
int value = -1;
if (getPrev.containsKey(i - 1)) {
value = getPrev.get(i - 1);
if ((value == j)) {
for (int k = j; k < getA.size(); k++) {
if (getA.get(k) == 1) {
row = i;
col = k;
}
}
break;
} else {
continue;
}
}
}
}
}
}
firstRow = false;
Map<Integer, Integer> getOne = new HashMap<>();
if ((row != -1) || (col != -1))
getOne.put(row, col);
result.add(getOne);
}
System.out.println(result);
}
private static void init() {
ArrayList<Integer> inner = new ArrayList<>();
inner.add(1);
inner.add(0);
inner.add(0);
inner.add(0);
twoDimen.add(inner);
inner = new ArrayList<>();
inner.add(1);
inner.add(1);
inner.add(0);
inner.add(0);
twoDimen.add(inner);
inner = new ArrayList<>();
inner.add(0);
inner.add(1);
inner.add(1);
inner.add(0);
twoDimen.add(inner);
inner = new ArrayList<>();
inner.add(1);
inner.add(1);
inner.add(1);
inner.add(1);
twoDimen.add(inner);
inner = new ArrayList<>();
}
}
const matrixSize = 5;
const dataGenerator = n => {
const data = [];
for (let i =0; i < n; i++) {
const insideData = [];
for (let i =0; i < n; i++) {
insideData.push(Math.round(Math.random()));
}
data.push([...insideData]);
}
return data;
};
const generateMap = path => {
path.visited = true;
if (path.x < matrixSize - 1 && inputData[path.x + 1][path.y] == 1) {
paths.push(
{
x: path.x + 1, y: path.y,
from: [...path.from, `${path.x},${path.y}`],
visited: false
});
}
if (path.y < matrixSize - 1 && inputData[path.x][path.y + 1] == 1) {
paths.push(
{
x: path.x, y: path.y + 1,
from: [...path.from, `${path.x},${path.y}`],
visited: false
}
);
}
}
const inputData = dataGenerator(matrixSize);
const paths = [{from: [], x: 0, y: 0, visited: false}];
while (paths.filter(path => !path.visited).length) {
paths.filter(path => !path.visited).forEach(path => generateMap(path));
}
const result = paths.find(
path => path.x === matrixSize - 1 && path.y === matrixSize - 1);
if (result) {
console.log("Destination reached and the route is ", result.from);
} else {
console.log("No route to the destination ");
}
console.log("Here is Input data ", JSON.stringify(inputData));
let matrix = [[1, 0, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 1]]
let lastx = 0
let lasty = 0
for (let i = lastx; i < matrix.length; i++) {
const row = matrix[i];
for (let j = lasty; j < matrix[0].length; j++) {
const item = row[j];
if (j + 1 <= row.length && row[j + 1] == 1) {
lastx = i
lasty = j + 1
console.log(lastx, lasty)
continue
}
if (i + 1 < matrix.length && matrix[i + 1][j] == 1) {
lastx = i + 1
lasty = j
console.log(lastx, lasty)
break
}
}
}
class Solution {
public boolean calculatePath(int [][] matrix){
if(matrix == null || matrix.length == 0){
return false;
}
Queue <int[]> queue = new LinkedList<>();
int [][] directions = {{0, 1} ,{1 , 0} };
queue.add(new int [] {0 , 0});
while(!queue.isEmpty()){
int [] arr = queue.poll();
int row = arr[0];
int col = arr[1];
if(row == matrix.length - 1 && col == matrix[0].length -1){
return true;
}
for(int [] dir : directions){
int x = row + dir[0];
int y = col + dir[1];
if(x < matrix.length && y < matrix[0].length && matrix[x][y] == 1){
queue.add(new int[] {x , y});
}
}
}
return false;
}
class Solution {
public boolean calculatePath(int [][] matrix){
if(matrix == null || matrix.length == 0){
return false;
}
Queue <int[]> queue = new LinkedList<>();
int [][] directions = {{0, 1} ,{1 , 0} };
queue.add(new int [] {0 , 0});
while(!queue.isEmpty()){
int [] arr = queue.poll();
int row = arr[0];
int col = arr[1];
if(row == matrix.length - 1 && col == matrix[0].length -1){
return true;
}
for(int [] dir : directions){
int x = row + dir[0];
int y = col + dir[1];
if(x < matrix.length && y < matrix[0].length && matrix[x][y] == 1){
queue.add(new int[] {x , y});
}
}
}
return false;
}.
class Solution {
public boolean calculatePath(int [][] matrix){
if(matrix == null || matrix.length == 0){
return false;
}
Queue <int[]> queue = new LinkedList<>();
int [][] directions = {{0, 1} ,{1 , 0} };
queue.add(new int [] {0 , 0});
while(!queue.isEmpty()){
int [] arr = queue.poll();
int row = arr[0];
int col = arr[1];
if(row == matrix.length - 1 && col == matrix[0].length -1){
return true;
}
for(int [] dir : directions){
int x = row + dir[0];
int y = col + dir[1];
if(x < matrix.length && y < matrix[0].length && matrix[x][y] == 1){
queue.add(new int[] {x , y});
}
}
}
return false;
}
class Solution {
public boolean calculatePath(int [][] matrix){
if(matrix == null || matrix.length == 0){
return false;
}
Queue <int[]> queue = new LinkedList<>();
int [][] directions = {{0, 1} ,{1 , 0} };
queue.add(new int [] {0 , 0});
while(!queue.isEmpty()){
int [] arr = queue.poll();
int row = arr[0];
int col = arr[1];
if(row == matrix.length - 1 && col == matrix[0].length -1){
return true;
}
for(int [] dir : directions){
int x = row + dir[0];
int y = col + dir[1];
if(x < matrix.length && y < matrix[0].length && matrix[x][y] == 1){
queue.add(new int[] {x , y});
}
}
}
return false;
}
class Solution {
public boolean calculatePath(int [][] matrix){
if(matrix == null || matrix.length == 0){
return false;
}
Queue <int[]> queue = new LinkedList<>();
int [][] directions = {{0, 1} ,{1 , 0} };
queue.add(new int [] {0 , 0});
while(!queue.isEmpty()){
int [] arr = queue.poll();
int row = arr[0];
int col = arr[1];
if(row == matrix.length - 1 && col == matrix[0].length -1){
return true;
}
for(int [] dir : directions){
int x = row + dir[0];
int y = col + dir[1];
if(x < matrix.length && y < matrix[0].length && matrix[x][y] == 1){
queue.add(new int[] {x , y});
}
}
}
return false;
}
class Solution {
public boolean calculatePath(int [][] matrix){
if(matrix == null || matrix.length == 0){
return false;
}
Queue <int[]> queue = new LinkedList<>();
int [][] directions = {{0, 1} ,{1 , 0} };
queue.add(new int [] {0 , 0});
while(!queue.isEmpty()){
int [] arr = queue.poll();
int row = arr[0];
int col = arr[1];
if(row == matrix.length - 1 && col == matrix[0].length -1){
return true;
}
for(int [] dir : directions){
int x = row + dir[0];
int y = col + dir[1];
if(x < matrix.length && y < matrix[0].length && matrix[x][y] == 1){
queue.add(new int[] {x , y});
}
}
}
return false;
}
import java.util.*;
- anaghgg September 24, 2020public class PathInMatrix {
public static boolean utilityPath(int x,int y,int m,int n,int[][] mat,List<List<Integer>> path)
{
if(x==m-1 && y==n-1)
{
path.add(Arrays.asList(x,y));
path.forEach((p)->System.out.println(p.get(0)+","+p.get(1)));
return true;
}
if(x>=0 && x<m && y>=0 && y<n && mat[x][y]==1)
{
path.add(Arrays.asList(x,y));
if(utilityPath(x+1,y,m,n,mat,path) || utilityPath(x,y+1,m,n,mat,path))
return true;
path.remove(path.size()-1);
}
return false;
}
public static void getPath(int[][] mat)
{
boolean path=utilityPath(0,0,mat.length,mat[0].length,mat,new ArrayList<>());
}
public static void main(String[] args) {
int[][] mat={{1,0,0,0},{1,1,0,0},{0,1,1,0},{1,1,1,1}};
getPath(mat);
}
}