## Amazon Interview Question for Research Scientists

Country: United States
Interview Type: Phone Interview

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

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.

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

/**
* @author chris moran
*/
public class ScanWithDFS {
public static void main(String[] args) {
int[][] image = new int[][]{
{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}
};
boolean[][] visited = new boolean[image.length][image[0].length];
for(boolean[] visit : visited) {
Arrays.fill(visit, false);
}
int total = 0;
for(int y = 0; y < image.length; y++) {
for(int x = 0; x < image[y].length; x++) {
total += processMatrix(image, visited, y, x);
}
}
System.out.println("Detected: " + total);
for(int[] arr : image) {
System.out.println(Arrays.toString(arr));
}
}
static int groupNumber = 0;
private static int processMatrix(int[][] image, boolean[][] visited, int y, int x) {
int totalDFS = 0;
if(visited[y][x])
if(image[y][x] > 0) {
//If we're here, DFS
totalDFS++;
groupNumber++;
processDFS(image, visited, y, x);
}
visited[y][x] = true;
}
private static void processDFS(int[][] image, boolean[][] visited, int y, int x) {
if(y < 0 || x < 0 || y >= image.length|| x >= image[y].length  || visited[y][x])
return;
visited[y][x] = true;

if(image[y][x] > 0) {
image[y][x] = groupNumber;
processDFS(image, visited, y, x + 1);
processDFS(image, visited, y, x - 1);
processDFS(image, visited, y + 1, x);
processDFS(image, visited, y - 1, x);
}
}
}``````

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

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).

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

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)``````

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

(could get rid of the "return" on the recursive call to label, and just continue to the next iteration of the loop, since count is incremented and i is incremented. That's marginally better.)

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

``````#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";
}
}``````

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

``````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("]");
}
}``````

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

``````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;``````

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

``````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]``````

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

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)
}``````

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

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``````

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

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'

var reformat = input.split(/\n/);
var N = reformat[0];
for (var i = 1; i < reformat.length; i++) {
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; 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++){
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;
}

this.tail = null;
this.size = 0;

// Add node to the end
var node = new Node();
node.data = data;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};

this.contains = function(data) {
return this;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};

this.traverse = function() {
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 next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
this.size += list.size;
return this;
};

this.reverse = function() {
return;
return;

while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = 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) {
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++) {
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
}
}
return combs;
}``````

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

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__':

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)``````

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

``````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)``````

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.