## Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Written Test

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

4->5->6->7->8->7->6->5->4->5->6->7
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(3,3)->(2,3)->(1,3)->(1,2)->(1,1)->(0,1)

``````#include<iostream>
#include<math.h>

using namespace std;

int array[] = {{4,	7,	9,	8 },
{5,	6,	5,	4 },
{6,	7,	8,	5 },
{10,	9,	7,	6 }};
int processed[] = {{0,	0,	0,	0 },
{0,	0,	0,	0 },
{0,	0,	0,	0 },
{0,	0,	0,	0 }};
int in_stack[] = {{0,	0,	0,	0 },
{0,	0,	0,	0 },
{0,	0,	0,	0 },
{0,	0,	0,	0 }};
int** solution;
int record[4*4];

void dfs(int i, int j, int* n, int* len, int count)
{
if(processed[i][j] == 1)
return;

processed[i][j] = 1;
in_stack[i][j] = 1;
record[count++] = array[i][j];

if(i+1 < 4)
if(!in_stack[i+1][j] && (abs(array[i+1][j] - array[i][j]) == 1))
dfs(i+1, j, n, len, count);
if(j+1 < 4)
if(!in_stack[i][j+1] && (abs(array[i][j+1] - array[i][j]) == 1))
dfs(i, j+1, n, len, count);

if(i-1 >= 0)
if(!in_stack[i-1][j] && (abs(array[i-1][j] - array[i][j]) == 1))
dfs(i-1, j, n, len, count);

if(j-1 >= 0)
if(!in_stack[i][j-1] && (abs(array[i][j-1] - array[i][j]) == 1))
dfs(i, j-1, n, len, count);

if(count > *len)
{
if((*n != 0) && solution != NULL)
{
if(*n > 1)
{
for(int i = 0; i < *n; i++)
delete [] solution[i];
}
delete solution;
}

*len = count;
*n = 1;
solution = new int*;
*solution = new int[count];
for(int i = 0; i < count; i++)
(*solution)[i] = record[i];
}
if(count == *len)
{
int** temp = new int*[*n+1];
for(int i = 0; i < *n; i++)
{
temp[i] = new int[*len];
for(int j = 0; j < *len; j++)
temp[i][j] = solution[i][j];
}
temp[*n] = new int[*len];
for(int j = 0; j < *len; j++)
temp[*n][j] = record[j];

if((*n != 0) && solution != NULL)
{
if(*n > 1)
{
for(int i = 0; i < *n; i++)
delete [] solution[i];
}
delete solution;
}
solution = temp;

}

in_stack[i][j] = 0;
count--;
}

void find_longest_snake(int* n, int* len)
{
*n = 0;
*len = 0;

for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
{
if(processed[i][j] == 0)
dfs(i, j , n, len, 0);
}
return;
}

int main()
{
int n, len;
find_longest_snake(&n, &len);
cout << n << " " << len << endl;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < len; j++)
cout << solution[i][j] << " ";
cout << endl;
}

return 0;
}``````

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

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

I have implemented the logic of DFS. The complexity is the size of given matrix as the algo explore each cell just once.

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

how are you making sure that you traverse each matrix element only once?

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

the answer for your longest snake is in correct as you are visiting the position 1,1 twice. The answer should be 4->5->6->5->4->5->6->7->8->7->6

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

Brute force way:
for all [i, j] do a dfs and use backtracking to store all the paths which satisfy the criteria
and also the size.
After all [i, j] is done, print the path which is longest.

Any other approach which makes uses of previously calculated path?

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

You can use memoization to reuse results you alredy have

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

@tpcz: good but how to do that?Can you help with below algo?
@aasshishh: how did you handle the case of visiting only once?

``````dfs()
{
mark the node visited;

for_all_neighbours who satisfies criteria
if(!visited)
dfs(neighbour)
else
//this path is already traversed now what to do??
}``````

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

I think this is the graph problem.
Create a graph with each matrix element ,graph should be undirected graph ,maintaine visited field for each node.

find the path with property that node data value shoukld not exceed by 1 or -1.

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

do a dfs, create trees, itll be a forest... a tree for every connected component. Find the diameter of each tree. maximum wins.

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

From any point of the graph;
Then use dfs to search its neighbours
if it satisfies the condition: the difference of them is 1 or -1
then add the neighbout to some place
recursively, from this point repeat the process
to other neighbour, till search its four direct neighbours
if its neighbours are all been visited all don't satisfy the condition, judge its length is larger than the default max length(Initiall, it maybe INT_MIN),
if its length is larger than the default one or saved ones, modify the max_length, and push the list to some place.
Below is the code:

``````#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#define MAX 100

using namespace std;

int n = 0;
int board[MAX][MAX];
vector<vector<int> > res;

int mlength = INT_MIN;
int dx = {1, 0, -1, 0};
int dy = {0, 1, 0, -1};

inline int abs(int x) { return x > 0 ? x : -x; }

void dfs(int x, int y, vector<int> current, bool visited[][MAX])
{
int change = 0, i = 0;
for(i = 0; i < 4; i++)
{
if(x + dx[i] >= 0 && x + dx[i] < n &&
y + dy[i] >= 0 && y + dy[i] < n &&
!visited[x + dx[i]][y + dy[i]] &&
abs(board[x][y] - board[x + dx[i]][y + dy[i]]) == 1)
{
change = 1;
visited[x + dx[i]][y + dy[i]] = true;
current.push_back(board[x + dx[i]][y + dy[i]]);
dfs(x + dx[i], y + dy[i], current, visited);

visited[x + dx[i]][y + dy[i]] = false;
current.pop_back();
}
}
if(!change && current.size() > 0)
{
if((int)current.size() >= mlength)
{
if((int)current.size() > mlength)
{
res.clear();
mlength = current.size();
}
res.push_back(current);
for(i = 0; i < (int)current.size(); i++)
{
printf("%d ", current[i]);
}
printf("\n");
}
}
}

