Amazon Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

I was asked a variant of this question recently the question was to ind out all the unique objects from these matrix. Consider for example:
0 1 1 1 0
0 0 1 0 0
1 1 0 1 0
1 1 0 1 1
0 0 0 1 0
so for example the above matrix contains two kinds of shapes one is
1 1 1
1
and the other is
1 1
1 1
Note that the third shape which is
1
1 1
1
is actually the first shape rotated by 90 degrees anticlockwise.

The problem was to find out the unique shapes and a rather more easy part would be how do you store the individual objects. I gave them a solution where each object will be stored as binary string where the corresponding 0's and 1's are being the representation of number of 0's and 1's in all the four directions so for example the object in the following matrix:
0 1 1 1 0
0 0 1 0 0
can be encoded as follows:
Consider the conventions as left->right->top->bottom for counting the adjacent 1s for a position, so the encoded string becomes:
0101#1101#1000#0010
and similarly we can represent other objects by using the following format and then sorting the adjacent substrings separated by #.

We can uniquely represent different objects by using the following conventions, and then rotate the matrix to find out the uniqueness of the object for example the following object:
1
1 1 1will become 1 1 when rotated by 90 degrees anticlockwise and have the same
1 1

representation. This can be used to identify the unique objects in the matrix.

- shawn June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Some problems while publishing the following object:
1 1 1 is actually 1 1 1
1 1

and the representation of this object is 0100#1101#1000#0010 instead of 0101#1101#1000#0010

- shawn June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

simple flood fill with DFS
keep a counter and increment it whenever a separate dfs is called

- kevseb1993 July 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please elaborate on this? Or give me some link where this method is explained? Thanks.

- Posiedon February 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Given n*m fields of O's and X's, where O=white, X=black, for example
//
//OOOXOOO
//OOXXOXO
//OXOOOXO

//Return the number of black shapes. A black shape consists of one or
// more adjacent X's (diagonals not included).
// In the example, the answer is 3.


using namespace std;


void explore(int arr[][7],int i,int j,int m,int n)
{
    if(i < 0 || i > m-1)
    {
       return;
    }
    if(j < 0 || j > n-1)
    {
      return;
    }

    if(arr[i][j] == 0 || arr[i][j] == -1)
    {
       return;
    }

    arr[i][j] = -1;

   //Open below to include diagonal also
   /* 
   explore(arr,i-1,j-1,m,n);
   explore(arr,i+1,j+1,m,n);
   explore(arr,i-1,j+1,m,n);
   explore(arr,i+1,j-1,m,n);
   */

   explore(arr,i,j-1,m,n);
   explore(arr,i,j+1,m,n);
   explore(arr,i-1,j,m,n);
   explore(arr,i+1,j,m,n);
}

int countbBlackShapes(int arr[3][7],int m,int n)
{
   int count = 0;

   for(int i = 0; i < m; i++)
   {
      for(int j = 0; j < n; j++)
      {
         if(arr[i][j] == 1)
         {
            explore(arr,i,j,m,n);
            count++;
         }
      }
   }

    //To recovedr the data again place -1 as 1
    for(int p = 0; p < m; p++)
    {
      for(int q = 0; q < n; q++)
      {
          if(arr[p][q] == -1)
            arr[p][q] = 1;
      }
   }

   return count;
}

int main()
{
   //OOOXOOO
   //OOXXOX
   //OXOOOXO

   //X =1
   //O =0

    int M[3][7]= {
        {0,0,0,1,0,0,0},
        {0,0,1,1,0,1,0},
        {0,1,0,0,0,1,0}
    };
    cout<<"Number of Black Shapes="<<countbBlackShapes(M,3,7);
}

this is my initial appraoch i will improve it for time complexity...

- Kavita June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char[][] data = new char[3][];
   
   public void load(){
       data[0] = "OOOXOOO".toCharArray();
       data[1] = "OOXXOXO".toCharArray();
       data[2] = "OXOOOXO".toCharArray();
   }
   
    
    
    
    public void parse() {
        int count = 0;
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                if ((j + 1) < data[i].length) {
                    if (data[i][j] == 'X') {
                        if (data[i][j] == data[i][j + 1]) {
                            // Adjacent columns are equal X
                            ++count;
                        }
                        if ((i - 1) >= 0) {
                            // Check top
                            if (data[i - 1][j] == data[i][j]) {
                                ++count;
                            }
                        }
                        if ((i + 1) < data.length) {
                            // Check bottom
                            if (data[i + 1][j] == data[i][j]) {
                                ++count;
                            }
                        }
                    }
                }
            }
        }
        System.out.println("Count: " + count);
    }

