Wednesday, March 28, 2007

C, Algorithm questions

Q) Given only putchar(no sprintf, itoa, etc) write a routine that prints out an unsigned long in decimal.
Sol:-
void putlong( unsigned int x)
{
unsigned int y = 0;
y = x % 10;
if( x > 9 )
putlong(x/10);
putchar(y+'0');
}

Q) Give a one line C expression to test whether a number is a power of 2
Sol:-
if ( x & (x-1) == 0 )
printf("x is power 2");
else
printf("x is not a power of 2");

PS: check if x is greater than 0 before performing this test.

Q) Given a sequence of characters. How will you convert the lower case characters to upper case characters.
Sol:-
#include<stdio.h>
#include<string.h>

int main()
{
char s[] = "This is string";
int i = 0;
while(s[i])
{
if( s[i] >= 'a' && s[i] <= 'z' )
printf("%c", s[i] + 'A' - 'a' );
else
printf("%c",s[i]);
i++;
}
}


Q) You are given a datatype, say X in C. The requirement is to get the size of the datatype, without declaring a variable or a pointer variable of that type, And, of course without using sizeof operator !
Sol:-
#define size(type) ( (int)((type *)0+1) - (int)((type *)0)) 


Q)Given an array of numbers, except for one number all the others, occur twice. Give an algorithm to find that number which occurs only once in the array.
Sol:-
XOR all the elements in the array, finally the single element will remain.

Q)Give a very good method to count the number of ones in a "n" (e.g. 32) bit number
Sol:-
int bitcount (unsigned int n)  
{
int count=0 ;
while (n)
{
count++ ;
n &= (n - 1) ;
}
return count ;
}


Q)Reversing a singly linked list
Sol:-
NonRecursive
Node *Reverse (Node *p)
{
Node *pr = NULL;
while (p != NULL)
{
Node *tmp = p->next;
p->next = pr;
pr = p;
p = tmp;
}
return pr;
}

Recursive
Node *reverseList(Node *current, Node *parent) 
{
Node *revHead;
if(current == null)
revHead = parent;
else
{
revHead = reverseList(current->next,current);
current->next = parent;
}
return revHead;
}
Initial method call should be : head = reverseList(head,NULL)



Q)Fast way to multiply a number with 7
Sol:-
(x << 3) - x


Q)Deleting a node in a doubly linked list.
Sol:-
List_Delete(L,x) 
{
if( x->prev != NULL )
x->prev->next = x->next;
else
L->head = x->next;

if( next->x != NULL )
x->next->prev = x->prev;
}

If we ignore the boundary conditions at the head & end of the list the above func. simplifies to:
x->prev->next = x->next
x->next->prev = x->prev


Q)Finding the depth of a binary tree
Sol:-
int Depth (struct NODE *Node, int Level)
{
if (Node != NULL)
{
if (Level > depth)
depth = Level;
Depth (Node->Left_Child, Level + 1);
Depth (Node->Right_Child, Level + 1);
}
return (depth);
}


Q) Write a C program to print itself
Sol:-
#include
#include
int main( int argc, char *argv[] )
{
FILE *fp;
char filename[10]={'\0'};
char line[80];

strcpy(filename,argv[0]+2);
strcat(filename,".c");

fp = fopen(filename,"r");

while( fgets(line,80,fp) )
printf("%s",line);

fclose(fp);
return 0;
}

I'm assuming the program is compiled & run as follows:
$gcc -o selfprint selfprint.c
$./selfprint

Q) Find end of nth node from end of singly linked list
Sol:-
for( i = 1; i < n ; i++ ) 
n1 = n1->next;
while(n1)
{ n2 = n2->next;
n1 = n1->next;
} // at the end n2 points to nth node from last

I just posted the logic above, care should be taken and check for NULL should be added appropriately.

Q) You are given a circular single linked list of sufficiently many number of nodes(say more than 1 crore). You need to delete a node say P and you are given a pointer to P in the circular single list. Suggest the most efficient methodology of deleting the node P from the circular single linked list without rounding about the circular single linked list.
Sol:- Copy the data of P->next to P, and delete P->next.

Q) Write a C program which when compiled and run, prints out a message indicating whether the compiler that it is compiled with, allows /* */ comments to nest.
Sol:- you can have an integer variable nest:
int nest = /*/*/0*/**/1;
if it supports nested comments then the answer is 1 else answer is 0

Q)
int main()
{
int i, n = 20;
for (i = 0; i < n; i--)
printf("*");
return 0;
}
Change/add only one character and print '*' exactly 20 times.

Sol:-
1) change n to -n in for condition
2) replace i-- with n-- OR
3) replace i < n with i + n

Q) Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.
Sol:-
The basic idea is to draw one quadrant and replicate it to other four quadrants. Assuming the center is given as (x,y) and radius as r units, then start X from (x+r) down to (x) and start Y from y up to (y+r). In the iteration, keep comparing is the equation is satisfied or not within an error of one unit for x and y. If not then re-adjust X and Y.

Q) Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.
Sol:-
The strategy 2 phase, first phase is to reverse the entire string, in second phase reverse individual words in the string obtained from first phase.
Ex:-
1) This is test => tset si sihT
2) tset si sihT => test is This


Q) Insertion in a sorted list.
Sol:-
list* insertInSorted(list *head) 
{
list *tmp;
list *store_head = head;

if( !head ) // list is empty
{
tmp->data = data;
tmp->next = NULL;
return tmp;
}

if( head & !head->next ) // only one node is there currently
{
if( data < head->data ) // new node should be head
{
tmp->data = data;
tmp-> next = head;
return tmp;
}
else // new node should be after head
{
tmp->data = data;
head->next = tmp;
tmp-> next = NULL:
return head;
}
}

while( head->next )
{
if( data < head->next->data )
break;
head = head->next;
}

if( !head->next ) // we are at the end of the list, insert at the end
{
tmp->data = data;
tmp->next = NULL;
head->next = tmp;
return store_head;
}

// we are in the middle of the list
tmp->data = data;
tmp->next = head->next;
head->next = tmp;

return store_head;
}


