Amazon Interview Question
Software Engineer / DevelopersCountry: India
Build a graph with all the numbers in same column and same row as its neighbours.
Run Dijikstra algo to find shortest path.
You are right. I did this last night 2 minutes before falling asleep, woke up in the morning and realized it was wrong :)
We need all the links as bharat suggested.
Input:-
------------------
1 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1
Output
-------------------
1 51 2 51
51 52 52 52
51 52 52 102
51 101 101 52
Start from element (0,0). Calculate lowest difficulty for row (0) and col(0).
element(1,1) --> Calculate the row (1) and col(1) starts from element (1,1)
element (2,2) --> Calculate the row(2) and col(2) starts from element (2,2)
--> Since Frog can jump any number of steps .
--> You need to consider the row(0) and row(1) for calculation of row(2)
-->also consider the col (As per Row)
element (n,n) --> Generalize it from element (2,2).
I'm not sure, but I'd do something like this:
1- Build a graph by connecting i,j to all the elements row i on its right and column j located below i,j.
2- Use shortest path algorithm to reach a particular cell from 0,0 using dijkstra.
Assume a m*n array, the total block is m*n vertices, therefore Dijikstra need O(m^2 n^2 ) time to find a path. Using a dynamic programming can reduce it to O (m*n*(m+n)), which seems better. Anybody has better ideas?
The Java code is shown as below
import java.util.LinkedList;
/**
* Dynamic programming method
* Complexity is time O(m*n*(m+n)) and space O(m*n)
* PathFinder.java
* Nov 12, 2012
*/
/**
*
*
*/
public class PathFinder {
private class Node{
int x;
int y;
int difficulty;
Node next;
public Node(int x, int y, int difficulty){
this.x = x;
this.y = y;
this.difficulty = difficulty;
}
public String toString(){
return "<" + difficulty + "(" + x + "," + y + ")" + ">";
}
}
private class Path{
int difficulty;
Node pathLink;
public void add(Node newNode){
if (pathLink == null)
pathLink = newNode;
else{
Node pointer = pathLink;
while(pointer.next != null){
pointer = pointer.next;
}
pointer.next = newNode;
}
difficulty += newNode.difficulty;
}
public String toString(){
if (pathLink == null) return null;
else{
String printOut = new String();
Node pointer = pathLink;
while (pointer.next != null){
printOut += pointer + "-->";
pointer = pointer.next;
}
return printOut + pointer;
}
}
}
Path aPath = new Path();
Node[][] nodeArray;
LinkedList<Node> bestPath = new LinkedList<Node>();
public PathFinder(int[][] difficulty){
int sizeRow = difficulty.length;
int sizeColumn = difficulty[0].length;
nodeArray = new Node[sizeRow][sizeColumn];
for (int index = 0; index < sizeRow; index ++){
for (int index1 = 0; index1 < sizeColumn; index1++){
nodeArray[index][index1] = new Node(index, index1, difficulty[index][index1]);
}
}
findPath();
}
public void findPath(){
int sizeRow = nodeArray.length;
int sizeColumn = nodeArray[0].length;
Node[][] pathArray = new Node[sizeRow][sizeColumn];
pathArray[0][0] = nodeArray[0][0];
for (int indexRow = 1; indexRow < sizeRow; indexRow++){
pathArray[indexRow][0] = new Node(0, 0, nodeArray[0][0].difficulty + nodeArray[indexRow][0].difficulty);
}
for (int indexCol = 1; indexCol < sizeRow; indexCol++){
pathArray[0][indexCol] = new Node(0, 0, nodeArray[0][0].difficulty + nodeArray[0][indexCol].difficulty);
}
for (int indexRow = 1; indexRow < sizeRow; indexRow++){
for (int indexCol = 1; indexCol < sizeColumn; indexCol++){
int minimumDif = pathArray[0][indexCol].difficulty;
int minRow = 0, minCol = indexCol;
// find minimum cost previous node
// search horizontally
for (int indexMin = 0; indexMin < indexCol; indexMin ++){
if (pathArray[indexRow][indexMin].difficulty < minimumDif){
minimumDif = pathArray[indexRow][indexMin].difficulty;
minCol = indexMin;
minRow = indexRow;
}
}
// search vertically
for (int indexMin = 0; indexMin < indexRow; indexMin++){
if (pathArray[indexMin][indexCol].difficulty < minimumDif){
minimumDif = pathArray[indexMin][indexCol].difficulty;
minCol = indexCol;
minRow = indexMin;
}
}
pathArray[indexRow][indexCol] = new Node(minRow, minCol, minimumDif + nodeArray[indexRow][indexCol].difficulty);
}
}
//System.out.println(pathArray[sizeRow - 1][sizeColumn - 1].difficulty);
int currentRow = sizeRow -1;
int currentCol = sizeColumn - 1;
int nextRow = 0;
int nextCol = 0;
while (currentRow > 0 || currentCol > 0){
aPath.add(nodeArray[currentRow][currentCol]);
//bestPath.add(new Node(currentRow, currentCol, nodeArray[currentRow][currentCol].difficulty));
nextRow = pathArray[currentRow][currentCol].x;
nextCol = pathArray[currentRow][currentCol].y;
currentRow = nextRow;
currentCol = nextCol;
}
aPath.add(nodeArray[currentRow][currentCol]);
}
public static void main(String[] args){
int[][] dif = {{1,50,1,50}, {50,1,50,1}, {1,50,1,50}, {50,1,50,1}};
PathFinder myPath = new PathFinder(dif);
System.out.printf("Easiest path is of difficulty %d by ", myPath.aPath.difficulty);
System.out.println(myPath.aPath.toString());
}
}
You can make one auxiliary matrix for the minimum difficulty as ...
mat[][] dif[][]
7 9 2 11 ----> 7 16 9 18
13 23 1 3 ----> 20 39 10 13
14 11 20 6 ----> 21 27 29 19
22 44 3 15 ----> 29 60 12 27
You can take this matrix as Matrix of pointers to nodes with structure ...
struct node{ int data; node parent};
First, Dynamically provide the required space for dif[][];
Now for making the above matrix do following ...
void PrintPath(int mat[][4],node *diff[][4]) //m*n*n
{
dif[0][0]->data = mat[0][0];
dif[0][0]->parent = NULL;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
node *temp;
if(i==0 || j==0) temp = dif[0][0]
else temp = FindMinimum(dif,i,j); //It returns the pointer to node with minimum value/data in jth column and ith row with in range of row(0,i) and column(0,j) in O(m+n) time complexity
dif[i][j]->data = temp->data + mat[i][j];
diff[i][j]->parent = temp;
}
}
temp = dif[m-1][n-1];
while(temp!=NULL)
{
cout<<temp->data;
temp = temp->parent;
}
} // Function ends Here
node *FindMinimum(node *dif[][4],int m,int n) //O(m+n)
{
node *min = dif[0][n];
for(int i=0;i<=m;i++)
if(min->data > dif[i][j]->data) min = dif[i][j];
for(int j=0;j<=n;j++)
if(min->data > dif[i][j]->data) min = dif[i][j];
return min;
}
Total Time Complexity O(m*n*(m+n))
Space Complexity O(m*n)
@ explorer : As per my understanding, u initialise d[][] with some high values.
1 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1
| |
V
1 51 2 51
51 52 101 52
51 52 3 52
51 101 52 52
actual ans is (0,0)->(0,2)->(2,2)->(2,1)->(1,1)->(1,3)->(3,3) = 7.
u'r algo fails when there is need to go back.
why not use Bellman-Ford's single-source algorithm.
d[v][i] is the shortest path from v to matrix[0][0] using i edges.
d[v][i] = min(d[x][i-1] + len(v,x)).
I changed my idea, since this question is very simple, for each node, the shortest path either comes from its left node or its upper node, thus I changed the d matrix. The following is my code:
// d for memorize
// m, M-1, N-1
int _ssp(int [][]m, int **d, int x, int y)
{
if(d[x][y]) return d[x][y];
int min = INT_MAX,
left = ssp(m, x-1, y),
up = ssp(m, x, y-1);
if(left < up){
min = left;
}else {
min = up;
}
d[x][y] = min
return min;
}
int ssp(int [][]m, int w, int h){
int **d = (int **)malloc(sizeof(int)*w*h);
int i = 0;
for(i = 0; i < w; i++){
d[0][i] = m[0][i];
}
for(i = 0; i < h; i++){
d[i][0] = m[i][0];
}
_ssp(m, d, w-1, h-1);
}
Here we need d for memorization, or we have to caculate for multiple times. Once we have run over the code, it's easy to populate some code to generate the path.
Dijkstra Algorithm
ideone.com/AgQ1e4
Point - represent a point with the total difficulty from the source
override the equals, hashCode and implement Comparable interface so that it can be put to the priority queue
calculate all points difficulty using Dijkstra algorithm
use an auxiliary array holding all points and a map which store the predecessor for each point
in the end construct the path using the predecessors map
class Point implements Comparable<Point>
{
public int x;
public int y;
public int d; //the total difficulty from the source
public Point(int x, int y)
{
this.x = x;
this.y = y;
this.d = Integer.MAX_VALUE;
}
@Override
public boolean equals(Object o)
{
Point pt = (Point)o;
return x == pt.x && y == pt.y;
}
@Override
public int hashCode()
{
return (17 + 31 * x) * 31 + y;
}
@Override
public String toString()
{
return "(" + x + ", " + y + ")";
}
@Override
public int compareTo(Point pt)
{
return d - pt.d;
}
}
public int minDifficulty(int[][] a)
{
int m = a.length;
int n = a[0].length;
Point[][] points = new Point[m][n];
Map<Point, Point> p = new HashMap<Point, Point>(); //the predecessor map
Queue<Point> q = new PriorityQueue<Point>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
Point pt = new Point(i, j);
points[i][j] = pt;
if(i == 0 && j == 0) pt.d = a[0][0];
p.put(pt, null);
q.offer(pt);
}
}
while(q.peek() != null) {
Point pt = q.poll();
//find adjacent points
List<Point> neighbours = new ArrayList<Point>();
for(int i = 0; i < m; i++) {
if(i != pt.x) neighbours.add(points[i][pt.y]);
}
for(int i = 0; i < n; i++) {
if(i != pt.y) neighbours.add(points[pt.x][i]);
}
for(Point neighbour: neighbours) {
//relax
if(q.contains(neighbour) && neighbour.d > pt.d + a[neighbour.x][neighbour.y]) {
q.remove(neighbour);
neighbour.d = pt.d + a[neighbour.x][neighbour.y];
p.put(neighbour, pt);
q.offer(neighbour);
}
}
}
//construct path
List<Point> path = new ArrayList<Point>();
for(Point pt = points[m - 1][n - 1]; pt != null; pt = p.get(pt)) path.add(0, pt);
System.out.println(path);
return points[m - 1][n - 1].d;
}
#include<algorithm>
#include<iostream>
#define M 4
#define N 4
#define D 3
#define INF 10000
using namespace std;
int a[M][N] = {{1,50,1,50},
{50,1,50,1},
{50,1,1,50},
{50,50,50,1},
};
int b[M][N] = {{1,INF,INF,INF},
{INF,INF,INF,INF},
{INF,INF,INF,INF},
{INF,INF,INF,INF}
};
void findMin(int &x,int &y)
{
int min=INF;
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
{
if(b[i][j]<min && b[i][j]>=0)
min=b[i][j],x=i,y=j;
}
}
void spreadMin(int x,int y)
{
for(int k = 0;k<M;k++)
b[k][y]=min(b[k][y],b[x][y]+a[k][y]);
for(int k = 0;k<N;k++)
b[x][k]=min(b[x][k],b[x][y]+a[x][k]);
return ;
}
int dig()
{
int minX,minY;
while(true)
{
findMin(minX,minY);
if(minX==D && minY == D) return b[D][D];
spreadMin(minX,minY);
b[minX][minY] = -1;
}
}
int main()
{
cout<<dig()<<endl;
return 0;
}
Can be done using Dynamic Programming in O(n^3) , Assuming all values are positive
Base cases , a[0.j] = a[0]+a[j]
a[j,0] = a[0]+a[j];
a[i,j] = min( min over all k's from 0to j-1 a[i,k]+a[i,j] ), min (over all k's from 0 to i-1 [k,j]+a[i,j]) )
Here is a C++ code which solves the problem, using a recursive function call.
The code of course can be optimized by building an identical sized matrix that each cell will contain the shortest jump path from (x,y) cell.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
struct node {
int x;
int y;
struct node *next;
};
struct path {
int difficulty;
struct node *pathlink;
};
int mat[3][3] = { {1, 100, 100}, {1, 1, 100}, {100, 0, 1} };
int rows = 3;
int cols = 3;
int sum = 0;
struct path jumpath;
int findLightestPath(int row, int col, struct node **output)
{
struct node *current = new struct node;
current->x = row;
current->y = col;
*output = current; // return the list from me...
if ( (row == (rows - 1) || col == (cols - 1)) ) {
printf("find path: mat[%d][%d] = %d (end)\n", row, col, (mat[row][col] + mat[rows - 1][cols - 1]));
struct node *last = new struct node;
last->x = (rows - 1);
last->y = (cols - 1);
last->next = NULL; // end of list
current->next = last;
return (mat[row][col] + mat[rows - 1][cols - 1]);
}
printf("find path: mat[%d][%d] = %d\n", row, col, mat[row][col]);
int sum = 10000000; // just a big number because I'm lazy
int tsum, i;
struct node *next = NULL;
for (i = 1; i < cols && (i + 1) < cols; i++) { // running horizontal
if ((i + 1) == cols) break;
tsum = findLightestPath(row, (col + i), &next);
if (tsum < sum) {
// delete current->next (am lazy...)
current->next = next;
sum = tsum;
} else {
// delete the list pointed by the next pointer - not needed (am lazy...)
}
} // horizontal for
printf("\n sum=%d \n", sum);
for (i = 1; (i < rows) && (i + 1) < rows; i++) { // running vertical
tsum = findLightestPath((row + i), col, &next);
if (tsum < sum) {
// delete current->next (am lazy...)
current->next = next;
sum = tsum;
} else {
// delete the list pointed by the next pointer - not needed (am lazy...)
}
} // vertical for
printf("\n sum=%d \n", sum);
return (mat[row][col] + sum);
}
void fillMatrix(int rows, int cols)
{
// random mat
/*for (int i=0; i < rows; i++)
for (int j=0; j < cols; j++)
mat[i][j] = ((rand() % 30) + 1);
*/
printf("The matrix: \n\n");
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
printf("[%d][%d]=%d ", i, j, mat[i][j]);
}
printf("\n");
}
}
int main(int argc, char *argv[])
{
jumpath.difficulty = 0;
fillMatrix(rows, cols);
jumpath.difficulty = findLightestPath(0,0, &jumpath.pathlink);
printf("Min path: %d\n", jumpath.difficulty);
// print the list
printf("The list: ");
struct node *list = jumpath.pathlink;
while (list != NULL) {
if (list->next == NULL) {
printf("(%d,%d)[%d]\n", list->x, list->y, mat[list->x][list->y]);
} else {
printf("(%d,%d)[%d]->", list->x, list->y, mat[list->x][list->y]);
}
list = list->next;
}
return 0;
}
you can do it by dynamic programming. I just implement finding difficulty part. tracing part can be done by keeping another array for path.
private static int find_minimum_difficulty(int[][]a){
int diff [][] = new int [a.length][a[0].length];
diff[0][0] = a[0][0];
for(int i=1;i<a.length;i++){
diff[i][0] = a[i][0]+a[0][0];
}
for(int i=1;i<a[0].length;i++){
diff[0][i] = a[0][i]+a[0][0];
}
for(int i=1;i<a.length;i++){
for(int j =1 ;j<a[0].length;j++){
int min = Integer.MAX_VALUE ;
for(int k=0;k<j;k++){
if(diff[i][k] < min){
min = diff[i][k];
}
}
for(int k=0;k<i;k++){
if(diff[k][j] < min){
min = diff[k][j];
}
}
diff[i][j] = a[i][j]+min;
}
}
for(int i=0;i<diff.length;i++){
for (int j = 0; j < diff[0].length; j++) {
System.out.print(diff[i][j]+"\t");
}
System.out.println();
}
return diff[a.length-1][a[0].length-1];
}
#include <bits/stdc++.h>
using namespace std;
int bfs(int si, int sj, vector<vector<int>>& grid){
int n=grid.size();
if(grid.size()==1) return grid[0][0];
priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > que;
que.push({grid[si][sj], si*n + sj});
vector<vector<bool>> vis(n,vector<bool>(n,false));
vis[si][sj]=true;
while(que.size()!=0){
pair<int,int> p = que.top();
que.pop();
int idx = p.second;
int r = idx/n;
int c = idx%n;
int wsf = p.first;
if(r==n-1 || c==n-1){
return wsf+grid[n-1][n-1];
}
for(int i=0;i<n;i++){
if(!vis[r][i]){
vis[r][i]=true;
que.push({wsf+grid[r][i], r*n + i});
}
if(!vis[i][c]){
vis[i][c] = true;
que.push({wsf+grid[i][c], i*n + c});
}
}
}
return -1;
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<vector<int>> grid(n, vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>grid[i][j];
}
}
int ans = bfs(0,0,grid);
cout<<ans<<endl;
}
return 0;
}
@amir: just considering the right and below positions may not suffice for example
- The Artist November 12, 20121 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1