Interview Question
Country: India
Interview Type: In-Person
There are some questions:
1) With multi-dimensional array you mean 2 dimensions or can be more than 2? I say that because you tell us to move from {0,0} to {n, n} and put only two coordinates.
2) The value of {0, 0} have to be 1 for the condition that say the cell have to be 1 for valid move? The same thing for {n, n}, have to be 1?
public class twoDArray {
public static void main(String args[]) {
int x[][] = {
{1, 1, 1, 0},
{1, 0, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1}
};
System.out.println("Shortest Path Distance: "+findShortestRoute(x));
}
public static int findShortestRoute(int[][] arrayX) {
// return errors
if (arrayX.length != arrayX[0].length) {
return -1;
}
//the (n,n) point has to be reachable
if (arrayX[arrayX.length - 1][arrayX.length - 1] != 1) {
return -1;
}
for (int x = 0; x < arrayX.length; x++) {
for (int y = 0; y < arrayX[0].length; y++) {
if (arrayX[x][y] != 0 && arrayX[x][y] != 1) {
return -1;
}
}
}
return findShortestRoute(arrayX, 0 , 0);
}
private static int findShortestRoute(int[][] arrayX, int x, int y) {
// base case
if (x == (arrayX.length - 1) && y == (arrayX[0].length - 1)) {
return 1;
}
int right= 99999, bottom= 99999, diagonal = 99999;
if (x < arrayX.length - 1 && arrayX[x+1][y] == 1) {
right = findShortestRoute(arrayX, x+1, y);
}
if (y < arrayX[0].length - 1 && arrayX[x][y+1] == 1) {
bottom = findShortestRoute(arrayX, x, y+1);
}
if (x < arrayX.length -1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 1) {
diagonal = findShortestRoute(arrayX, x+1, y+1);
}
if (x < arrayX.length - 1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 0 && arrayX[x+1][y] == 0 && arrayX[x][y+1] == 0) {
return 9999;
}
return 1 + minValue(right, bottom, diagonal);
}
private static int minValue(int a, int b, int c) {
int firstMin = (a < b) ? a : b;
return (c < firstMin) ? c : firstMin;
}
}
public class twoDArray {
public static void main(String args[]) {
int x[][] = {
{1, 1, 1, 0},
{1, 0, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1}
};
System.out.println("Shortest Path Distance: "+findShortestRoute(x));
}
public static int findShortestRoute(int[][] arrayX) {
// return errors
if (arrayX.length != arrayX[0].length) {
return -1;
}
//the (n,n) point has to be reachable
if (arrayX[arrayX.length - 1][arrayX.length - 1] != 1) {
return -1;
}
for (int x = 0; x < arrayX.length; x++) {
for (int y = 0; y < arrayX[0].length; y++) {
if (arrayX[x][y] != 0 && arrayX[x][y] != 1) {
return -1;
}
}
}
return findShortestRoute(arrayX, 0 , 0);
}
private static int findShortestRoute(int[][] arrayX, int x, int y) {
// base case
if (x == (arrayX.length - 1) && y == (arrayX[0].length - 1)) {
return 1;
}
int right= 99999, bottom= 99999, diagonal = 99999;
if (x < arrayX.length - 1 && arrayX[x+1][y] == 1) {
right = findShortestRoute(arrayX, x+1, y);
}
if (y < arrayX[0].length - 1 && arrayX[x][y+1] == 1) {
bottom = findShortestRoute(arrayX, x, y+1);
}
if (x < arrayX.length -1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 1) {
diagonal = findShortestRoute(arrayX, x+1, y+1);
}
if (x < arrayX.length - 1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 0 && arrayX[x+1][y] == 0 && arrayX[x][y+1] == 0) {
return 9999;
}
return 1 + minValue(right, bottom, diagonal);
}
private static int minValue(int a, int b, int c) {
int firstMin = (a < b) ? a : b;
return (c < firstMin) ? c : firstMin;
}
}
public class twoDArray {
public static void main(String args[]) {
int x[][] = {
{1, 1, 1, 0},
{1, 0, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1}
};
System.out.println("Shortest Path Distance: "+findShortestRoute(x));
}
public static int findShortestRoute(int[][] arrayX) {
// return errors
if (arrayX.length != arrayX[0].length) {
return -1;
}
//the (n,n) point has to be reachable
if (arrayX[arrayX.length - 1][arrayX.length - 1] != 1) {
return -1;
}
for (int x = 0; x < arrayX.length; x++) {
for (int y = 0; y < arrayX[0].length; y++) {
if (arrayX[x][y] != 0 && arrayX[x][y] != 1) {
return -1;
}
}
}
return findShortestRoute(arrayX, 0 , 0);
}
private static int findShortestRoute(int[][] arrayX, int x, int y) {
// base case
if (x == (arrayX.length - 1) && y == (arrayX[0].length - 1)) {
return 1;
}
int right= 99999, bottom= 99999, diagonal = 99999;
if (x < arrayX.length - 1 && arrayX[x+1][y] == 1) {
right = findShortestRoute(arrayX, x+1, y);
}
if (y < arrayX[0].length - 1 && arrayX[x][y+1] == 1) {
bottom = findShortestRoute(arrayX, x, y+1);
}
if (x < arrayX.length -1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 1) {
diagonal = findShortestRoute(arrayX, x+1, y+1);
}
if (x < arrayX.length - 1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 0 && arrayX[x+1][y] == 0 && arrayX[x][y+1] == 0) {
return 9999;
}
return 1 + minValue(right, bottom, diagonal);
}
private static int minValue(int a, int b, int c) {
int firstMin = (a < b) ? a : b;
return (c < firstMin) ? c : firstMin;
}
}
public static int findShortestRoute(int[][] arrayX) {
// return errors
if (arrayX.length != arrayX[0].length) {
return -1;
}
//the (n,n) point has to be reachable
if (arrayX[arrayX.length - 1][arrayX.length - 1] != 1) {
return -1;
}
for (int x = 0; x < arrayX.length; x++) {
for (int y = 0; y < arrayX[0].length; y++) {
if (arrayX[x][y] != 0 && arrayX[x][y] != 1) {
return -1;
}
}
}
return findShortestRoute(arrayX, 0 , 0);
}
private static int findShortestRoute(int[][] arrayX, int x, int y) {
// base case
if (x == (arrayX.length - 1) && y == (arrayX[0].length - 1)) {
return 1;
}
int right= 99999, bottom= 99999, diagonal = 99999;
if (x < arrayX.length - 1 && arrayX[x+1][y] == 1) {
right = findShortestRoute(arrayX, x+1, y);
}
if (y < arrayX[0].length - 1 && arrayX[x][y+1] == 1) {
bottom = findShortestRoute(arrayX, x, y+1);
}
if (x < arrayX.length -1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 1) {
diagonal = findShortestRoute(arrayX, x+1, y+1);
}
if (x < arrayX.length - 1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 0 && arrayX[x+1][y] == 0 && arrayX[x][y+1] == 0) {
return 9999;
}
return 1 + minValue(right, bottom, diagonal);
}
private static int minValue(int a, int b, int c) {
int firstMin = (a < b) ? a : b;
return (c < firstMin) ? c : firstMin;
}
If diagonal is allowed
public static int findShortestRoute(int[][] arrayX) {
// return errors
if (arrayX.length != arrayX[0].length) {
return -1;
}
//the (n,n) point has to be reachable
if (arrayX[arrayX.length - 1][arrayX.length - 1] != 1) {
return -1;
}
for (int x = 0; x < arrayX.length; x++) {
for (int y = 0; y < arrayX[0].length; y++) {
if (arrayX[x][y] != 0 && arrayX[x][y] != 1) {
return -1;
}
}
}
return findShortestRoute(arrayX, 0 , 0);
}
private static int findShortestRoute(int[][] arrayX, int x, int y) {
// base case
if (x == (arrayX.length - 1) && y == (arrayX[0].length - 1)) {
return 1;
}
int right= 99999, bottom= 99999, diagonal = 99999;
if (x < arrayX.length - 1 && arrayX[x+1][y] == 1) {
right = findShortestRoute(arrayX, x+1, y);
}
if (y < arrayX[0].length - 1 && arrayX[x][y+1] == 1) {
bottom = findShortestRoute(arrayX, x, y+1);
}
if (x < arrayX.length -1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 1) {
diagonal = findShortestRoute(arrayX, x+1, y+1);
}
if (x < arrayX.length - 1 && y < arrayX[0].length - 1 && arrayX[x+1][y+1] == 0 && arrayX[x+1][y] == 0 && arrayX[x][y+1] == 0) {
return 9999;
}
return 1 + minValue(right, bottom, diagonal);
}
private static int minValue(int a, int b, int c) {
int firstMin = (a < b) ? a : b;
return (c < firstMin) ? c : firstMin;
}
/*
Assumptions:
- two dimensional due to given coordinates
- move in any of the 8 directions possible, if the field is a "1" , -1,-1, -1, 0, -1, 1
- from {0,0} to {n-1, n-1} to keeps things more conventional
- {0,0} and {n-1, n-1} are both 1
Example
{
{1, 0, 1, 1, 0, 0},
{0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 0, 1},
{1, 1, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 1, 1, 0, 1},
}
Solution:
- If we create a graph G=(V,E) where V are the coordinates (positions) in
the array marked with 1 and E are the edges between two adjecent
coordinates that are 1, we can use bread first search to find the
shortest path between any two vertices that are connected by edges.
- V and E do not need to be objects or form a graph in a classical
representation such as adjecent list or adjecent matrix, it is
created on the fly, coordinates being the vertices and adjecents being
the list of coordinates one can go from a certain coordinate.
- the BFS traversal tree is kept in a parent array with coordinates, where
each entry has an associated coordinate with it's parent from the
tree traversal.
*/
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <sstream>
using namespace std;
class MatrixShortestPath
{
struct Position
{
int x;
int y;
};
private:
vector<vector<bool>> _field;
int _n;
public:
MatrixShortestPath(vector<vector<bool>>&& field) : _field{field}, _n(field.size())
{
_field[0][0] = true;
for (int i = 0; i < _n; i++)
if (_field[i].size() != _n)
throw invalid_argument("field size");
_field[_n - 1][_n - 1] = true;
}
// creates an adjecents list with positions on the fly based on the values of
// the field array
vector<Position> GetAdjecents(Position pos)
{
static const int move[8][2]{ {-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1} };
vector<Position> adj;
for (int i = 0; i < 8; i++)
{
Position np{ pos.x + move[i][0], pos.y + move[i][1] };
if (np.x >= 0 && np.y >= 0 && np.x < _n && np.y < _n && _field[np.x][np.y])
adj.emplace_back(np);
}
return adj;
}
// returns the path as a string containing each position e.g. (0,0) (1,1) etc...
// using breath first search
string ComputeShortestPath()
{
vector<vector<Position>> parent(_n, vector<Position>(_n, Position{ -1,-1 }));
// push start into queue and mark parent of start to it self
// (0,0) = (root of BFS traversal tree)
deque<Position> q;
parent[0][0] = Position{ 0,0 };
q.emplace_front(Position{ 0, 0});
while (!q.empty())
{
auto u = q.back();
q.pop_back();
for (auto v : GetAdjecents(u))
{
if (parent[v.x][v.y].x == -1)
{
parent[v.x][v.y] = u;
if (u.x == _n - 1 && u.y == _n - 1)
{
q.clear();
break;
}
q.emplace_front(v);
}
}
}
// case where destination wasn't reached
if (parent[_n - 1][_n - 1].x == -1)
return "no path exists";
// backtrack the BFS tree from destination to start
Position pos{_n-1, _n-1};
vector<Position> path;
path.emplace_back(pos);
while (pos.x != 0 || pos.y != 0)
{
pos = parent[pos.x][pos.y];
path.emplace_back(pos);
}
// reverse the path and print it to string
stringstream ss;
for (int i = path.size() - 1; i >= 0; i--)
{
ss << string("(") << path[i].x << "," << path[i].y << ") ";
}
return ss.str();
}
};
int main()
{
MatrixShortestPath sp( {
{ 1, 0, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0 },
{ 1, 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 0, 1 },
{ 0, 0, 1, 1, 0, 1 } } );
cout << sp.ComputeShortestPath();
}
Can we move diagonally?
- Abhi August 20, 2016