Cisco Systems Interview Question Software Engineer / Developers
Problem Statement - Counting Cells in a Sector
Consider a two-dimensional grid of cells, each of which may be empty or filled. The filled cells that are connected form a sector. Two cells are said to be connected if they are adjacent to each other horizontally, vertically or diagonally. There may be several sectors on the grid. Your job is to find the largest sector (in terms of number of cells) on the grid.
The following figure illustrates a grid with 3 sectors (the largest contains 5 cells).
Problem
Write a program that determines the size of the largest sector for a given grid.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The grid is given as a set of string, each composed of 0s and 1s. The 1 indicates that the cell is filled and 0 indicates an empty cell. The strings should be converted into the grid format. The largest grid that should be considered is a 25x25 grid.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output is the size of the largest sector found on the grid.
Sample Input
2
11000
01100
00101
10001
01011
1011
1010
Sample Output
5
3
Attached (in.txt) is the input file, please return the send the output file for the corresponding input.
PLEASE HELP ME OUT
Hi given is my task plz can any give me source code to fillup my task.
Consider a two-dimensional grid of cells, each of which may be empty or filled. The filled cells that are connected form a sector. Two cells are said to be connected if they are adjacent to each other horizontally, vertically or diagonally. There may be several sectors on the grid. Your job is to find the largest sector (in terms of number of cells) on the grid.
The following figure illustrates a grid with 3 sectors (the largest contains 5 cells).
Problem
Write a program that determines the size of the largest sector for a given grid.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The grid is given as a set of string, each composed of 0s and 1s. The 1 indicates that the cell is filled and 0 indicates an empty cell. The strings should be converted into the grid format. The largest grid that should be considered is a 25x25 grid.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output is the size of the largest sector found on the grid.
Sample Input
2
11000
01100
00101
10001
01011
1011
1010
Sample Output
5
3
Attached (in.txt) is the input file, please return the send the output file for the corresponding input.
#include<stdio.h>
int grid[25][25];
int rows=0, cols=0;
static int maxCount=0;
#define MARKED -1;
// counting matrix function
int countMatrix(int row, int col){
int sizeSector=0;
if(row<0 || row>=rows)
return 0;
if(col<0 || col>=cols)
return 0;
if(grid[row][col]!=1)
return 0;
grid[row][col]=MARKED;
sizeSector=1+ countMatrix(row-1, col-1) + countMatrix(row-1, col) + countMatrix(row-1, col+1)+ countMatrix(row, col-1)+ countMatrix(row, col+1) + countMatrix(row+1, col-1)+ countMatrix(row+1, col+1)+ countMatrix(row+1, col+1);
return sizeSector;
}
// make it unmarked so the next time a fresh will happen and -1 will be remove from array
void unmarkGrid(void){
int i,j;
for(i=0;i<rows;i++){
for(j=0;j<cols;j++){
if(grid[i][j]== -1)
grid[i][j]=1;
}
}
}
int mainloop(){
int i,j,count=0,tmp=0;
for(i=0;i<rows; i++){
for(j=0;j<cols;j++){
count=countMatrix(i,j);
if(count>maxCount){
maxCount=count;
unmarkGrid();
}
}
}
tmp=maxCount;
//printf("count : %d",maxCount);
maxCount=0;
return tmp;
}
main(){
int testsize=0,c,x=0,y=0;
int blank=0,count=0,value,output;
char in[4],im[2];
FILE *fin,*fout;
fin=fopen("input.txt","r"); //open two files, one in read mode other in write mode
fout=fopen("out.txt","w");
testsize=atoi(fgets(in,4,fin));
//printf("total test cases : %d",testsize);
fseek(fin,5L,SEEK_SET);// move to first value in input.txt
while ((c=fgetc(fin))!= EOF){
if(c ==48){
grid[x][y]=0;
y++; //increment cols
blank=0;
}
else if(c== 49){
grid[x][y]=1;
y++;//increment cols
blank=0;
}
else if(c == '\n' && blank ==0){ //end of first row
cols=y;y=0;x++;rows++; //we got cols & increment row
blank=1;}
else if(c== '\n' && blank==1){ //two balnks--> end of reading2d array
output=mainloop(); //returns count=cells in a sector
rows=cols=x=y=blank=0; //set to zero --> for next iteration
//putw(output,fout);
fprintf(fout,"%d\n",output);// print to output file
}
}
fclose(fin);fclose(fout);
}
sample input:
200//test cases
01111001100011010101001
11110100100001000101100
01101001100000000100010
10111010010000001111011
10010101010110100010110
10110111100011110001001
10000010001100111001100
11001000111111010110110
00000011010110001100001
00000100101011001001110
00010110001001100111101
11011110011010111100001
01010000110100111010110
10111101000110010000011
10101010000001001001001
11010000110010011010011
0010000111001001
1011110000000011
1001101010010011
0000010000010110
1111111101110000
0100110011101001
1001100101001100
1000110010011111
0000110010100111
1111110001010100
1110000011010100
00011110010
00000101111
11001000001
10111110001
00000111100
01110101010
00110101110
10010011110
10001110100
10011101010
10010100110
11011100010
01100010110
11000100100
01010001010
01001100000
11011101101
00011111100
00000110110
11000000011
01011100011011011010100
01001001010010111000010
11000110110010110101010
00110110001101010101111
01101110111101111010000
11101011011000101100110
11101000010000100110011
00101111011101000011100
01001111001110100000100
10011000000110000110110
01010111100010110111010
11100010011100110011100
11010011111111111000000
10100101010101011101011
10101000111010110101110
00110010110100100001001
10100000110110111100001
011010001010
110101101101
111011010011
011110010100
000100010011
101010010010
000000000011
000000111101
100000000011
100110010100
101100011001
01011
10100
10000
10110
11111
11000
00111
10101
11011
10000
01011
01011
10101
10000
10000
11111
11100011110111
00001100010111
10100110011000
11111101101111
11001001111110
01001011111011
00010010000100
11001001110011
01011111111011
00100111000000
00001100110100
01010100100110
10110000010100
10001000111010
01110111100000
01100001101100
01110100010111
00010010011110
00000010000111
11100111010111
01101111110001
01001010100100
11000110111100
01111100010000
0010000
0010010
1011110
0100000
0010010
1011011
111101
111110
111111
010011
110101
00011111100010111011110
01000000101011011011110
01011111011001101110110
10000100001010110110001
10110101111101100011100
10111011001101110010001
01011101110111011100111
11011001110001011001101
01111011000101000111000
01000000101111001011100
01101001101100000110100
00001011000010100100011
10110001010111000111001
0011111
1000000
0010101
0010010
0010111
1110110
0011100
0101111
1010000
0011100
0001000
0001011
...................................................upto 200 test cases
int countMatrix(int row, int col){
int sizeSector=0;
if(row<0 || row>=rows)
return 0;
if(col<0 || col>=cols)
return 0;
if(grid[row][col]!=1)
return 0;
grid[row][col]=MARKED;
sizeSector=1+ countMatrix(row-1, col-1) + countMatrix(row-1, col) + countMatrix(row-1, col+1)+ countMatrix(row, col-1)+ countMatrix(row, col+1) + countMatrix(row+1, col-1)+ countMatrix(row+1, col)+ countMatrix(row+1, col+1);
return sizeSector;
}
This is direct lift from codechef site.
- Erik September 23, 2009The trick behind this is to calculate matrix M = (intial) xor (final).
Transform this to matrix with all zeroes.