- Sathish June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

One of either // Check top or // Check bottom code block must be removed to get expected count.

- Sathish June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

check both up and down will get double count.

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Satish Will u try a test case on your code.....
i not know java so i cannot check

int M[5][9] = {
{0,1,1,0,1,0,1,0,0},
{1,1,0,0,1,1,1,0,0},
{0,1,1,1,1,0,0,0,0},
{1,1,0,0,0,0,0,0,0},
{0,1,1,1,0,0,0,0,0}
};

No of black shapes here is 1

1 used as black shape i mean x and 0 used for white shape

- Kavita June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

g

- g June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Without recursion just count the adjacent elements first row-wise and then column-wise. This can be done without recursion using the loops as:

#include <stdio.h>
#include <conio.h>

int countRows(char a[][7],int n,int m)
{
	int j=0,count=0,flag=0;
	for(int i=0;i<n;)
	{
		if(a[i][j]=='X'&&a[i][j+1]=='X'&&j<m-1)
		{	
			j=j+2;
			flag=1;
		}
		if(a[i][j]=='X'&&a[i][j+1]!='X'&&j<m-1)
		{
			j=j+2;
		}	
		if(a[i][j]=='X'&&j==m-1)
			j++;	
		if(a[i][j]=='O'&&j<m)
		{
			j++;
			if(flag==1)
			{
				count=count+1;
			}
			flag=0;	
		}
		if(j==m)
		{
			i++;
			j=0;
		}
	}
	return count;
}
int countCols(char a[][7],int n,int m)
{
	int i=0,count=0,flag=0;
	for(int j=0;j<m;)
	{
		if(a[i][j]=='X'&&a[i+1][j]=='X'&&i<n-1)
		{	
			i=i+2;
			flag=1;
		}
		if(a[i][j]=='X'&&a[i+1][j]!='X'&&i<n-1)
			i=i+2;
		if(a[i][j]=='X'&&i==n-1)
			i++;	
		if(a[i][j]=='O'&&i<n)
		{
			i++;
			if(flag==1)
			{
				count=count+1;
			}	
			flag=0;	
		}
		if(i==n)
		{
			j++;
			i=0;
		}	
	}
	return count;
}


int main()
{
	char a[][7]={{'O','O','O','X','O','O','O'},{'O','O','X','X','O','X','O'},
					{'O','X','O','O','O','X','O'}};
	int n=sizeof(a)/sizeof(a[0]);
	int m=sizeof(a[0])/sizeof(a[0][0]),flag=0;
	printf("%d",countRows(a,n,m)+countCols(a,n,m));
}

- vgeek June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it's wrong

- Anonymous June 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please can you elaborate that because i have checked it and it is working for all the cases i have checked for. Please provide a case for which it is wrong

- vgeek June 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{'O','O','O','X','O','O','O'} it will return 0. not mentioning it fails on boundary checking

- Anonymous June 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The black shape consists of one or more adjacent Xs and it checks the boundary cases

- vgeek June 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your code will fail in the case when the input is like

xxxxxxxxxxxxxx

because when u r checking

if(j==m)
		{
			i++;
			j=0;
		}

u r not updating the count if the last element of the row or all the rows in the element are x....

- Tanay November 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CountXGroups {

/**
* O , O , X , O , X
* O , X , O , X , O
* O , O , O , X , O
* O , X , X , X , O
*/

char[][] grid = { {'O' , 'O' , 'X' , 'O' , 'O'} ,
{'O' , 'X' , 'O' , 'X' , 'O'} ,
{'O' , 'O' , 'O' , 'X' , 'O'} ,
{'X' , 'O' , 'X' , 'O' , 'X'} };

public static void main(String[] args) {
CountXGroups countXGroups = new CountXGroups();
countXGroups.countXGroups();
}

private void countXGroups() {
int counter = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
char value = grid[i][j];
if (value == 'X') {
if (!check(grid, i, j)) {
counter++;
}
update(grid, i, j);
}
}
}
System.out.println(counter);
}

