Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

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)

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

using namespace std;

int array[][4] = {{4,	7,	9,	8 },
              {5,	6,	5,	4 },
              {6,	7,	8,	5 },
              {10,	9,	7,	6 }};
int processed[][4] = {{0,	0,	0,	0 },
              {0,	0,	0,	0 },
              {0,	0,	0,	0 },
              {0,	0,	0,	0 }};
int in_stack[][4] = {{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;
}

- aasshishh April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

logic please?

- aka April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aasshishh April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous April 07, 2013 | Flag
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?

- aka April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can use memoization to reuse results you alredy have

- tpcz April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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??
}

- aka April 07, 2013 | Flag
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.

- Anonymous April 06, 2013 | Flag Reply
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.

- Anonymous April 08, 2013 | Flag Reply
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[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;
}

- Gabriel April 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka April 18, 2013 | Flag
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.

- Gabriel April 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 April 18, 2013 | Flag
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}

- Gabriel April 18, 2013 | Flag Reply
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.

- Gabriel April 18, 2013 | Flag Reply
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[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;
}

- Gabriel April 19, 2013 | 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