Amazon Interview Question
Applications DevelopersCountry: United States
Interview Type: In-Person
private List<String> pathList;
public List<String> getPaths(int destX, int destY){
pathList = new ArrayList<String>();
getPaths(0,0, destX, destY, "");
return pathList;
}
private void getPaths(int currX, int currY, int destX, int destY, String path){
path += String.format(" (%d,%d)", currX , currY);
if( currX == destX && currY == destY){ //reach the (destX,destY) point
pathList.add(path);
}else if( currX > destX || currY > destY){//wrong way
return;
}else {
getPaths(currX + 1, currY, destX, destY, path);//down
getPaths(currX , currY + 1, destX, destY, path);//right
}
}
C++ implementation (This is my first time answering a question here so helpful advice is welcome)
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
const int MATRIX_SIZE = 5;
void TraverseMatrix(int x, int y, string path);
int main() {
TraverseMatrix(0,0, "");
return 0;
}
void TraverseMatrix(int x, int y, string path){
//Make path pretty
stringstream ss;
ss << x;
string node = "(" + ss.str() + ",";
ss.str("");
ss << y;
node += ss.str() + ") -> ";
if(x == (MATRIX_SIZE - 1) && y == (MATRIX_SIZE - 1)){ //Reached destination, print path
cout << path << "(" << x << "," << y << ")" << endl << endl;
}else if(x == (MATRIX_SIZE - 1)){ //Reached right boundary, go down
path.append(node);
TraverseMatrix(x, y + 1, path);
}else if(y == (MATRIX_SIZE - 1)){ //Reached lower boundary, go right
path.append(node);
TraverseMatrix(x + 1, y, path);
}else{ //Traverse down or right
path.append(node);
//Go right
TraverseMatrix(x + 1, y, path);
//Go down
TraverseMatrix(x, y + 1, path);
}
}
C++ Implementation
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
const int MATRIX_SIZE = 5;
void TraverseMatrix(int x, int y, string path);
int main() {
TraverseMatrix(0,0, "");
return 0;
}
void TraverseMatrix(int x, int y, string path){
//Make path pretty
stringstream ss;
ss << x;
string node = "(" + ss.str() + ",";
ss.str("");
ss << y;
node += ss.str() + ") -> ";
if(x == (MATRIX_SIZE - 1) && y == (MATRIX_SIZE - 1)){ //Reached destination, print path
cout << path << "(" << x << "," << y << ")" << endl << endl;
}else if(x == (MATRIX_SIZE - 1)){ //Reached right boundary, go down
path.append(node);
TraverseMatrix(x, y + 1, path);
}else if(y == (MATRIX_SIZE - 1)){ //Reached lower boundary, go right
path.append(node);
TraverseMatrix(x + 1, y, path);
}else{ //Traverse down or right
path.append(node);
//Go right
TraverseMatrix(x + 1, y, path);
//Go down
TraverseMatrix(x, y + 1, path);
}
}
C++ Implementation (This is my first time posting here, so helpful advice is welcomed)
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
const int MATRIX_SIZE = 5;
void TraverseMatrix(int x, int y, string path);
int main() {
TraverseMatrix(0,0, "");
return 0;
}
void TraverseMatrix(int x, int y, string path){
//Make path pretty
stringstream ss;
ss << x;
string node = "(" + ss.str() + ",";
ss.str("");
ss << y;
node += ss.str() + ") -> ";
if(x == (MATRIX_SIZE - 1) && y == (MATRIX_SIZE - 1)){ //Reached destination, print path
cout << path << "(" << x << "," << y << ")" << endl << endl;
}else if(x == (MATRIX_SIZE - 1)){ //Reached right boundary, go down
path.append(node);
TraverseMatrix(x, y + 1, path);
}else if(y == (MATRIX_SIZE - 1)){ //Reached lower boundary, go right
path.append(node);
TraverseMatrix(x + 1, y, path);
}else{ //Traverse down or right
path.append(node);
//Go right
TraverseMatrix(x + 1, y, path);
//Go down
TraverseMatrix(x, y + 1, path);
}
}
Dynamic programming solution for a NxM matrix in C#
public int GetNumbPaths(int numRows, int numCols)
{
int[,] matrix = new int[numRows, numCols];
for (int i = 0; i < numRows; i++)
matrix[i, 0] = 1;
for (int j = 0; j < numCols; j++)
matrix[0, j] = 1;
for (int i = 1; i < numRows; i++)
for (int j = 1; j < numCols; j++)
matrix[i, j] = matrix[i - 1, j] + matrix[i, j - 1];
return matrix[numRows - 1, numCols - 1];
}
c# implementation.
Running space 2*n.
Space complexity O(n).
using System;
namespace AllPossiblePaths {
class Program {
static private int Get( int i, int j, int len ) {
int res = 0;
if ( i == j && j == len - 1 ) {
return 1;
}
if ( j < len - 1 ) {
res += Get( i, j + 1, len );
}
if ( i < len - 1 ) {
res += Get( i + 1, j, len );
}
return res;
}
static void Main( string[] args ){
var res = Get( 0, 0, 8 );
Console.WriteLine( res );
Console.ReadLine();
}
}
}
void moveInCircularMotion(int (*a)[col])
{
int i = 0, j = 0, temp = a[i][j];
while( i < row - 1)
{
a[i][j] = a[i+1][j];
i++;
}
while( j < col - 1)
{
a[i][j] = a[i][j+1];
j++;
}
while( i > 0)
{
a[i][j] = a[i-1][j];
i--;
}
while( j > 0)
{
if(j == 1)
{
a[i][j] = temp;
break;
}
a[i][j] = a[i][j-1];
j--;
}
}
An improvement from my previous post, dynamic programming, just use two rows for previous and current row. space O(n) C# implementation
- hnatsu December 16, 2015