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

- hnatsu December 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mehraz January 05, 2016 | Flag
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
	        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
	    }
	}

- Adnan Ahmad March 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

		
	}
}

- Mike December 15, 2015 | Flag Reply
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);

		
	}

}

- Mike December 15, 2015 | Flag Reply
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);

		
	}

}

- Mike December 15, 2015 | Flag Reply
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];
}

- hnatsu December 16, 2015 | Flag Reply
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 );
            Console.ReadLine();
        }
    }
}

- zr.roman December 19, 2015 | Flag Reply
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--;
}
}

- sumeet.yaduwanshi December 16, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More