## Amazon Interview Question for Development Support Engineers

Country: United States

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

This is a classical BFS task in a grid graph.

``````import java.util.*;

/**
* Created by sis on 5/26/15.
*/
public class CareerCup_5671254340141056 {
private static class Point {
int x, y;

public Point(int y, int x) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "(" + (x + 1) + "," + (y + 1) +')';
}
}

public static void main(String[] args) {
int[][] m = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0}
};

for (int i = 0; i < res.size(); i++) {
System.out.printf("#%d {", i);
res.get(i).forEach(System.out::print);
System.out.println("}");
}
}

private static List<List<Point>> getAdjacentNodes(int[][] m) {
if (m.length == 0 || m[0].length == 0) {
throw new IllegalArgumentException();
}

List<List<Point>> res = new ArrayList<>();
int H = m.length;
int W = m[0].length;
boolean[][] visit = new boolean[H][W];

int[][] offsets = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

for (int ys = 0; ys < H; ys++) {
for (int xs = 0; xs < W; xs++) {
if (!visit[ys][xs] && m[ys][xs] == 1) {
visit[ys][xs] = true;

List<Point> subres = new ArrayList<>();
while (!q.isEmpty()) {
Point p = q.remove();

for (int i = 0; i < offsets.length; i++) {
int y = p.y + offsets[i][0];
int x = p.x + offsets[i][1];

if (x >= 0 && x < W && y >= 0 && y < H && !visit[y][x] && m[y][x] == 1) {

visit[y][x] = true;
}
}
}

}
}
}

return res;
}
}``````

time O(N * M) and memory O(N * M).

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

Can try the same in the recursion?

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

perfect, produces the expected result.

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

I didn't find ability to answer to a particular comment, so answering just below.
>> Can try the same in the recursion?
Yes, but in this case you will get DFS (deep). From asymptotic perspective this is equal O(N * M), but because DFS is to aggressive and tries to go deeper and deeper in recursion and ultimately we could have one recursive call for each point in stack if we have full '1' field. BFS is slightly modest and stores only border (perimeter) points.

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

Assuming allowed to change the array. Alternately, would change the array back or use a different 2d boolean array. Run time O(nm) with O(nm) memory where n and m are the dimensions of the 2d array:

``````static class Worker{
private int[][] arr;
private ArrayList<ArrayList<int[]>> results;

Worker(int[][] arr){
this.arr = arr;
this.results = new ArrayList<ArrayList<int[]>>();
}

void execute(){
ArrayList<int[]> resultList = new ArrayList<int[]>();
for(int x = 0; x < arr.length; x++){
for(int y = 0; y < arr[x].length; y++){
execute(x, y, resultList);
if(resultList.size() > 0){
resultList = new ArrayList<int[]>();
}
}
}
}

void execute(int x, int y, ArrayList<int[]> list){
if(x < 0 || x > this.arr.length-1 || y < 0 || y > this.arr[x].length -1 || this.arr[x][y] < 1){
return;
}
this.arr[x][y] = -this.arr[x][y];

this.execute(x-1, y-1, list);
this.execute(x-1, y, list);
this.execute(x-1, y+1, list);
this.execute(x, y-1, list);
this.execute(x, y+1, list);
this.execute(x+1, y-1, list);
this.execute(x+1, y, list);
this.execute(x+1, y+1, list);
}

ArrayList<ArrayList<int[]>> getResults(){
return this.results;
}
}

public static void printPixelSets(int[][] arr){
if(arr == null){
throw new NullPointerException();
}
Worker worker = new Worker(arr);
worker.execute();
ArrayList<ArrayList<int[]>> results = worker.getResults();
StringBuilder row = new StringBuilder();
for(ArrayList<int[]> set : results){
row.append('{');
for(int[] point : set){
row.append('(');
row.append(point[0]);
row.append(", ");
row.append(point[1]);
row.append(')');
}
row.append('}');
java.lang.System.out.println(row.toString());
row.setLength(0);
}
}``````

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

