Amazon Interview Question
Research ScientistsCountry: United States
Interview Type: Phone Interview
You start a DFS/BFS everytime you meet a cell with 1 and assign it the current value of the counter and all the cells with value 1 you meet while DFS/BFS. The counter should be incremented everytime DFS/BFS is done. Consider cells with value smaller than counter, but greater than 1 as visited. I suggest to start with the value counter 2, as it allows to skip the special case, when the label should be equal 1. (It's not said that the first label has to be equal 1).
Go left/right, top/bottom, and tag any marked cell. When tagging, tag any adjacent cells recursively. If any tagged, increment label index.
./label_grid.py
0000011000
2200110000
2220011000
0003300000
#!/usr/bin/env python
GRID="""0000011000
1100110000
1110011000
0001100000""".split('\n')
ROWS = len(GRID)
COLS = len(GRID[0])
def tag(gridlines, count, row, col):
# tag cell if marked, and tag all connected
# continguous cells. return True if tagged.
if gridlines[row][col] != 'A':
return False
# find all 'A' elements that are contiguous
gridlines[row][col] = chr(ord('0') + count)
# check if on top/left/right/bottom edge
top = row == 0
bottom = row == ROWS-1
left = col == 0
right = col == COLS - 1
if not left:
tag(gridlines, count, row, col-1)
if not right:
tag(gridlines, count, row, col+1)
if not top:
tag(gridlines, count, row-1, col)
if not bottom:
tag(gridlines, count, row+1, col)
return True
def label(gridlines, count, pos):
# tag each marked cell, and increment label
# if tagged
for i in range(pos, ROWS*COLS):
row = i / COLS
col = i % COLS
if tag(gridlines, count, row, col):
count += 1
return label(gridlines, count, i + 1)
if __name__ == '__main__':
# first convert '1' to 'A' to identify
# unlabeled sections, and split to characater arrays
grid = [[ch for ch in line.replace('1', 'A')] for line in GRID]
label(grid, 1, 0)
for line in grid:
print ''.join(line)
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct coOrdinates
{
int row;
int col;
coOrdinates(int i ,int j): row(i) , col(j){}
};
void markRegion(vector<vector<int> >& matrix , vector<vector<bool> >& visited, int row , int col , int regionNum)
{
queue<coOrdinates> q;
q.push(coOrdinates(row,col));
int i, j;
while(!q.empty())
{
i = q.front().row;
j = q.front().col;
q.pop();
if(i >= 0 && i< matrix.size() &&
j >= 0 && j< matrix[0].size() &&
!visited[i][j] && matrix[i][j] == 1)
{
// Marking with pixel with region number
matrix[i][j] = regionNum;
// making sure we are not visiting again
visited[i][j] = true;
// Top
q.push(coOrdinates(i+1 , j ));
// bottom
q.push(coOrdinates(i-1 , j ));
// Right
q.push(coOrdinates(i , j+1));
// left
q.push(coOrdinates(i , j-1));
}
}
}
void markRegions(vector<vector<int> >& matrix)
{
vector<vector<bool> > visited(matrix.size() , vector<bool>(matrix[0].size() , false));
int regionNum = 1;
for(int i = 0 ; i < matrix.size() ; ++i)
{
for(int j = 0 ; j < matrix[0].size() ; ++j)
{
// Call this function
if(matrix[i][j] == 1 && !visited[i][j])
{
markRegion(matrix , visited , i , j , regionNum);
++regionNum;
}
}
}
}
int main()
{
vector<vector<int> > matrix = {{0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
{1, 1, 0, 0, 1, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0}};
markRegions(matrix);
// print results
for(int i = 0 ; i < matrix.size() ; ++i)
{
for(int j = 0 ; j < matrix[0].size() ; ++j)
{
cout<<matrix[i][j]<<" ";
}
cout<<"\n";
}
}
public class MatrixVisits {
/**
* The phylosofy of the code is this.
* - Iterate the input matrix (visits)
* - If I found a visitor I search how big is that neigbor and update the ourput matrix
* @param visits
* @return
*/
public int[][] getNeighbors(int[][] visits) {
// Create output matrix
int[][] neigh = new int[visits.length][visits[0].length];
// count of neigbors
int count = 1;
// Iterates in visits (input)
for (int n = 0; n < visits.length; n++) {
for (int m = 0; m < visits[0].length; m++) {
// Enter in recursive case only if there is a visit and is not part of the finded neighbors yet
if (visits[n][m] > 0 && neigh[n][m] == 0) {
checkNeighbors(n, m, count, neigh, visits);
count++;
} else if (visits[n][m] == 0) {
neigh[n][m] = 0;
}
}
}
return neigh;
}
private void checkNeighbors(int n, int m, int count, int[][] neigh, int[][] visits) {
// Base Case - Outside of the matrix
if (n < 0 || m < 0 || n >= neigh.length || m >= neigh[0].length) {
return;
} else {
// Recursive Case - check Neighbors if there is a visit there or if the count need to be updated.
if (visits[n][m] > 0 && neigh[n][m] < count) {
neigh[n][m] = count;
checkNeighbors(n - 1, m, count, neigh, visits);
checkNeighbors(n, m - 1, count, neigh, visits);
checkNeighbors(n + 1, m, count, neigh, visits);
checkNeighbors(n, m + 1, count, neigh, visits);
}
}
}
public static void main(String[] args) {
// TODO code application logic here
MatrixVisits matriz1 = new MatrixVisits();
int[][] visitas = {
{0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
{1, 1, 0, 0, 1, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0}
};
int[][] neigh = matriz1.getNeighbors(visitas);
for (int i = 0; i < neigh.length; i++) {
System.out.print("[");
for (int j = 0; j < neigh[0].length; j++) {
System.out.print("" + neigh[i][j] + ",");
}
System.out.println("]");
}
}
def algo( data ):
ctr = 0;
for y in range(0,len(data)):
x = 0;
while x < len(data[y]):
mu=0;
run=[];
while data[y][x] > 0:
mu=max(data[y-1][x] if y >0 else 0,mu);
run.append((x,y));
x+=1;
if len(run) != 0 and mu == 0:
ctr+=1;
replace=ctr;
else:
replace=mu;
for (x,y) in run:
data[y][x]=replace;
x+=1;
return data;
list1=[[0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
[1, 1, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0]]
list2=[]
for i in range(0,len(list1)):
for j in range(0,len(list1[i])):
if list1[i][j]==1:
list2+=[[i,j]]
list3=[]
list3+=[[list2[0]]]
del list2[0]
x=0
while len(list2)!=0:
p=len(list3[x])
for y in range(0,p):
for i in range(0,len(list2)):
try:
if (list2[i][0]==list3[x][y][0]+1 and list2[i][1]==list3[x][y][1]) or (list2[i][1]==list3[x][y][1]+1 and list2[i][0]==list3[x][y][0]) or (list2[i][0]==list3[x][y][0]-1 and list2[i][1]==list3[x][y][1]) or (list2[i][1]==list3[x][y][1]-1 and list2[i][0]==list3[x][y][0]):
list3[x]+=[list2[i]]
del list2[i]
except:
continue
q=len(list3[x])
if p==q and len(list2)!=0:
x+=1
list3+=[[list2[0]]]
del list2[0]
for i in range(0,len(list3)):
for j in range(0,len(list3[i])):
list1[list3[i][j][0]][list3[i][j][1]]=i+1
for i in range(0,len(list1)):
print list1[i]
R Code:
find_segment <- function(m) {
r = 4
c = 10
for (i in 1:r) {
for (j in 1:c) {
if (m[i,j]==-1) {
return (c(i,j))
}
}
}
return (c(-1,-1))
}
label_segment <-function(m, p, curr_l) {
i = p[1]
j = p[2]
m[i,j] = curr_l
if (i < 4){
if (m[i+1,j]==-1) {
m = label_segment(m, c(i+1,j), curr_l)
}
}
if (i>1) {
if (m[i-1,j]==-1) {
m = label_segment(m, c(i-1,j), curr_l)
}
}
if (j < 10){
if (m[i,j+1]==-1) {
m = label_segment(m, c(i,j+1), curr_l)
}
}
if (j>1) {
if (m[i,j-1]==-1) {
m = label_segment(m, c(i,j-1), curr_l)
}
}
return (m)
}
a=c(0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0)
a = matrix(a, nrow = 4)
a=a*-1
label_count = 0
while (min(a)<0) {
label_count = label_count+1
p = find_segment(a)
a = label_segment(a, p, label_count)
}
Dynamic R Code:
find_segment <- function(m) {
r = length(m[,1])
c = length(m[1,])
for (i in 1:r) {
for (j in 1:c) {
if (m[i,j]==-1) {
return (c(i,j))
}
}
}
return (c(-1,-1))
}
label_segment <-function(m, p, curr_l) {
i = p[1]
j = p[2]
m[i,j] = curr_l
if (i < length(m[,1]) ){
if (m[i+1,j]==-1) {
m = label_segment(m, c(i+1,j), curr_l)
}
}
if (i>1) {
if (m[i-1,j]==-1) {
m = label_segment(m, c(i-1,j), curr_l)
}
}
if (j < length(m[1,])){
if (m[i,j+1]==-1) {
m = label_segment(m, c(i,j+1), curr_l)
}
}
if (j>1) {
if (m[i,j-1]==-1) {
m = label_segment(m, c(i,j-1), curr_l)
}
}
return (m)
}
a=c(0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0)
a = matrix(a, ncol = 12)
a=a*-1
label_count = 0
while (min(a)<0) {
label_count = label_count+1
p = find_segment(a)
a = label_segment(a, p, label_count)
}
a
Implements disjoint set data structure with linked lists. Code merges all lists A,B ->C when they find out that they are connected, deletes A,B. Currently prints the total number of connected components but they are completed constructed and labeled in the code below
var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}
//MIT license, authored by Ling Qing Meng
//'4\nYYNN\nYYYN\nNYYN\nNNNY'
//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
adjMatrix.push(reformat[i]);
}
//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
var s = new LinkedList();
s.add(i);
sets.push(s);
}
//populate friend potentials using combinatorics, then filters
var people = [];
var friends = [];
for (var i = 0; i < N; i++) {
people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
friends.push(potentialFriends[i]);
}
}
//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
var x = friends[i][0];
var y = friends[i][1];
if (FindSet(x) != FindSet(y)) {
sets.push(MergeSet(x,y));
}
}
for (var i = 0; i < sets.length; i++) {
//sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);
//Linked List data structures neccesary for above to work
function Node(){
this.data = null;
this.next = null;
}
function LinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
// Add node to the end
this.add = function(data){
var node = new Node();
node.data = data;
if (this.head == null){
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};
this.contains = function(data) {
if (this.head.data === data)
return this;
var next = this.head.next;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};
this.traverse = function() {
var current = this.head;
var toPrint = '';
while (current !== null) {
//callback.call(this, current); put callback as an argument to top function
toPrint += current.data.toString() + ' ';
current = current.next;
}
console.log('list data: ',toPrint);
}
this.merge = function(list) {
var current = this.head;
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
current.next = list.head;
this.size += list.size;
return this;
};
this.reverse = function() {
if (this.head == null)
return;
if (this.head.next == null)
return;
var currentNode = this.head;
var nextNode = this.head.next;
var prevNode = this.head;
this.head.next = null;
while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
this.head = currentNode;
return this;
}
}
/**
* GENERAL HELPER FUNCTIONS
*/
function FindSet(x) {
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
return sets[i].contains(x);
}
}
return null;
}
function MergeSet(x,y) {
var listA,listB;
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
listA = sets[i].contains(x);
sets.splice(i,1);
}
}
for (var i = 0; i < sets.length; i++) {
if (sets[i].contains(y) != null) {
listB = sets[i].contains(y);
sets.splice(i,1);
}
}
var res = MergeLists(listA,listB);
return res;
}
function MergeLists(listA, listB) {
var listC = new LinkedList();
listA.merge(listB);
listC = listA;
return listC;
}
//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
return matrix[pair[0]].charAt(pair[1]);
}
function k_combinations(set, k) {
var i, j, combs, head, tailcombs;
if (k > set.length || k <= 0) {
return [];
}
if (k == set.length) {
return [set];
}
if (k == 1) {
combs = [];
for (i = 0; i < set.length; i++) {
combs.push([set[i]]);
}
return combs;
}
// Assert {1 < k < set.length}
combs = [];
for (i = 0; i < set.length - k + 1; i++) {
head = set.slice(i, i+1);
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
combs.push(head.concat(tailcombs[j]));
}
}
return combs;
}
1. Visit every node (x,y)
2. if not yet discovered (discovered[x][y]==0) then increment group_count and update group[x][y] with group_count.
3. create a stack (mystack = []) to add discovered nodes (discovered[x][y] == 1)
4. for every discovered node update its group with the current group_count. Then add to the stack all its valid neighbours (discovered nodes).
5. then discovered[x][y] = 2 signals that the node was already processed.
6. print the groups matrix.
from sys import stdin
def create_zero_matrix(m,n):
return [[0 for _ in range(n)] for _ in range(n)]
def print_mat(mat, m, n):
for i in range(m):
for j in range(n):
print(mat[i][j],end ='')
print('')
def find_candidates(elem, mat, discovered, m, n):
xe, ye = elem
candidates = []
if xe-1 >=0:
if mat[xe-1][ye] and discovered[xe-1][ye] == 0:
candidates.append((xe-1, ye))
if xe+1 <m:
if mat[xe+1][ye] and discovered[xe+1][ye] == 0:
candidates.append((xe+1, ye))
if ye-1 >=0:
if mat[xe][ye-1] and discovered[xe][ye-1] == 0:
candidates.append((xe, ye-1))
if ye+1 <n:
if mat[xe][ye+1] and discovered[xe][ye+1] == 0:
candidates.append((xe, ye+1))
return candidates
if __name__ == '__main__':
m,n = map(int, stdin.readline().split())
mat = [None for _ in range(m)]
for i in range(m):
mat[i] = [int(x) for x in stdin.readline().split()]
discovered = create_zero_matrix(m,n)
group = create_zero_matrix(m,n)
group_count = 0
for x in range(m):
for y in range(n):
node = mat[x][y]
if node != 0:
if discovered[x][y] == 0:
group_count += 1
mystack = [(x,y)]
discovered[x][y] = 1
while len(mystack) != 0:
elem = mystack.pop()
xe, ye = elem
group[xe][ye] = group_count
candidates = find_candidates(elem, mat, discovered, m, n)
for c in candidates:
mystack.append(c)
discovered[xe][ye] = 2
print_mat(group, m,n)
import numpy as np
x = np.random.binomial(1,.3,size=(9,9))
label = np.zeros_like(x)
def check(pos):
i, j = pos
if (i<0) | (i>=x.shape[0]) | (j<0) | (j>=x.shape[1]):
return False
else:
return (x[i,j]==1) & (label[i,j]==0)
def propagate(pos,l):
i, j = pos
for a, b in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
if check((a,b)):
label[a,b]=l
propagate((a,b),l)
l = 5
for i in range(x.shape[0]):
for j in range(x.shape[1]):
if check((i,j)):
label[i,j] = l
propagate((i,j),l)
l += 1
print(label)
Implementing this using a scan and DFS in O(m*n) time complexity (array dimensions). There is probably a way to do this without using a static group identifier but I didn't put much effort into finding that way.
- Chris August 01, 2014