Amazon Interview Question Development Support Engineers
Country: United States
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.
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){
this.results.add(resultList);
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;
}
list.add(new int[]{x, y});
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);
}
}
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());
}
}
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)
{
Console.WriteLine(findImmediateAdjacent(array, xaxis, yaxis, M, N));
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);
findImmediateAdjacent(array, x+1, y, M, N);
return overall;
}
#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;
}
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;
}
}
}
}
}
result.Add(tempResult);
}
}
}
return result;
}
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
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 }}
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} }; List<List<Point>> res = getAdjacentNodes(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 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}}; Queue<Point> q = new LinkedList<>(); 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; q.add(new Point(ys,xs)); List<Point> subres = new ArrayList<>(); while (!q.isEmpty()) { Point p = q.remove(); subres.add(p); 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; q.add(new Point(x, y)); } } } res.add(subres); } } } return res; } }time O(N * M) and memory O(N * M).
- igor.s.sokolov May 27, 2015