Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
I have implemented the logic of DFS. The complexity is the size of given matrix as the algo explore each cell just once.
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?
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[4] = {1, 0, -1, 0};
int dy[4] = {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;
}
@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.
@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?
@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}
@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.
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[4] = {1, 0, -1, 0};
int dy[4] = {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;
}
The answer should be
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)
- aasshishh April 06, 2013