private boolean check(char[][] grid, int i, int j) {
return checkLeft(grid, i, j) || checkUp(grid, i, j) ;
}

private void update(char[][] grid, int i, int j) {
grid[i][j] = 'Y';

if (j > 0) {
char left = grid[i][j - 1];
if (left == 'X') {
update(grid, i, j - 1);
}
}

if (j + 1 < grid[i].length) {
char right = grid[i][j + 1];
if (right == 'X') {
update(grid, i, j + 1);
}
}

if (i + 1 < grid.length) {
char down = grid[i + 1][j];
if (down == 'X') {
update(grid, i + 1, j);
}
}
}

private boolean checkUp(char[][] grid, int i, int j) {
if (i > 0) {
if (grid[i - 1][j] == 'Y') {
return true;
}
}
return false;
}

private boolean checkLeft(char[][] grid, int i, int j) {
if (j > 0) {
if (grid[i][j - 1] == 'Y') {
return true;
}
}
return false;
}

}

- newbie June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CountXGroups {

	/**
	 * O , O , X , O , X
	 * O , X , O , X , O
	 * O , O , O , X , O
	 * O , X , X , X , O
	 */
	
	char[][] grid = { {'O' , 'O' , 'X' , 'O' , 'O'} ,
				   	  {'O' , 'X' , 'O' , 'X' , 'O'} ,
				      {'O' , 'O' , 'O' , 'X' , 'O'} ,
				      {'X' , 'O' , 'X' , 'O' , 'X'} }; 
	
	public static void main(String[] args) {
		CountXGroups countXGroups = new CountXGroups();
		countXGroups.countXGroups();
	}

	private void countXGroups() {
		int counter = 0;
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				char value = grid[i][j];
				if (value == 'X') {
					if (!check(grid, i, j)) {
						counter++;
					}
					update(grid, i, j);
				}
			}
		}
		System.out.println(counter);
	}
	
	private boolean check(char[][] grid, int i, int j) {
		return checkLeft(grid, i, j) || checkUp(grid, i, j) ;
	}
	
	private void update(char[][] grid, int i, int j) {
		grid[i][j] = 'Y';
		
		if (j > 0) {
			char left = grid[i][j - 1];
			if (left == 'X') {
				update(grid, i, j - 1);
			}
		}
		
		if (j + 1 < grid[i].length) {
			char right = grid[i][j + 1];
			if (right == 'X') {
				update(grid, i, j + 1);
			}
		}
		
		if (i + 1 < grid.length) {
			char down = grid[i + 1][j];
			if (down == 'X') {
				update(grid, i + 1, j);
			}
		}
	}

	private boolean checkUp(char[][] grid, int i, int j) {
		if (i > 0) {
			if (grid[i - 1][j] == 'Y') {
				return true;
			}
		}
		return false;
	}

	private boolean checkLeft(char[][] grid, int i, int j) {
		if (j > 0) {
			if (grid[i][j - 1] == 'Y') {
				return true;
			}
		}
		return false;
	}

}

- newbie June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 represents 'X'
0 represents 'O'

public class FindShapes {

	public static int countBlackShapes(int[][] arr, int rows, int cols)
	{
		if(arr.length == 0)
			return 0;
		
		int count = 0;
		boolean ind = false;
		for(int i = 0; i < rows; i++)
		{
			for(int j = 0; j < cols - 1; j++)
			{				
				if((arr[i][j] == arr[i][j+1]) && arr[i][j] == 1)
				{
					ind = true;					
				}
				else{
					if(ind == true)
						count = count + 1;
					
					ind = false;
				}
				
				if((j == cols - 2) && ind == true)
				{
					count = count + 1;
					ind = false;
				}
				
			}
			
			
		}
		
		for(int i = 0; i < cols; i++)
		{
			for(int j = 0; j < rows - 1; j++)
			{
				if((arr[j][i] == arr[j+1][i]) && arr[j][i] == 1)
				{
					ind = true;					
				}
				else{
					if(ind == true)
						count = count + 1;
					
					ind = false;
				}
				
				if((j == rows - 2) && ind == true)
				{
					count = count + 1;
					ind = false;
				}
			}		
			
		}
		
		return count;
	}
	
