Amazon Interview Question for Applications Developers

Country: United States
Interview Type: In-Person

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

An improvement from my previous post, dynamic programming, just use two rows for previous and current row. space O(n) C# implementation

``````public int GetNumPaths(int numRows, int numCols)
{
int[] prevRow = new int[numCols];
int[] currRow = new int[numCols];

currRow[0] = prevRow[0] = 1;
for (int i = 0; i < numRows; i++)
{

for (int j = 1; j < numCols; j++)
currRow[j] = currRow[j - 1] + prevRow[j];
int[] temp = currRow;
currRow = prevRow;
prevRow = temp;
}

return prevRow[numCols - 1];
}``````

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

can't understand how the space can be O(n). the question wants all possible paths. The total paths will be 2^n where n is the size of square. you solution only returns the number of paths

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

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

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

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

}
}``````

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

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

}``````

}

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

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

}``````

}

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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.