One more option is to use Union-Find data structure that allows us to perform union and find operations in amortized O(1) (more precisely the time complexity is counted as inverse Ackermann function). So we can go through all nodes of grids and union them if m[x][y] == 1 and the are adjacent. One additional pass we need to go through union-find data structure and place point from one union to map and return it. The total time complexity and memory is O (M * N).

``````import java.util.*;
import java.util.stream.Collectors;

/**
* Created by sis on 5/26/15.
*/
public class CareerCup_5671254340141056 {
private static class Point {
int x, y;

public Point(int y, int x) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "(" + (x + 1) + "," + (y + 1) +')';
}
}

public static void main(String[] args) {
int[][] m = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0}
};

List<List<Point>> res = ufApproach(m);

for (int i = 0; i < res.size(); i++) {
System.out.printf("#%d {", i);
res.get(i).forEach(System.out::print);
System.out.println("}");
}
}

private static class UF {
int[] parent;
int[] rank;

public UF(int size) {
this.parent = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}

this.rank = new int[size];
Arrays.fill(rank, 1);
}

public void union(int i, int j) {
int pi = find(i);
int pj = find(j);

if (rank[pi] == rank[pj]) {
parent[pi] = pj;
rank[pj]++;
} else if (rank[pi] > rank[pj]) {
parent[pj] = pi;
} else {
parent[pi] = pj;
}
}

public int find(int j) {
int p = j;
while (parent[p] != p) {
p = parent[p];
}

while (parent[j] != p) {
int x = parent[j];
parent[j] = p;
j = x;
}

return p;
}
}

private static List<List<Point>> ufApproach(int[][] m) {
if (m.length == 0 || m[0].length == 0) {
throw new IllegalArgumentException();
}

int H = m.length;
int W = m[0].length;

int[][] offsets = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
UF uf = new UF(W * H);

for (int ys = 0; ys < H; ys++) {
for (int xs = 0; xs < W; xs++) {
if (m[ys][xs] == 1) {
int value1 = ys * W + xs;

for (int i = 0; i < offsets.length; i++) {
int x = xs + offsets[i][0];
int y = ys + offsets[i][1];

if (x >= 0 && x < W && y >= 0 && m[y][x] == 1) {
int value2 = y * W + x;
uf.union(value1, value2);
}
}
}
}
}

HashMap<Integer, List<Point>> subres = new HashMap<>();
for (int i = 0; i < uf.parent.length; i++) {
int p = uf.find(i);
if (p != i || uf.rank[i] > 1) {
List<Point> points = subres.get(p);
if (points == null) {
points = new ArrayList<>();
}

points.add(new Point(i / W, i % W));
subres.put(p, points);
}
}

return subres.values().stream().collect(Collectors.toList());
}
}``````

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

Thank you all for the code. Find the code below that I came up with. I guess this is similar to zortlord solution. but it works in minimal lines of code. This is written on an assumption that I can modify the array. Please comment

``````public static void getAdjacent (int[,] array, int x, int y, int M , int N)
{
for(int xaxis = 0 ; xaxis < M ; xaxis ++)
{
for(int yaxis = 0; yaxis < N ; yaxis ++)
{
if(array[xaxis,yaxis] == 1)
{
overall = string.Empty;
}
}
}
}

public static string overall = string.Empty;

public static string findImmediateAdjacent(int[,] array, int x, int y, int M , int N)
{
if((x>=M || y >=N || y< 0 || x<0))
return null;
if (array[x, y] != 1)
return null;
else
{
overall += "(" + (x + 1) + "," + (y + 1) + ')';
array[x, y] = 0;
}

findImmediateAdjacent(array, x - 1, y -1 , M, N);
findImmediateAdjacent(array, x - 1, y, M, N);
findImmediateAdjacent(array, x - 1, y + 1, M, N);
findImmediateAdjacent(array, x , y - 1, M, N);
findImmediateAdjacent(array, x , y, M, N);
findImmediateAdjacent(array, x, y + 1, M, N);
findImmediateAdjacent(array, x+1 , y + 1, M, N);
findImmediateAdjacent(array, x+1, y - 1, M, N);
return overall;
}``````

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

``````#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int DG = sizeof(unsigned int) * 8;