	public static void main(String[] args)
	{
		int arr[][] = {
				{1, 1, 0, 1, 1},
				{1, 1, 0, 1, 1},
				{0, 0, 1, 0, 0}
		};
				
		
		System.out.println(FindShapes.countBlackShapes(arr, 3, 5));
	}
}

- Kasim June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Graphs and Strongly Connected components?

- Anonymous July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using the simple flood fill with DFS, i was able to code something up.
I found algorithm off top coder, but it just uses DFS, and i just substituted Xs for 1s, and marked a node as visited as -1, if you need to restore the graph, you could keep track of items, then just restore afterwards.

public class testJava {

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

		testJava test = new testJava();
		test.solveProblem(worldMap);
	}

	public void solveProblem(int[][] worldMap) {
		System.out.println("# of rows " + worldMap.length);
		System.out.println("# of cols " + worldMap[0].length);

		int result = 0;
		int maxResult = 0;

		for (int i = 0; i < worldMap.length; i++) {
			for (int j = 0; j < worldMap[0].length; j++) {
				if (worldMap[i][j] > 0) {
					result = doFill(worldMap, j, i);
					System.out.println("results: " + result);

					if (result > maxResult) {
						maxResult = result;
					}
				}
			}
		}

		System.out.println("max result : " + maxResult);

	}

	public int doFill(int[][] worldMap, int x, int y) {
		System.out.println("do fill called x: " + x + " y: " + y);

		if (x == 5 && y == 2)
			System.out.println("debug");

		// check x bounds
		if (x < 0 || x >= worldMap[0].length)
			return 0;

		if (y < 0 || y >= worldMap.length)
			return 0;

		if (worldMap[y][x] == 0)
			return 0;

		if (worldMap[y][x] == -1)
			return 0;

		// visited node
		worldMap[y][x] = -1;

		return 1 + doFill(worldMap, x - 1, y) + doFill(worldMap, x + 1, y)
				+ doFill(worldMap, x, y + 1) + doFill(worldMap, x, y - 1);

	}

- Farooq July 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

on my code, i returned the number of units within each shape, but each time we do a DFS , you could increment counter.
that would be in the loop before you call doFill the 1st time.

- Anonymous July 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ code using floodfill algorithm

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

// flood fill.
inline unsigned getKey(unsigned row, unsigned col, unsigned ncols){
    return row * ncols + col;
}

template <size_t T>
void fill(char mat[][T], int i, int j, unsigned nrows, unsigned ncols, const unordered_map<unsigned, unsigned> &hash,
         unordered_set<unsigned> &visited, unsigned regionId, bool diag){

    if (i <0 || i >= nrows || j<0 || j>= ncols || mat[i][j] != 'x') return;
    
    unsigned key = getKey(i,j,ncols);
    if (visited.find(key) != visited.end()) return;
    cout << "Visited:" << i<<"," <<j<<"\n";
    visited.insert(key);
    
    if(diag) fill(mat, i-1, j-1, nrows, ncols, hash, visited, regionId, diag);
    fill(mat, i-1, j, nrows, ncols, hash, visited, regionId, diag);
    if(diag) fill(mat, i-1, j+1, nrows, ncols, hash, visited, regionId, diag);
    fill(mat, i, j-1, nrows, ncols, hash, visited, regionId, diag);
    fill(mat, i, j+1, nrows, ncols, hash, visited, regionId, diag);
    if(diag) fill(mat, i+1, j-1, nrows, ncols, hash, visited, regionId, diag);
    fill(mat, i+1, j, nrows, ncols, hash, visited, regionId, diag);
    if(diag) fill(mat, i+1, j+1, nrows, ncols, hash, visited, regionId, diag);

}

template <size_t T>
unsigned getNumRegions(char mat[][T], unsigned nrows, unsigned ncols, bool diag = false){
    unsigned num = 0;
    unordered_map<unsigned, unsigned> hash;
    unordered_set<unsigned> visited;
    
    for (unsigned i=0; i<nrows; ++i){
        for (unsigned j=0; j<ncols; ++j){
            unsigned key = getKey(i,j,ncols);
            if (mat[i][j] != 'x' || (visited.find(key) != visited.end()) ) continue;
            cout << "Fill:" << i<<"," <<j<<"\n";
            fill<T>(mat, i, j, nrows, ncols, hash, visited, ++num, diag);
        }
    }
    
    return num;
}

