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])
            return totalDFS;
        if(image[y][x] > 0) {
            //If we're here, DFS
            totalDFS++;
            groupNumber++;
            processDFS(image, visited, y, x);
        }
        visited[y][x] = true;
        return totalDFS;
    }
    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);
        }
    }
}

- Chris August 01, 2014 | Flag Reply
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).

- joe kidd August 01, 2014 | Flag Reply
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)

- Dan August 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dan August 01, 2014 | Flag
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";
	}
}

- MIG August 02, 2014 | Flag Reply
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("]");
        }
    }

- Adrian Garcia August 04, 2014 | Flag Reply
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;

- atripp August 07, 2014 | Flag Reply
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]

- Aalekh Neema August 13, 2014 | Flag Reply
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)
}

- Zaigham November 12, 2014 | Flag Reply
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

- Zaigham November 12, 2014 | Flag Reply
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'

    //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;
    }

- ling.q.meng March 27, 2015 | Flag Reply
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__':
	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)

- marcelousp June 16, 2017 | Flag Reply
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)

- J July 04, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More