struct Point {
int x, y;

Point(int ix, int iy) {
x = ix;
y = iy;
}

Point() {
x = y = 0;
}
};

void resetBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data &= ~(1 << (DG - 1 - bit));
}
}

void setBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data |= (1 << (DG - 1 - bit));
}
}

unsigned int getBit(unsigned int data, unsigned int bit) {
unsigned int res = 0;
if (bit < DG) {
res = ((data & (1 << (DG - 1 - bit))) == 0) ? 0 : 1;
}

return res;
}

void setIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;

setBit(data[I], J);
}

void resetIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;

resetBit(data[I], J);
}

int getIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;

return getBit(data[I], J);
}

bool getNeighbors(unsigned int data[], int M, int N, int i, int j, int which) {
bool anyOneSet = false;

switch (which) {
case 0:
if (i - 1 >= 0) {
if (j - 1 >= 0) {
anyOneSet = getIJ(data, i - 1, j - 1, N);
}
}
break;

case 1:
if (i - 1 >= 0) {
anyOneSet = getIJ(data, i - 1, j, N);
}
break;

case 2:
if (i - 1 >= 0) {
if (j + 1 < N) {
anyOneSet = getIJ(data, i - 1, j + 1, N);
}
}
break;

case 3:
if (j + 1 < N) {
anyOneSet = getIJ(data, i, j + 1, N);
}
break;

case 4:
if (i + 1 < M) {
if (j + 1 < N) {
anyOneSet = getIJ(data, i + 1, j + 1, N);
}
}
break;

case 5:
if (i + 1 < M) {
anyOneSet = getIJ(data, i + 1, j, N);
}
break;

case 6:
if (i + 1 < M) {
if (j - 1 >= 0) {
anyOneSet = getIJ(data, i + 1, j - 1, N);
}
}
break;

case 7:
if (j - 1 >= 0) {
anyOneSet = getIJ(data, i, j - 1, N);
}
break;

default:
break;
}

return anyOneSet;
}

void checkForIt(unsigned int data[], int M, int N, int i, int j, vector<Point>& res) {
res.push_back(Point(i, j));
resetIJ(data, i, j, N);
bool neighbor[4];
memset(neighbor, 0, sizeof(neighbor));

if (getNeighbors(data, M, N, i, j, 0)) {		// -1, -1
checkForIt(data, M, N, i - 1, j - 1, res);
}
if (getNeighbors(data, M, N, i, j, 1)) {		// -1, 0
checkForIt(data, M, N, i - 1, j, res);
}
if (getNeighbors(data, M, N, i, j, 2)) {		// -1, 1
checkForIt(data, M, N, i - 1, j + 1, res);
}
if (getNeighbors(data, M, N, i, j, 7)) {		// 0, -1
checkForIt(data, M, N, i, j - 1, res);
}
if (getNeighbors(data, M, N, i, j, 3)) {		// 0, 1
checkForIt(data, M, N, i, j + 1, res);
}
if (getNeighbors(data, M, N, i, j, 6)) {		// 1, -1
checkForIt(data, M, N, i + 1, j - 1, res);
}
if (getNeighbors(data, M, N, i, j, 4)) {		// 1, 1
checkForIt(data, M, N, i + 1, j + 1, res);
}
if (getNeighbors(data, M, N, i, j, 5)) {		// 1, 0
checkForIt(data, M, N, i + 1, j, res);
}
}

void fillResult(unsigned int data[], const int size, int M, int N, vector<vector<Point>* >& result) {
int move = 0;

while (move < size) {
if (data[move] != 0) {
for (int i = 0; (data[move] != 0) && (i < DG); ++i) {
if (getBit(data[move], i) != 0) {
vector<Point>* res = new vector<Point>();

int total = (move * DG) + i;

checkForIt(data, M, N, total / N, total % N, *res);

++i;

if (res->size() > 0) {
result.push_back(res);
} else {
delete res;
}
}
}
}

++move;
}
}

int main() {
int M;
int N;
unsigned int* data;
int input = 0;

cin >> M >> N;
const int size = (M * N - 1) / DG + 1;

data = new unsigned int[size];
memset(data, 0, sizeof(unsigned int) * size);

for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> input;

if (input != 0) {
setIJ(data, i, j, N);
}
}
}