int main() {
    char mat[4][3] = {
        {'x','o','o'},
        {'o','x','x'},
        {'x','o','o'},
        {'o','x','x'}
    };
    cout << getNumRegions<3>(mat,4,3, true) <<"\n";
    cout << getNumRegions<3>(mat,4,3) <<"\n";
    cout << "Done!\n";
    return 0;
}

- im.code.warrior July 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You loop through every cell and as you detect one black cell then you recurse on it to find the black shape holding that black cell. Of course, as you detect black shapes you make them white shapes to prevent repeating yourself.

import java.util.Scanner;

public class Main {

    /*
    * Input : Row count, Column count then
    *           the grid with 1's and 0's
    *           where 1 means black zero means 0.
    *
    * ex:
    * 2 4
    * 0 1 1 0
    * 1 0 0 1
    *
    * */

    private int n; //row count
    private int m; //column count
    private int[][] inputGrid;

    public void init(){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        /*Surround the input grid with zeros.
        * This makes checking neighbours easier.
        */

        inputGrid = new int[n+2][m+2];

        for(int j = 0 ; j < m+2; j++){
            inputGrid[0][j] = 0;
            inputGrid[n+1][j] = 0;
        }

        for(int i = 1 ; i < n+1; i++){
            inputGrid[i][0] = 0;
            inputGrid[i][m+1] = 0;
            for(int j = 1 ; j < m + 1 ; j ++ ){
                inputGrid[i][j] = sc.nextInt();
            }
        }
    }

    public void detectBlackShape(int i, int j){
        inputGrid[i][j] = 0;
        if(inputGrid[i][j-1] == 1) detectBlackShape(i, j-1);
        if(inputGrid[i-1][j] == 1) detectBlackShape(i-1,j);
        if(inputGrid[i+1][j] == 1) detectBlackShape(i+1, j);
        if(inputGrid[i][j+1] == 1) detectBlackShape(i, j+1);
    }

    public int process(){
        int count = 0;
        for(int i = 1 ; i < n+1 ; i++){
            for(int j = 1 ; j < m+1 ; j++){
                if(inputGrid[i][j] == 1){
                    count++;
                    detectBlackShape(i,j);
                }
            }
        }
        return count;
    }

    public void print(int result){
        System.out.println(result);

        for(int i = 1 ; i < n+1;i++){
            for(int j = 1 ; j < m+1;j++){
                System.out.print(inputGrid[i][j] + " ");
            }
            System.out.println();
        }
    }

    public void run(){
        init();
        int result = process();
//        print(result);
        System.out.println(result);
    }

    public static void main(String[] args) {
        new Main().run();
    }
}

- Elshad Mustafayev August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simpler solution would be to loop over the cells and modifying the result according to the 2*2 shape that the cell makes with its top left diagonal :

O
OX -> +1

  X      O   XX
OX ; XX ; XX  -> nothing

OX
XX -> -1

This is a O(n*m) complexity.

- Navrug October 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

public class CountTheShapes {

public static void main(String[] args) {

char[][] matrix = new char[][]
{"OOOXOOO".toCharArray(),
"OOXXOXO".toCharArray(),
"OXOOOXO".toCharArray()};

boolean visited[][] = new boolean[matrix.length][matrix[0].length];
int count = 0;
for(int row=0;row<matrix.length;row++){
for(int col=0;col<matrix[row].length;col++){
if(!visited[row][col] && matrix[row][col] == 'X'){
searchShape(matrix,row,col,visited);
count++;
}
}
}

System.out.println(count);
}

private static void searchShape(char[][] matrix, int row, int col, boolean[][] visited) {

if(row<0 || row >= matrix.length || col<0 || col >=matrix[row].length){
return;
}

if(visited[row][col] || matrix[row][col] == 'O'){
return;
}
visited[row][col] = true;
searchShape(matrix, row+1, col, visited);
searchShape(matrix, row-1, col, visited);
searchShape(matrix, row, col+1, visited);
searchShape(matrix, row, col-1, visited);
}
}

and

- fatih January 20, 2017 | 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