Directi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
/* Very Bad-Brute force*/
/* Desert represented as 0 and forest as 1 */
#define COLUMN 8
#define ROW 6
#define K 2
void matrix(int (*a)[8])
{
int i, j;
int flag;
int count = 0;
while(count != K) {
for(i=0;i<ROW;i++) {
for(j=0;j<COLUMN;j++) {
if(a[i][j] == 0) {
if(i+1 < ROW) {
a[i+1][j] = -1;
}
if(j+1 < COLUMN) {
a[i][j+1] = -1;
}
if(j-1 >= 0) {
a[i][j-1] = -1;
}
if(i+1 < ROW && j+1 < COLUMN) {
a[i+1][j+1] = -1;
}
if(i-1 >= 0) {
a[i-1][j] = -1;
}
if(i-1 >= 0 && j+1 < COLUMN) {
a[i-1][j+1] = -1;
}
if(i+1 < ROW && j-1 >= 0) {
a[i+1][j-1] = -1;
}
if(i-1 >= 0 && j-1 >= 0) {
a[i-1][j-1] = -1;
}
}
}
}
for(i=0;i<ROW;i++)
for(j=0;j<COLUMN;j++) {
if(a[i][j] == -1)
a[i][j] = 0;
}
count++;
}
}
int main()
{
int i, j;
int counter;
int array[ROW][COLUMN] = {
1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 0,
};
matrix(array);
/* calculate how many FOREST left out*/
for(counter=0,i=0;i<ROW;i++)
for(j=0;j<COLUMN;j++) {
if(array[i][j] == 1) {
printf("%d %d,", i, j);
counter++;
}
}
printf("\n");
printf("no of forest left out after de-forestation %d\n", counter);
for(i=0;i<ROW;i++) {
for(j=0;j<COLUMN;j++) {
printf("%d ,", array[i][j]);
}
printf("\n");
}
return 0;
}
declare the given matrix as static.
boolean isAdjacentToDesert( int x, int y){
if(element(x,y) is adjacent to desert){
return true;
}
else
return false;
}
public String updateDesert(){
for( iterate through rows){
for ( iterate through coloumns){
check if the element ( rowNumber, coloumnNumber) is desert or not.
if ( ! desert)
{
isAdjacentToDesert(rowNumber, coloumnNumber);
if(adjacent)
change the status of the element to '2'.
}
}} // end of for loops.
Now change the status '2' to deserts ( '1' ) .
}
use a static array of the matrix
scan though the matrix once to identify all the desserts. Push each dessert into a primary stack
initialize your k.
for each year pop all the values from your primary stack
for each popped value push all the adjacent forests into a secondary stack and make
those forests as desserts
now your secondary stack becomes your primary
after the k years iterate through your matrix to see if any forests are left and them into a list.
return the list
Let the matrix is of order MxN.
void func(int x,int y)
{
if(((x>0 || x<M) && (Y>0 || Y<N)))
if(arr[x][y]==1 && arr[x-1][y]==0 && arr[x+1][y]==0 & & arr[x][y+1]==0 &&arr[x][y-1]==0))
{
arr[x-1][y]==1;
arr[x+1][y]==1;
arr[x][y+1]==1;
arr[x][y-1]==1;
}
func(x-1,y);
func(x+1,y);
func(x,y+1);
func(x,y-1);
}
else
return;
Scan the matrix and store the cell positions whose values are 0 in a separate array.
- DashDash December 28, 2012Now every year scan the array and for every element in the array check the adjacent values and if it is all 1 then remove the element from the array and change the matrix.
after k yrs the left elements in the array are the forests left