GLaDOS is feeling bored, so sh

National Instruments Interview Question for Software Developers

0

of 0 votes

2
Answers
GLaDOS is feeling bored, so she decided to come up with a board game. The game is as follows. There is
board of dimension n x n (2 <= n <= 10). Each position in this board is either a 0 or a power of 2, between 2
and 2048. Once the board is set up, there are only two moves allowed - move all left or move all right.
The way move all left works is as follows:
For every row on the board, starting from the rightmost position each element is moved to its left. An
element with a zero value does not move. An element with non-zero value can move to its left if the value of
the element to its left is a 0 or has the same value as the current element.
In case, the element to the left is 0 then the element and 0 swap positions i.e., 4 0 0 4 would become 4 0 4 0
In case, the element to the left has the same value as the current element then the left element combines
with its right element and creates an element with double the value in place of the right element and leaves
a 0 in its current place. For e.g., 2 2 would become 4 0 or 2 2 2 2 would become 4 0 4 0.
The combining operation can cause a cascading operation i.e., if the new element created has the same
value as the element to its left, it can combine again.
For e.g., if a row had 8 4 2 2, move left would combine 2 and 2 to form 4 leading to 8 4 4 0. Now, it is
possible to combine further as the element to the left of 4 has the same value, thus after the second
combine, the row would be 8 8 0 0. And again 8 and 8 would form a 16. Thus the final values in the row
would be 16 0 0 0.
But if the row was 8 4 2 0 2, then moving left would result in 8 4 2 2 0. The cascading operation is allowed
only after a combination operation, There would no cascading operation if the element is swapped with 0.
Similar rules apply for move all right, wherein for every row elements starting from the leftmost position
move to their right.
You can either choose move all left or move all right operation but not both. Now given a state of the board,
you have determine what will be the maximum value on the board after either move all left or move all right.
Example
3
2 2 0
2 2 4
2 0 2
Move all left would result in:
4 0 0
4 0 4
2 2 0
The maximum value on the board after this move is 4.
Move all right would result in:
0 4 0
0 0 8
0 2 2
In the first row, 2 and 2 combines to form 4. In the second row, left most 2 combines with 2 to form 4. As the
element to its right has a value 4, combination operation cascades to form 8.
The maximum value on the board after this move is 8.
Now of the two operations, the higher of the two maximum values is 8. Thus the expected output is 8.
Input
3
2 2 0
2 2 4
2 0 2
Output
8
Input
3
0 0 4
0 2 2
0 4 8
Output
8
Time limit per test case:
1 second(s)
- glory for dreams April 24, 2015 in India | Report Duplicate | Flag | PURGE
National Instruments Software Developer C C++

Email me when people comment.

An error occurred in subscribing you.

Country: India
Interview Type: Written Test

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

#include<stdio.h>

int check_pow(int n){

int k=2;
if(n<=2048 && n>=2){
while(k<=n){
if(k==n) // validate the value for power of two
return 1;

k=k*2;
}
return 0;

}
else if(n==0)
return 1;

else
return 0;
}
main()
{
int a[10][10];
int b[10][10];
int n;
int r=0,c=0;
int max1=0,max2=0;

int temp=0;

while(1){
scanf("%d",&temp);
if(temp<2 || temp>10)
{
printf("~~~~~ please enter the valide range \n ~~~~~(VALUE SHOULD BE IN BETWEEN 2 AND 10 INCLUDEING BOTH 2 AND 10)\n");
}
else
{
n=temp;
break;
}

}

printf(" enter data to the grid \n");
for(c=0;c<n;++c){

for(r=0;r<n;){

scanf("%d",&temp);
if(check_pow(temp))
{
a[c][r]=temp;
b[c][r]=temp;
++r;
}
else
{
printf(">>>>>%d is not a valide number (NOT A POWER OF TWO) \n>>>>>please enter the valide value\n",temp);
}
}

}

//for left move

for(c=0;c<n;++c){
for(r=n-1;r>0;r=r-1){
if(a[c][r-1] == 0 )
{

a[c][r-1]=a[c][r];
a[c][r]=0;
r=r-1;

}
else if(a[c][r-1] == a[c][r])
{

a[c][r-1]=a[c][r]+a[c][r-1];
a[c][r]=0;
if( a[c][r-2]==0)
r=r-1;
// printf("%d",a[c][r-1]);

}

}
}

// for right move

for(c=0;c<n;++c){
for(r=0;r<n-1;r=r+1){
if(b[c][r+1] == 0 )
{

b[c][r+1]=b[c][r];
b[c][r]=0;
r=r+1;

}
else if(b[c][r+1] == b[c][r])
{

b[c][r+1]=b[c][r]+b[c][r+1];
b[c][r]=0;
if( b[c][r+2]==0)
r=r+1;
// printf("%d",a[c][r-1]);

}

}
}

/* for(c=0;c<n;++c){
for(r=n-1;r>0;r=r-1){

}
}
*/

printf(" *************** LEFT MOVE ************************* \n");

for(c=0;c<n;++c){

for(r=0;r<n;++r){
if(a[c][r]>max1)
max1=a[c][r];
printf("%d\t",a[c][r]);
}
printf("\n");

}
printf(" **************** RIGHT LEFT ************************ \n");
for(c=0;c<n;++c){

for(r=0;r<n;++r){
if(b[c][r]>max2)
max2=b[c][r];
printf("%d\t",b[c][r]);
}
printf("\n");

}
if(max1>max2)
printf("MAX VALUE = %d",max1);
else
printf("MAX VALUE = %d",max2);

}

- Mithun Kumar Soni April 26, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

- mkumarsoni75 April 26, 2015 | Flag Reply

CareerCup

National Instruments Interview Question for Software Developers

Books

Videos

Resume Review

Mock Interviews