Solutions - Part I

CODEFINGER was the On-Spot-Programming event and Casino RoYahoo! was the Yahoo Internship event. Both consisted of two rounds - a preliminary written round followed by the final round which required the finalists to program directly on a system provided to them.

Here I shall post the solutions to only a few questions. One can download the question papers here. Feel free to contact me for the answers to the other questions

--------------------------------------------------------------------------------------------------------------

Q. What is the output?

int main()
{
..... i=3;
.....( "%d\n", sizeof(i==3? 5 : 6.8) );
.....return 0;
}

Ans. sizeof is a unary operator which returns the number of bytes its operand occupies. It is a compile-time operator because at run-time, type identification cannot be done in C. Since it is compile-time, it is to be noted that the expression is not evaluated (It is for the same reason that i=5 ; sizeof(++i) ; print i would output 5 itself, i.e. the ++i is not executed). Thus first of all, int i=3 is inconsequential.
The result of the expression i==3? 5 : 6.8 should be large enough to hold either an integer or a double(default for real values). Thus the output of the above code snippet is 8.

--------------------------------------------------------------------------------------------------------------


Q. Why can we have Virtual Destructors but not Virtual Constructors?

Ans. Virtual mechanism acts on complete objects. If something is virtual, it means it can be over-ridden by a sub-class. When a constructor is in the process of execution, the object is not complete. Thus it makes no sense to have virtual constructors.
But we can have virtual destructors because the fact that a destructor is being executed means the object has been constructed completely.

--------------------------------------------------------------------------------------------------------------

Q. The following function void insert_right(int value , int element) aims at inserting value to the right of element in a linked list whose header node is first. The structure definition of the linked list is as follows:-
struct node {int info; struct node *next};
The following code gives a run-time error for certain cases. Point out the cases and make the correction so that it gives correct output for all cases.
void insert_right( int value, int element )
{
.....struct node* cur=first, *temp;
.....while( cur->info != element && cur != NULL)
..........cur = cur->next;
.....if(cur==NULL)
..........printf( “Element not found.\n” );
.....else
.....{
..........temp = get_new_node(); //returns a pointer to struct node
..........temp->info = value;
..........temp->next = cur->next; cur->next = temp;
.....}
.....return;
}

Ans. The correction is cur->info != element && cur != NULL must be changed to cur != NULL && cur->info != element. The reason is easy to make out. When the value that is being searched for is not present in the list, we reach the end of the list. At that point cur = NULL. So cur->info results in access violation, resulting in the run-time error.

--------------------------------------------------------------------------------------------------------------

Q. Write a one-liner to find the value of n mod 2^s without using the % operator. No looping allowed either.

Ans. The value of n mod 10 is always the last digit of the number. This can be proved pretty easily-> if we have a number abcd where a,b,c,d are the individual digits, it can be expressed as abc*10 + d. Thus it is obvious that the remainder when divided by 10 would be the last digit itself. Similarly the value of the remainder when a decimal number is divided by 100 are the last two digits of the number.
We can extend this logic to powers of 2 as well. The value of a number mod 2 is the last bit in the binary representation of the number. Similarly the value of a number mod 4 is the last two bits in the binary representation of the number.
Illustration:-
If we have a number 10100100101, the number mod 16 is basically the last four bits of the number,i.e. 101 which is 5. The reason for this is pretty simple. The above number can be actually expressed as (1010010)*16 + (0101). Thus is it clear that the remainder is 0101.

Hence to find the remainder of a number divided by 2^s, all we have to do is mask all but the first s bits from the right side. Therefore the remainder is given
by the expression rem = n[bitwise and]((1[shift left]s)-1).

--------------------------------------------------------------------------------------------------------------

Q. The expression i = (i + 1)%10 generates values like this:
...1->2->3->4->5->6->7->8->9->0->1->2->3->4->5->6->7->8->9->0->1...
Write an expression which will generate values like this:
...8->7->6->5->4->3->2->1->10->9->8->7->6->5->4->3->2->1->10->9->8...

Ans. I am not sure whether the question statement is very clear. Basically if I begin with say i=5 and successively perform i=(i+1)%10, then the sequence of values generated are 6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,.... Basically, i gets incremented till 9 and then comes back to 0. Now I want a statement that would generate values in the order 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10...

First of all, let us see how one can generate the sequence 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9...(A)
At first thought, i=(i-1)%10 is what comes to mind. This works for all instances other than i=0. When i=0, the next value should be 9. So we need to handle the case where (i-1) goes negative. Now we know (a+b)%b = a%b. Therefore (i-1)%10 = (i-1+10)%10. i=(i+9)%10 thus generates a sequence (A). The expression can also be though of in this way going back one circularly is equivalent to going ahead 9 circularly.

Now the sequence asked for is 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8...(B) This sequence is just sequence (A)+1. Thus the first idea here is that i=(i+9)%10 can itself be used. Now, the value of i in sequence (B) is the value of i in sequence (A)+1. Therefore we have:-
ia=(ia+9)%10
We want the expression for ib where ib is ia-1
So, ib-1=(ib-1+9)%10
ib-1=(ib+8)%10
ib=(ib+8)%10+1
Thus the expression i=(i+8)%10+1 will generate sequence (B). Pardon me for the unclear explanation. But this is the best I could do.

--------------------------------------------------------------------------------------------------------------

Q. Change one character in the following code to get the output as 20 x's.
int i,n=20;
for(i=0; i [less_than] n; --i)
....printf("x);

Ans. The above question is a well known question. The answer is
int i,n=20;
for(i=0; i [less_than] n; --n)
....printf("x);

(or)

int i,n=20;
for(i=0; i + n; --i)
....printf("x);
Now, this question was asked just for the heck of it. Coming up next is a bouncer. Try it!!!

--------------------------------------------------------------------------------------------------------------

Q. Add one character to the following code to get the output as 21 x's.
int i,n=20;
for(i=0 ; i [less_than] n ; --i)
....printf("x");

Ans. I happen to recall that only one team got this one right. The answer to it is...

int i,n=20;
for(i=0 ; ~i [less_than] n; --i)
....printf("x")

You are supposed to think like this. For the previous question, if we had the for condition as -i[less_than]n, then the output would have been 20 x's. If the condition had been -i[less_than](n+1), then the output would have been 21 x's. Similarly if the condition was (-i-1)[less_than]n, the output would have been 21 x's. -i is 2's complement of i. -i-1 would be i's 1 complement. Thus, the solution is ~i[less_than]n.

--------------------------------------------------------------------------------------------------------------

There is more coming up...
Abhiram Natarajan