## Amazon Interview Question

• 1
of 1 vote

Country: United States

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

``````void elements(int a[][N],int x,int y,int col,int *n)
{
if(x<0 || x>=N || y<0 || y>=N || a[x][y]!=col || a[x][y]==-1)
return;
(*n)++;
a[x][y]=-1;
printmatrix(a);
elements(a,x+1,y,col,n);
elements(a,x-1,y,col,n);
elements(a,x,y+1,col,n);
elements(a,x,y-1,col,n);
}``````

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

``````// Assumptions:
// 1) Intensity is represented by an integer.
// 2) A pixel is reacable by another pixel if they are facing each other
//    vertically or horizontally, but not diagonally.
#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;

// Input format:
// i j
// n
// [n * n numbers]
//
// * (i, j) denotes the given pixel at (i + 1)th row, (j + 1)th column
// * n is the width and height of the screen
// * Each number is separated by whitespace characters.
//
// Sample input:
// 2 2
// 5
// 0 0 1 2 0
// 0 1 3 1 0
// 0 0 0 1 1
// 1 2 0 0 4
// 0 0 0 0 0
//
// Sample output:
// 13
int main() {
int i, j, n;
cin >> i >> j >> n;
int index = i * n + j;
int size = n * n;
int* screen = new int[size];
for (int i = 0; i < size; i++) {
cin >> screen[i];
}
int target_intensity = screen[index];
int count = 0;
unordered_set<int> visited;
stack<int> s;
s.push(index);
while (!s.empty()) {
int cur = s.top();
s.pop();
if (visited.count(cur) != 0) continue;
visited.insert(cur);
if (screen[cur] != target_intensity) continue;
count++;
int cur_i = cur / n;
int cur_j = cur % n;
if (cur_i > 0) s.push(cur - n);
if (cur_j > 0) s.push(cur - 1);
if (cur_i < n - 1) s.push(cur + n);
if (cur_j < n - 1) s.push(cur + 1);
}
cout << count << endl;
delete[] screen;
}``````

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

FYI, it's a simple depth first search.

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

Talk about an overly complicated and unnecessary use of sets and stacks. See Nitin's response below: since it's a NxN screen, consider it a large 2D array (of pixels). All you need to do, based on your assumptions is, do a +1, -1 and compare if they're equal, and return the total count.

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

If the screen array can be modified, my algorithm can be changed so that the set is not necessary. It's obvious it can be modified in my code since they are just holding the input. But if it is written as a reusable function like Nitin's, then the assumption that the screen array can be modified may not always be true. And if it is not true, using a hash set is more memory efficient way than creating a copy of the screen array. Also Nitin's takes more memory for its call stacks. As N goes to large, the difference becomes significant.

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.