Q) Finding the depth of a binary tree
Sol:-
int Depth (struct NODE *Node, int Level)
{
if (Node != NULL)
{
if (Level > depth)
depth = Level;
Depth (Node->Left_Child, Level + 1);
Depth (Node->Right_Child, Level + 1);
}
return (depth);
}


Q) Given two strings S1 and S2. Delete from S2 all those characters which occur in S1 also and finally create a clean S2 with the relevant characters deleted.
Sol:-
There are two different solutions I could think of:
1) If we are looking for a space efficient solution: We go through each character of S2 and check all the characters in S1 if there is a matching one, if there is a matching we delete that character and proceed. The disadvantage of this approach is you need to go through S1 no. of characters in S2 times.
2) If we are looking for runtime efficient solution: We declare a hash array of size equal to total no. of possible characters and initialize all the elements to 0. Now we go through S1 and we set the bit in the hash array to 1 for the corresponding character. So now we can determine which characters are present in S2 while going through that string.
Waiting for more efficient ones....

Q) what is the difference between global int & static int declaration?
(or) What is the use of static global int?

Sol:-
When we declare a variable in the c file outside any of the function, then it is treated as a global variable. That variable can be used in other c files by using the "extern" keyword. If we use the keyword "static" for that variable then its treated as a static variable. static variable in this sense is the scope of that variable is limited to the file in which it is declared, this is generally used to prevent from using the global variables that are defined in some other files.

Q)
Consider the following program:

#include
main()
{
int i=3;
int *j;
int **k;
j=&i;
k=&j;
printf("Address of i=%un",&i);
printf("Address of j=%un",&j);
printf("Address of k=%un",&k);
return 0;
}
Suppose the answer is:
Address of i=2004
Address of j=2002
Address of k=2000
why is the address decreasing ?

Sol:-
Depending on the processor architecture, the stack grows downwards. As the local variables are being stored on the stack, there is a chance to see the address decreasing.

Q)
the following program fragment
int m=n=b=8;
char wer[80];
sprintf(wer, "%d%d%d", m, n, b,);
puts (wer):

1. prints the string 8 8 8
2. prints the null string
3. prints the string m, n, b
4. none of these

Sol:-
Choice 4 is correct, because n & b are undeclared.
For this to work, the tweak can be:
int n,b;
int m=n=b=8;
Now intended output 888 can be obtained.

Q)
void main()
{
int *ptr =55;
printf("%d", ++(ptr));
}

Sol:-
In the first place its not correct to directly assign a value to the pointer variable, pointer variable is intended to point to the address of another variable, sometimes pointing to some memory regions might result in "segmentation fault".
In the case where it works the printf will print 57 or 59 depending on no. of bytes an integer takes on the machine the program compiled.

Q) what is the difference between these two syntax #include<stdio.h> and #include "stdio.h"
Sol:-
When we declare the header file using <>, the compiler will look for the file in the standard library directories and then directories specified in the path variable and then the local directory.
But if we declare the header file using "", the compiler will look for the file first in the local directory and then checks for standard library directories.
That's why in almost all the cases we use <> for standard header files and "" for the header files that we declare ourselves.

Q) printf ("%d" ,printf {"tim") );
Choice:
1. results in a syntax error
2. outputs tim 3
3. outputs garbage
4. prints tim and terminates abruptly

Sol:-
Choice 1 is correct because the second printf starts with '{' instead of '('.
If it has been '(' then the choice would be 2 because printf returns no. of characters that were output.

Q) How to allocate memory to multi-dimensional arrays?
Sol:-
#define ROW 5    
#define COL 6
int main()
{
int **arr;
arr = (int *)malloc(sizeof(int*) * ROW); /* Allocating memory for arr */
for (i = 0; i < ROW; i++)
arr[i] = (int*) malloc(sizeof(int) * COL); /* Allocating induvissual elements in array */
}


Q) Find the output for the following C program
main()
{
char *ptr = "Ramco Systems";
*ptr++;
printf("%s\n",ptr);
ptr++;
printf("%s\n",ptr);
}
explain difference between *ptr++ and ptr++

Sol:-
The output will be
amco Systems
mco Systems
In the above example it doesn't matter because as ++ have higher precedence that *
*ptr++ is treated as *(ptr++)
so in *ptr++, first we increment the pointer to next location and dereference it.
In the second case ptr++, we just increment the pointer to point to next location
In the first case if our intension is to increment the value at *ptr we should use the right paranthesis (*ptr)++

Q) You are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). ( or )
There are numbers from 1 to N in an array. out of these, one of the number gets duplicated and one is missing. The task is to write a program to find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..).

Sol:-
S = sum of n natural numbers
X = sum of the given set of numbers
Duplicate no = n - (S-X)

Q)
char *f(void)
{
char *a;
a=malloc(sizeof(char)*10);
strcpy(a,"hello World");
return a;
}
int main()
{
char *b;
b = f();
printf("%s",b);
}
Is there any error in this code?

Sol:-
This program might work fine sometimes, but it might cause memory corruption because we allocated only 10 char locations for a and we are using 12 ( 11 for hello world + 1 for '\0' ).
Other possible bugs might be:
we are not checking for NULL after allocation memory to a, if the malloc() fails to allocate memory the program might fail at strcpy.