int find()
{
int i = 0, j = 0, k = 0;
vector<int> current;
bool visited[MAX][MAX];
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
current.clear();
memset(visited, 0, sizeof(visited));
visited[i][j] = true;
current.push_back(board[i][j]);
dfs(i, j, current, visited);
}
}
return 0;
}

int main()
{
int i = 0, j = 0;
memset(board, 0, sizeof(board));

scanf("%d", &n);
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &board[i][j]);
}
}
find();

return 0;
}``````

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

@Gabriel: how are you using the knowledge of previously calculated paths?

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

@aka
I use mlength to remember the length of current longest snakes, and use map<int, vector<int> > to remember all snakes whose length are all mlength.
Using recursive method as I wrote above, I use vector<int> current to remember the snake contents till this point, when you visited some point and can't find any neighbour of can satisfy the condition, then the snake can't be longer.
And use the length of current to compare with mlength,
(1) if it's shorter than the mlength snakes, ignore it;
(2) if it's longer than the mlength snakes, clear the map<int, vector<int> > res, push the snake into it;
(2) if it's equal to the mlength snakes, then push it to the set.

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

@Gabriel: suppose you have traversed a
4 7 9 8
5 6 5 4
6 7 8 5
10 9 7 6
Obviously you will start from node 4(0,0) and you will traverse path 4->5->6->7->8->7->6->5->4->5
So when you go to any other node such as 7(0,1) then you will have to traverse the same path again (6->7->8->7->6->5->4->5). How are you utilising your previous knowledge of previous path, so that you don't traverse the same path again?

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

@aka
Yes, I have to admit the algorithm can't avoid the situation that it maybe traverse the sampe path two times, like {1, 2, 3, 4} and {4, 3, 2, 1}.
Since if I use the recursive method, the code structure ensure I won't traverse the same path two times, for example, I won't traverse {1, 2, 3, 4} again. Since the loop will turn to the other directions, and won't traverse the same direction of any point.
Two different path may share some elements, such as {1, 2, 3, 4} and {1, 2, 3, 2}

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

@aka
And there is another problem, if some point has been pushed into the longest snakes, we can judge, this two paths' start point, we call them p1(x1, y1) and p2(x2, y2), and call the two paths P1={} and P2={}.
If p2 belongs to P1 which means the point has been visited and checked, can be ignored.
If p2 doesn't belong to P1, the program can be processed continue, even when some points exist in the two paths.

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

``````int n = 0;
int board[MAX][MAX];
bool g_visited[MAX][MAX];
vector<vector<int> > res;
vector<vector<int> > g_px;
vector<vector<int> > g_py;

int mlength = INT_MIN;
int dx = {1, 0, -1, 0};
int dy = {0, 1, 0, -1};

inline int abs(int x) { return x > 0 ? x : -x; }

void dfs(int x, int y, vector<int> current, vector<int> px, vector<int> py, bool visited[][MAX])
{
int change = 0, i = 0;
for(i = 0; i < 4; i++)
{
if(x + dx[i] >= 0 && x + dx[i] < n &&
y + dy[i] >= 0 && y + dy[i] < n &&
!visited[x + dx[i]][y + dy[i]] &&
abs(board[x][y] - board[x + dx[i]][y + dy[i]]) == 1)
{
change = 1;
visited[x + dx[i]][y + dy[i]] = true;
current.push_back(board[x + dx[i]][y + dy[i]]);
px.push_back(x + dx[i]);
py.push_back(y + dy[i]);

dfs(x + dx[i], y + dy[i], current, px, py, visited);

visited[x + dx[i]][y + dy[i]] = false;
current.pop_back();
px.pop_back();
py.pop_back();
}
}
if(!change && current.size() > 0)
{
if((int)current.size() >= mlength)
{
if((int)current.size() > mlength)
{
res.clear();
g_px.clear();
g_py.clear();
mlength = current.size();
}
res.push_back(current);
g_px.push_back(px);
g_py.push_back(py);
for(i = 0; i < (int)current.size(); i++)
{
printf("%d ", current[i]);
}
printf("\n");
}
}
}

bool checkpath(int x, int y)
{
bool ret = false;
for(int i = 0; i < (int)g_px.size() && !ret; i++)
{
for(int j = 0; j < (int)g_px[i].size() && !ret; j++)
{
if(g_px[i][j] == x && g_py[i][j] == y)
{
ret = true;
}
}
}
return ret;
}
int find()
{
int i = 0, j = 0;
vector<int> current;
vector<int> px;
vector<int> py;
bool visited[MAX][MAX];
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
if(!checkpath(i, j))
{
current.clear();
px.clear();
py.clear();
memset(visited, 0, sizeof(visited));

visited[i][j] = true;

current.push_back(board[i][j]);
px.push_back(i);
py.push_back(j);
dfs(i, j, current, px, py, visited);
}
}
}
return 0;
}

int main()
{
int i = 0, j = 0;
memset(board, 0, sizeof(board));

scanf("%d", &n);
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &board[i][j]);
}
}
find();

return 0;
}``````

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.