vector<vector<Point>* > result;
fillResult(data, size, M, N, result);

if (result.size() > 0) {
vector<Point>* set = NULL;

for (size_t i = 0; i < result.size(); ++i) {
set = result[i];

if ((set != NULL) && (set->size() > 0)) {
cout << "{";
for (size_t j = 0; j < set->size(); ++j) {
Point p = set->at(j);
cout << "(" << (p.y + 1) << "," << (p.x + 1) << "),";
}
cout << "}" << endl;
} else {
cout << "Inner set#" << (i + 1) << " is empty" << endl;
}
}
} else {
cout << "Empty!" << endl;
}

return 0;
}``````

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

BFS it is.

``````internal List<string> BFSOnAGridGraph(int[,] matrix, int sizeX, int sizeY)
{
var result = new List<string>();
for (var a = 0; a < sizeX; a++)
{
for (var b = 0; b < sizeY; b++)
{
var tempResult = string.Empty;
if (matrix[a, b] == 1)
{
var queue = new Queue<int[]>();
queue.Enqueue(new int[] { a, b });
matrix[a, b] = 9;
tempResult = string.Format("({0}, {1}) ", a + 1, b + 1);

while (queue.Count != 0)
{
var elem = queue.Dequeue();
for (var i = -1; i <= 1; i++)
{
for (var j = -1; j <= 1; j++)
{
if (elem[0] + i >= 0 && elem[1] + j >= 0 && elem[0] + i < sizeX && elem[1] + j < sizeY)
{
if (matrix[elem[0] + i, elem[1] + j] != 9 && matrix[elem[0] + i, elem[1] + j] == 1)
{
queue.Enqueue(new int[] { elem[0] + i, elem[1] + j });
Console.WriteLine("{0} , {1} ", elem[0] + i + 1, elem[1] + j + 1);
tempResult += string.Format("({0}, {1}) ", elem[0] + i + 1, elem[1] + j + 1);
matrix[elem[0] + i, elem[1] + j] = 9;
}
}
}
}
}
}
}
}
return result;``````

}

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

?

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

Here is the simplest way:

``````public static void main(String[] args) {
int[][] inputMatrix = {
{0,1,0,1,1},
{1,1,0,0,1},
{0,1,1,0,1},
{0,1,0,1,1},
{0,1,1,0,1}
};

for(int i=0;i<inputMatrix.length;i++){
System.out.print("Array "+(i+1) + " {");
for(int j=0;j<inputMatrix[i].length;j++){
if(inputMatrix[i][j]==1)
System.out.print("{"+(i+1)+","+(j+1)+" }");
}
System.out.println("}");
}
}``````

Output:
Array 1 {{1,2 }{1,4 }{1,5 }}
Array 2 {{2,1 }{2,2 }{2,5 }}
Array 3 {{3,2 }{3,3 }{3,5 }}
Array 4 {{4,2 }{4,4 }{4,5 }}
Array 5 {{5,2 }{5,3 }{5,5 }}

Regards,
-DShingan

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

You are displaying the elements that are connected to each other. The question is to identify the elements that are adjacent (straight or diagonally). Is there a better answer using graph theory and better big-O time performance?

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

Simplest way

``````public static void main(String[] args) {
int[][] inputMatrix = {
{0,1,0,1,1},
{1,1,0,0,1},
{0,1,1,0,1},
{0,1,0,1,1},
{0,1,1,0,1}
};

for(int i=0;i<inputMatrix.length;i++){
System.out.print("Array "+(i+1) + " {");
for(int j=0;j<inputMatrix[i].length;j++){
if(inputMatrix[i][j]==1)
System.out.print("{"+(i+1)+","+(j+1)+" }");
}
System.out.println("}");
}
}``````

Output:

Array 1 {{1,2 }{1,4 }{1,5 }}
Array 2 {{2,1 }{2,2 }{2,5 }}
Array 3 {{3,2 }{3,3 }{3,5 }}
Array 4 {{4,2 }{4,4 }{4,5 }}
Array 5 {{5,2 }{5,3 }{5,5 }}

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.