Solutions to C programming questions

1 solution) gives compiler error because of post increment on an expression and it it valid only on variable


2 solution) 9 9 56



3 solution) ans1: x*=y+1;
ans2:x*=++y,y--;



4 solution) emptystring or nthing



5 solution) First call can take an integer as input whether or not you put any spaces/newlines/white space characters before it.
But the second call expects at least one ' ' [ space ] character and then some/none white space characters and then an integer.



6 solution) 16


7 solution) 1111


8 solution) prints the numbers in 2 rows each containing 10 elements with in between spaces


9 solution) it won't because of overflow in the statement *a=*a+*b;


10 solution) 4 8


11 solution) 987641

12 solution) 2 1 2

13 solution) unsigned/**/int/**/p;


14 solution) 3 3 5 5


15 solution) output1:2 3
output2:2 4


16 solution) 111


17 solution) 82


18 solution) segmentation fault


19 solution) 15


20 solution) (nil)


21 solution) It prints the lower case letters present in the input


22 solution) 3 1


23 solution) 12
concatinate(1,2)


24 solution) *1 -> replacing '<' with '+' in the declaration of the loop #include
int main(){
int n = 42;
for(int i = 0; i + n; i-- )
printf("-");
return 0;
}
* 2 -> replacing n with i in the declaration of the loop
#include
int main(){
int n = 42;
for(int i = 0; i <> adding a '-' before i in the comparison in for loop
#include
int main(){
int n = 42;
for(int i = 0; -i < href="http://placementsindia.blogspot.com/2007/10/c-programming-questions.html">

Modified Array based QuickSort with respect to the Partition Strategy

Recall that the linked-list version of quicksort() puts all items whose keys are equal to the pivot's key into a third queue, which doesn't need to be sorted. This can save much time if there are many repeated keys.

The array-based version of quicksort() does not treat items with equal keys specially, so those items are sorted in the recursive calls.

Is it possible to modify array-based quicksort() so that the array is partitioned into three parts (keys less than pivot, keys equal to pivot, keys greater than pivot) while still being in-place? (The only memory you may use is the array plus a constant amount of additional memory.)

Why or why not?

Solution:In the first place,whatever I put here is only my approach to solve this problem and much better solution might exist.Now getting on to the solution..

In linked list implementation,we simply modify the pointers so that we end up with 3 lists.One list L1 to contain all the keys less than pivot ,one L2 with keys equal to the pivot and the other L3 with keys greater than pivot.Hence what we require is only an additional head pointer which points to this list L3 containing all elements equal to the pivot.SO we do not require any significant additional memory !!

But this is not the case with array implementation wherein we are confronted by difficulties arising from fixed size of array .If at all we want to maintain a list of keys equal to the pivot, then we need to maintain a separate array and also need to remove all those from the original array,which means a herder's task.


We will do it in much simpler way.Whenever,a duplicate entry of pivot is encountered by the left pointer,swap it with some element ,smaller than pivot and positioned to its left.Hence we move all the pivots encountered by the left pointer to the left extreme of the array. Similarly move all the pivots encountered by the right pointer to the right side of the array.
Now we have all the elements equal to the pivot on either extreme ends of the array.
In the middle,we have remaining 2 sub-arrays.Now the array looks like this
L2-left L1 L3 L2-right
Now get all these pivot elements in the left extreme (L2-left) to occupy the positions preceding L3 by swapping with those elements on the right portion of the first list L1.Similarly do swaps to get L2-right next to L2-Left by swapping its elements with those elements on the left portion of 3rd list L3.Now we have array in the form L1,L2,L3 where L2-left and L2-right are joined into one.

Now we can recursively sort L2-left and L2-right.

I am also putting the code of normal array based quicksort and this modified version ,so that once can verify it.





int leftpivotcounter=0; //global variable
int rightpivotcounter=0; //global variable
// these 2 are the only additional space used to accomplish the task in modified quicksort.


void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void normal_quicksort(int *arr,int left,int right)
{
if(left>=right)
return;
else if(right-left==1)
{
if(arr[left]>arr[right])
swap(arr+left,arr+right);
}
else
{
swap(arr+(left+right)/2,arr+right);
int rpos=right,lpos=left;
int pivot=arr[right--];
while(left {
while(left left++;
while(right>=lpos &&arr[right]>=pivot )
right--;
if(left <=right )
{
swap(arr+left,arr+right);
}
else if (left > right )
{

swap(arr+right+1,arr+rpos);

partition(arr,lpos,right);
partition(arr,right+2,rpos);
break;
}

}
}
}


void modified_quicksort(int *arr,int left,int right)
{
if(left>=right)
return;
else if(right-left==1)
{
if(arr[left]>arr[right])
swap(arr+left,arr+right);
}
else
{
swap(arr+(left+right)/2,arr+right);
int rpos=right,lpos=left;
leftpivotcounter=lpos-1;
rightpivotcounter=rpos;
int pivot=arr[right--];
while(left {
while(left {
if(arr[left]==pivot)
{
leftpivotcounter++;
swap(arr+leftpivotcounter,arr+left);
}
left++;
}
while(right>=lpos &&arr[right]>=pivot )
{
if(arr[right]==pivot)
{
rightpivotcounter--;
swap(arr+rightpivotcounter,arr+right);
}
right--;
}
if(left <=right )
{
swap(arr+left,arr+right);
}
else if (left > right )
{
swap(arr+right+1,arr+rpos);
for(int i=0;(i+lpos<=leftpivotcounter) &&((2*i) {
swap(arr+lpos+i,arr+right-i);
}
for(int i=0;(rpos-i-1>=rightpivotcounter) && (rpos > right+3+2*i) ;i++)
{
swap(arr+rpos-1-i,arr+right+2+i);
}
partition(arr,lpos,right-(leftpivotcounter-lpos+1));
partition(arr,right+2+(rpos-rightpivotcounter),rpos);
break;
}

}
}
}

Last Non Zero Digit of Factorial

Question Write a program that can compute the last non-zero digit of any factorial for ( 0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce 2 because 5! = 120, and 2 is the last nonzero digit of 120.

Solution:Well if one has thoroughly gone through the post,
the answer is easy to arrive at.Since the question asks only about the last non Zero digit,we need not bother about calculating the whole factorial and can just keep track of last nonzero digit by writing nonzerodigit(N)=nonzerodigit(N* nonzerodigit(N-1)).

Here follows the last nonzero digits of first 5 numbers.
N factorial Last Non Zero Digit

1! 1
2! nonzerodigit(2*1)=2
3! nonzerodigit(3*2)=6
4! nonzerodigit(4*6)=4
5! nonzerodigit(4*5)=2!!!(one gets zero if only the last digit is tracked)

So ,it should be clear the mere tracking of last digit is not enough but we need to track some K digits in each factorial.
So we track the last K digits of factorial of each number and store them in a vector V.
At the same time we want to have minimum K.
A brief thought would suggest that we should track of that many no of digits such that for all numbers <=1000 we should never encounter a 0 in V.

This means K is 1+ maximum no of zeros one would encounter in N! for N<=1000.

In this particular case K is 1+5 (maximum no of zeros is 5 since 5^5=3125 and 5^6>10000).

So track the last 6 digits of each of the factorials.Thus we arrived at the solution!!

Question If you have already solved the above problem, then give a generalized method to find the last X non-zero digits of N factorial

Solution:This question is similar to the above one except that we need to track X-1 more digits of N! .
so answer to this is X+No of zeros in N! factorial.

Quick Sort routine to find the kth smallest element in an array

Question Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted.

Solution:We make slight modifications to the quicksort routine to find the kth smallest element.Like in normal quicksort,we choose a pivot and partition the remaining array in to 2 sub arrays.At this stage,we have 3 possibilities.

1)the size of the first sub array is k-1 ,in which case pivot itself is the kth smallest.
2)the size of the first sub array is greater than k ,in which case kth smallest element is to be recursively searched in the first sub-array.

3)the size of the first sub array is less than k-1 ,in which case reuired element is to be recursively searched in the second sub-array.


Hence unlike quicksort where each problem gives rise to 2 subproblems,here each problem gives rise to only 1 sub problem.

Pseudo Code:

QuickSelect(Array A, n, k)
pivot = A [Random(1, n)]
X={x | x belongs to A and x <=pivot}
Y={x | x belongs to A and x >=pivot}
if size(X) = k
return pivot;
else if size(X) < k
return QuickSelect(Y,n-size(X)-1,k-size(X)-1);
else
return QuickSelect(X,size(X),k);

Run time Analysis of QuickSort ,Nature of Input,Pivot strategies

Question Determine the running time of QuickSort for

a.Sorted input
b.reverse -ordered input
c.random input
d. When all the elements are equal



Solution:This solution is being written with the assumption that middle element of the array is chosen as the pivot.The answers differ based on the pivot selection as well.
a.Sorted input
In the case of sorted input,the left and right pointers of the sub arrays pass each other with out a single swap in all the iterations.The problem is divided in to 2 equal problems in all but the base case of unit size array.Hence the recurrence relation for this case is T(N)=2*T(N/2)+O(N).Hence the complexity in this case is O(NlogN).

b.reverse-ordered input

This case is identical to the previous case except that we have so many swaps in each iteration.The left and right pointers swap the content on each increment in their directions.This effects only the O(N) part of the recurrence relation that we have in the previous case.But as the swap is of complexity O(1), the complexity of each iteration remains the same.And the division of the array is still even.So the complexity doesn't change.Hence it is still O(NlogN)

c.Random Input
Well there are theorems asserting that the complexity of quicksort on a random input is O(NlogN).We will prove it by considering evenly the chances of even and worst splits.
let's consider that good and bad splits alternate in the iterations, with good splits in the best case (N/2) and bad ones in the worst (N-1).
So every two levels, the array's been cut in half,which means, it's still exponential reduction -- O(NlogN ).

d. When all the elements are equal

It is as good as the sorted array.So the complexity is O(NlogN).

Question The ones who are familiar with QuickSort might also be well aware of the important phase of the algorithm-the pivot selection.Suppose we always choose the middle element as the pivot .Does this make it unlikely that QuickSort will require quadratic time?


Solution:Choosing the middle element never makes it unlikey that the QuickSort will require quadratic time.One might encounter an input in which the middle element is always the maximum in all iterations.Then the complexity will be quadratic.

example:a={1,3,2} choosing 3 as pivot produces 2 subproblems , one of size 0 and other of size 2.In the next iteration,with out loss of generality take 2 as the pivot.It produces a sub array of size 1 and another of size 0.Thus an input can always be generated in such a way that QuickSort routine always gives rise to 2 subarrays,one of them being of size 0.Hence quadratic time is not always avoidable.

Question What is the worst-case behavior (number of comparisons) for quick sort?
Solution:As we have seen in the previous question,because of a bad pivot selection we might at the worst run in to quadratic time complexity.

Question In selecting the pivot for QuickSort, which is the best choice for optimal partitioning:
a.The first element of the array
b.The last element of the array
c.The middle element of the array
d.The largest element of the array
e.The median of the array
f.Any of the above


Solution:while the choices a,b,c will always not guarantee O(NlogN) complexity,choice d always gives quadratic run time.choice e guarantees even partition of the array.Hence it is the optimal partition.
hence the sol is e.

Question In its worst case QuickSort behaves like:
a.Bubble sort
b.Selection sort
c.Insertion sort
d.Bin sort


Solution:In the worst ,the pivot selected will always be the maximum element leading to quadratic time complexity.In this case as it depicts the behaviour of bubble sort,where in maximum element always bubbles to the end.

Tree Arithmetic

1)If a tree has N nodes, then how many are the edges?

Solution:Every node has a parent except the root.Each edge associates a node with its child.So the number of edges are N-1.

2)Prove that there exists only a single path from each node to the root?
Solution:If there are more than 1 paths from a node to the root,it means there are more than 1 parents for one of the ancestors of the node concerned, which is impossible in a tree.

3)Prove that the depth of a tree is always equal to the height of the tree?

Solution: Height of a tree is the height of the root.Depth of a tree is the depth of the deepest node, which is the number of edges from root to it.This should also be the node which defines the height of the root,otherwise we end up with a contradiction.

4)The structure of a typical tree is to have in each node ,besides it data, a pointer to each of its children.But this might be infeasible if there aren’t fixed number of children at each node.So how do modify this data structure to accommodate variable no of children at each node?


Solution:Well the answer to this is child sibling relationship.


5)What are the maximum and minimum depths of a binary search tree?

Solution:In a binary tree of N nodes,the maximum depth is N-1 when it develops only on 1 side and the minimum is floor(log(N)).


6)How many are the no of null pointers for a binary tree of N nodes?

Solution: Total no of pointer=2*N. And each edge is associated with 1 pointer.
So the no of null pointer is 2*N-(N-1)=N+1 .

7)Distinguish inorder , preorder and postorder traversals properly?
Solution: Inorder traversal:Left subtree is first processed ,followed by root and then by right subtree.

Preorder: root is first processed followed by left and right subtrees.There is no order defined between left and right children.Essentially left and right subtrees are traversed only after the root is traversed.

Postorder:Left and right children are traversed before traversing root.


8)How is a binary tree different from binary search tree?

Solution:In Binary search tree, all the elements in the left subtree are <= root and all the elements in the right subtree are >= root,which is not the case with all the binary trees.

9)Recursive calls have always been employed in the case of trees because of their recursive structural property.But linked lists aren’t that different .But why recursion is not that advisable in the case of lists?(A little theoretical …. Think in terms of limited stack size of your machine)

Solution:The depth of a well built tree of N nodes is log(N).So recursive calls are affordable most of the times as stack overflow is seldom possible.But if recursive calls are employed for lists, then the order of recursive call stack size is N which
is not feasible for large N.

10)What are the complexities of insertion,deletion on a binary search tree?

Solution:Insertion in a well built binary search tree is O(logN) and so is the deletion.This is under assumption that depth of tree is O(logN).


11)Show that the maximum number of nodes in a binary tree of height H is 2^(H+1) -1

Solution:In a binary tree of height H ,with maximum number of nodes,all the levels should be completely filled.At depth d, the number of nodes should be 2^d.
Therefore, the total number of nodes =1+2+4+....+2^H=2^(H+1)-1.

Number of ways to express a number as summation of consecutive numbers

Question.All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer ,you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.

Solution:
2+3+4=(1+2+3+4)-(1)
=(1+2+3+4+5)-(1+2+3)
=(1+2+3+4+5+6+7+8+9)-(1+2+3+4+5+6+7+8)

This shows that the no of solutions to this problem is the no of tuples (n,m) such that
given number K can be expressed as K=(1+2+..........+n)-(1+2+3+...........+m)
and n > m

i.e K=n*(n+1)/2 -m*(m+1)/2
=(n-m)(n+m+1)/2
2*k=(n-m)*(n+m+1)
If we put the factor n-m=p and (n+m+1)=q,we get S=2*k=p*q
As p+q=2*n+1 is odd and S is even either n-m is odd otherwise n+m+1 is odd.
This leaves out with finding out the no of odd divisors of S,which can be easily done using prime factorization.
if S=(2^p)*(3^q)*(5^r)*(7^s)......

then the solution is (q+1)*(r+1)*(s+1)*.. i.e the no of odd divisors of S.

Solutions to Logical Puzzles-2

)3
It is of the form 0^2+2,1^2+2,3^2+2,6^2+2,10^2+2,.....
The sequence of n is 0,1,3,6,10,... so the next n is 15 => 15^2+2

2)2
The function is S(n)=S(n-1)*(n+2) + 3 ,n>1
=6 ,n=1

3)1
It is of the form S(n)*3+2 for even and S(n)*2-3 for odd where S(n) is the nth element.
So 7th element = 239*2-3=475

4)2
The function is S(n)=(n+2)^3 -2

5)1
The numbers in the sequence is a combination of n^2 and n^3 and n is odd.

6)2
The function is S(n)=S(n-1)*n-n n>1
=3 n=1

7)

8)1
The function is S(n)=(S(n-1)-1)*(n-1) n>1
=8 n=1

9)

10)

Combinations

Question:Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.So given 5<=N<=100 5<=M<=100 and M<=N.Compute the EXACT value of: N!/(M!*(N-M)!) The final value of C will fit in a 32-bit Pascal LongInt or a C long. So deduce an approach based on this assumption given.

Solution:At a mere glance,this problem may seem to have a direct solution,though it isn't upon a long thought.The naive approach to calculate combination of N things taken M at a time is obtained by mere application of formula,which mean finding N! ,M! and (N-M)! and the putting them in the expression.But as N and M are independently large enough for overflows to occur in N! and M! calculations.
One of the approaches to solve this problem,based on prime factorization can be formulated in the following manner.

Consider a prime P whose exponents in N!,M! and (N-M)! are p1,p2 and p3 respectively.

therefore the exponent of P in N!/M!*(N-M)! is p1+p2-p3.

This way we can store the exponents of all primes <= the largest prime which divides N.

One this is done ,we can merely multiply all these primes each raised to its exponent to get the required answer.


Now getting on to the tricky part of finding the exponent of a prime P in N!

In general ,if P is any prime,then the no of P's in N! is given by
Sum (floor(n/P^i)) for P^i <= N This apparently weird formula can be explained with ease!! consider the numbers 1,2,3,.........,,N.Every Pth number is divisible by P.So all those multiples of P put together contribute floor(N/P) to the power of P. Similarly every P^2th number is divisible by P^2.And each of them have already contributed 1 to power of P in previous iteration,as each of them are divisible by P.So each of them contribute an additional 1, which means they all together contribute floor(N/P^2) to the already sum. These terms of contribution go on till we have P^i <= N,hence the summation Sum (floor(N/P^i)) for P^i <= N The Cpp implementation of above task is given below


#include
using namespace std;
#include
#include
#include
#include
typedef vector powers;
void insert(vector &P,int i,vector V,int size)
{
vector temp=P[i-1];
//calculation of exponent of each prime
for(int j=0;j {
while(i%V[j]==0)
{
temp[j]++;
i/=V[j];
}
}
P.push_back(temp);
}
int main()
{
vector V;
vector P;
V.push_back(2);
bool flag;
int N,R;
for(int i=3;i<100;i+=2)
{
flag=true;
for(int j=0;V[j]*V[j] <=i;j++)
{
if(i%V[j]==0)
{
flag=false;
break;
}
}
if(flag)
{
V.push_back(i);
}
}
int size=V.size();
vector temp(size,0);
P.push_back(temp);
P.push_back(temp);
for(int i=2;i<=100;i++)
{
insert(P,i,V,size);
}
while(cin >> N >>R)
{
if(N==0 && R==0)
{
return(0);
}
else
{
long sol=1;
for(int i=0;i {

sol*=(long)pow((double)V[i],P[N][i]-P[R][i]
-P[N-R][i]); //Pi^(p1-p2-p3)
}
cout< "< "<

}

}
return(0);
}

Solutions to Basic C Interview Questions

Click here for the questions>

1)To check for it, create two pointers,and set each to the start of the list. Update each as follows:

while (pointer1) {
pointer1 = pointer1->next;
pointer2 = pointer2->next;
if (pointer2) pointer2=pointer2->next;
if (pointer1 == pointer2) {
print ("circular linked list\n");
}
}

2)Union x : 1101791232 21.500000
Union y : 100 d 0.000000

3)It is an object of some class whose purpose is to indicate that a real object of that class does not exist. One common use for a null object is a return value from a member function that is supposed to return an object with some specified properties but cannot find such an object.

4) Java,Smalltalk,Eiffel,Sather.

5)A container class is a class that is used to hold objects in memory or
external storage. A container class acts as a generic holder. A
container class has a predefined behavior and a well-known interface. A
container class is a supporting class whose purpose is to hide the
topology used for maintaining the list of objects in memory. When a
container class contains a group of mixed objects, the container is
called a heterogeneous container; when the container is holding a group
of objects that are all the same, the container is called a homogeneous
container.

6)fffffff0

7)C was the C++ predecessor. As it's name implies, a lot of C remains in C++. Although not actually being more powerful than C, C++ allows the programmer to more easily manage and operate with Objects, using an OOP (Object Oriented Programming) concept.

C++ allows the programmer to create classes, which are somewhat similar to C structures. However, to a class can be assigned methods, functions associated to it, of various prototypes, which can access and operate within the class, somewhat like C functions often operate on a supplied handler pointer.

Although it is possible to implement anything which C++ could implement in C, C++ aids to standarize a way in which objects are created and managed, whereas the C programmer who implements the same system has a lot of liberty on how to actually implement the internals, and style among programmers will vary a lot on the design choices made.

In C, some will prefer the handler-type, where a main function initializes a handler, and that handler can be supplied to other functions of the library as an object to operate on/through. Others will even want to have that handler link all the related function pointers within it which then must be called using a convention closer to C++.

To finish this discussion, C++ applications are generally slower at runtime, and are much slower to compile than C programs. The low-level infrastructure for C++ binary execution is also larger. For these reasons C is always commonly used even if C++ has alot of popularity, and will probably continue to be used in projects where size and speed are primary concerns, and portable code still required (assembly would be unsuitable then).

8)Incomplete types
refers to pointers in which there is non availability of the
implementation of the referenced location or it points to some location
whose value is not available for modification.

int *i=0x400 // i points to address 400
*i=0; //set the value of memory location pointed by i.

9)Printf : Call by value
Scanf : Call by reference

10)a const pointer means the pointer which represents the address of one value. so if you declare a pointer inside the function, it doesn't have scope outside the function. if it is also available to the outside function whenever we declare a pointer as const.

11)Type casting must be done wheneever the data type of the variable to which u r gonna assign some values is diff from the data type of the variable on the right side.

for instance;

float f;
int i = 10 , j = 5 ;

f = (float) ( i / j ) ;

f -------> left side variable.
i -------> right side variable.

but always make sure that the size of the var on the left is greater than that of the right. else there will be data loss.

A type cast should not be used to override a const or volatile declaration. Overriding these type modifiers can cause the program to fail to run correctly.
A type cast should not be used to turn a pointer to one type of structure or data type into another. In the
rare events in which this action is beneficial, using a union to hold the values makes the programmer.s
intentions clearer.

12)he answer is the standard library function qsort(). It.s the easiest sort by far for several reasons:
It is already written.
It is already debugged.
It has been optimized as much as possible (usually).
Void qsort(void *buf, size_t num, size_t size, int (*comp)(const void *ele1, const void *ele2));

13)The answer depends on what you mean by quickest. For most sorting problems, it just doesn't matter how quick the sort is because it is done infrequently or other operations take significantly more time anyway. Even in cases in which sorting speed is of the essence, there is no one answer. It depends on not only the size and nature of the data, but also the likely order. No algorithm is best in all cases.
There are three sorting methods in this author.s .toolbox. that are all very fast and that are useful in different situations. Those methods are quick sort, merge sort, and radix sort.

The Quick Sort
The quick sort algorithm is of the .divide and conquer. type. That means it works by reducing a sorting
problem into several easier sorting problems and solving each of them. A .dividing. value is chosen from the input data, and the data is partitioned into three sets: elements that belong before the dividing value, the value itself, and elements that come after the dividing value. The partitioning is performed by exchanging elements that are in the first set but belong in the third with elements that are in the third set but belong in the first Elements that are equal to the dividing element can be put in any of the three sets.the algorithm will still work properly.

The Merge Sort
The merge sort is a .divide and conquer. sort as well. It works by considering the data to be sorted as a
sequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don.t fit into memory. It also can be implemented as a stable sort.

The Radix Sort
The radix sort takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints.

14)Both the merge sort and the radix sort are good sorting algorithms to use for linked lists.

15)The preprocessor is used to modify your program according to the preprocessor directives in your source code. Preprocessor directives (such as #define) give the preprocessor specific instructions on how to modify your source code. The preprocessor reads in all of your include files and the source code you are compiling and creates a preprocessed version of your source code. This preprocessed version has all of its macros and constant symbols replaced by their corresponding code and value assignments. If your source code contains any conditional preprocessor directives (such as #if), the preprocessor evaluates the condition and modifies your source code accordingly.
The C preprocessor is used to modify your program according to the preprocessor directives in your source code. A preprocessor directive is a statement (such as #define) that gives the preprocessor specific instructions on how to modify your source code. The preprocessor is invoked as the first part of your compiler program.s compilation step. It is usually hidden from the programmer because it is run automatically by the compiler.

16)The standard C library provides several functions for converting strings to numbers of all formats (integers, longs, floats, and so on) and vice versa.

The following functions can be used to convert strings to numbers:
Function Name Purpose
atof() Converts a string to a double-precision floating-point value.
atoi() Converts a string to an integer.
atol() Converts a string to a long integer.
strtod() Converts a string to a double-precision floating-point value and reports any .leftover. numbers that could not be converted.
strtol() Converts a string to a long integer and reports any .leftover. numbers that could not be converted.
strtoul() Converts a string to an unsigned long integer and reports any .leftover. numbers that could not be converted.

17)
The standard C library provides several functions for converting numbers of all formats (integers, longs, floats, and so on) to strings and vice versa

The following functions can be used to convert integers to strings:
Function Name Purpose
itoa() Converts an integer value to a string.
ltoa() Converts a long integer value to a string.
ultoa() Converts an unsigned long integer value to a string.

The following functions can be used to convert floating-point values to strings:
Function Name Purpose
ecvt() Converts a double-precision floating-point value to a string without an embedded decimal point.
fcvt() Same as ecvt(), but forces the precision to a specified number of digits.
gcvt() Converts a double-precision floating-point value to a string with an embedded decimal point.

18)The heap is where malloc(), calloc(), and realloc() get memory.
Getting memory from the heap is much slower than getting it from the stack. On the other hand, the heap
is much more flexible than the stack. Memory can be allocated at any time and deallocated in any order. Such
memory isn't deallocated automatically; you have to call free().
Recursive data structures are almost always implemented with memory from the heap. Strings often come
from there too, especially strings that could be very long at runtime. If you can keep data in a local variable (and allocate it from the stack), your code will run faster than if you put the data on the heap. Sometimes you can use a better algorithm if you use the heap.faster, or more robust, or more flexible. It's a tradeoff.
If memory is allocated from the heap, it.s available until the program ends. That's great if you remember to deallocate it when you.re done.

19)n++ takes more than one instruction, ++n is faster. n++ has to store n, increment the variable and return n, while ++n increment n and return without storing the previous value of n.

20) If a program is large, it is subdivided into a number of smaller programs that are called modules or subprograms. If a complex problem is solved using more modules, this approach is known as modular programming.

21)expression if (a=0) always return false
expression if (a=1) always return true

22)Malloc is dynamic memory allocation,it allocates the memory and initialize garbage value.Calloc is similar to malloc but only difference is initialize zero

23)A middle level language

24)Overloading is polymorphism which is one of the characteristics of Object oriented programming. C is not and object oriented language like C++ or Java. Therefore, no overloading, inheritance, etc.

25)Static int variable are accessed only inside the file where it is defined. Thus we can have same variable name in 2 files if the variable is defined as static. The scope of the variable is limited to the file in which it is defined.

On the other hand if the variable is not defined as static and defined globally then it can be accessed across the files. To access the variable which is global variable and declared and defined in file A, keyword "extern" is used in front of the variable in file B. This indicated to compiler while compiling that the variable is defined in some other file other than B and continues compiling and while linking the variable it search for the actual definition and links.

Solutions to Logical Puzzles-1

Click here for the questions

We need 3 cuts to cut a cube into 6 equal pieces,with one cut in each dimension.Maximum identical pieces obtained with n cuts[if n is a factor of 3] = (n/3 + 1)^3, with n/3 cuts, we form n/3 + 1 equal pieces.If we need to get maximum number of identical cubes with some number of cuts then the number of cuts in all the dimensions should be equal if possible or almost equal.
The number of identical pieces formed with l,n,m cuts in the 3 demensions are (l+1)*(n+1)*(m+1).

1)3,Here there are 6,7,8 cuts in each dimension

2)2

3)4,Here the number of cuts are 7,7,6 in the 3 dimensions.

4)1

5)3

All the problems from 6-18 are based mostly on imagination.Note that 27 identical pieces have no color at all i.e they are inner pieces.

6)3

7)4

8)1

9)3

10)2

11)2

12)4

13)1

14)4

15)3

16)1

17)4

18)1

19)2

20)4

Solutions to Logical Puzzles-3

Click here for the questions

1)

2)3,
The number obtained by dividing 48 with 4 is 12 which is even while all the others get odd number for the same.

3)4,
The sequence has to be AON,EWR,IEV,MMZ

4)2
The remaining 3 are input devices.

5)2
The remaining 3 represent an image.

6)3
Trousers can only take a plural form while others can also take a singular form.

7)

8)

9)4
All the other three lie inside a cell.

10)

11)4

12)3

13)1

14)2

15)3

16)3

17)1

18)3

19)3

20)4

C program to find the height of a binary search tree

Question:Write a C program to find the depth or height of a binary tree

Solution:
#include

struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

int max(int a,int b)
{
if(a >=b)
return a;
else
return b;
}

int height(tree T)
{
if(T==NULL)
return 0;
else
{
int h1=height(T->left);
int h2=height(T->right);
return 1+max(h1,h2);
}
}

C program to determine the number of nodes in a binary tree

Question:Write a C program to determine the number of elements(or size) in a binary tree?

Solution:


#include
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;


int tree_size(tree T)
{
if(T==NULL)
return 0;
else
{
return 1+tree_size(T->left)+tree_size(T->right);
}
}

C program to delete a tree

Write a C program to delete a tree(i.e, free up its nodes)


#include
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

void tree_free(tree T)
{
if (T==NULL)
return;
else
{
tree_free(T->left);
tree_free(T->right);
free(T);
}
}

Minimum Value of a Binary Search Tree

Question:Write a C program to find the minimum value in a binary search tree.

Solution:

#include
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

tree min(tree T)
{
if (T==NULL)
return NULL;
else
{
if(T->left==NULL)
return T;
else
return min(T->left);
}
}

Solutions to Questions on recursion

Click here for the questions


1)
int Fibinocci(int n)
{
if(n==1)
return 1;
else
n+Fibinocci(n-1);
}

2)
void reverse(char*str)
{
if(*str != '\0')
reverse(str+1);
}

3)
int Factorial(int n)
{
if(n==1)
return 1;
else
return(n*Factorial(n-1);
}

4)
void MoveTower(int disk, int source, int dest, int spare):
{
if(disk == 1)
printf("Move top disc from %d to %d\n",source,desc);
else
{
MoveTower(disk - 1, source, spare, dest);
printf("Move top disc from %d to %d\n",source,desc);
// Step 2
MoveTower(disk - 1, spare, dest, source);
}
}

5)
int gcd(int a,int b)
{
if(b==0)
return(a);
else
return(gcd(b,a(mod)b);
}


6)
arr is an array containing N integers.You can also change the program by keeping characters.k is initially 0.


void permutation(int *arr, int N, int k)
{
static level = -1;
level = level+1;
arr[k] = level;

if (level == N)
{
if(arr!=0)
for(int i=0; i < N;i++)
printf("%d",arr[i]);
}
else
for (int i = 0; i < N; i++)
if (arr[i] == 0)
permutation(arr, N, i);
level = level-1;
arr[k] = 0;
}

7)void combinations(char*str,int no)
{
int temp1=0;
int i,count,n=1,num,len;

for(i=0;*(str+i)!='\0';i++);
len=i;

for(i=0;i < len;i++)
n=2*n;
temp=(int*)malloc(len*sizeof(int));
for(i=0;i < len;i++)
*(temp+i)=0;
for(num=0;num <= n;num=num+1)
{
temp1=num;
for(i=0;i < len;i++)
{
*(temp+i) = temp1%2;
temp1=temp1/2;
}
count=0;
for(i=0;i < len;i++)
{
if(*(temp+i)==1)
count++;
}
if(count==no)
{
for(i=0;i < len;i++)
{
if(*(temp+i)==1)
printf("%c",*(str+i));
}
printf("\n");


}
}


8)
Mergesort:a is an array of n intergers,temp is just a temporary array.low is initially 0 and high is n-1.


void mergesort(int *a,int *temp,int low,int hi)
{
int mid;
if(hi==low)
{
return;
}
else
{
mid=(low+hi)/2;
mergesort(a,temp,low,mid);
printf("1\n");
mergesort(a,temp,mid+1,hi);
printf("2\n");
merge(a,temp,low,mid+1,hi);
}
}

void merge(int a[],int temp[],int left,int rig,int r)
{
printf("%d %d %d\n",left,rig,r);
int i,l,n,k;
l=rig-1;
k=left;
n=r-left+1;
while(left<=l&&rig<=r)
{
if(a[left]<=a[rig])
temp[k++]=a[left++];
else
temp[k++]=a[rig++];
}
while(left<=l)
temp[k++]=a[left++];
while(rig<=r)
temp[k++]=a[rig++];
for(i=0;i < n;i++,r--)
a[r]=temp[r];
}


Quicksort:a is an array of n integers.left is initially 0 and right is n-1.


void quick(int *a, int left, int right)
{
int temp,i,k;
temp=left;
if (left>=right)
{
return;
}

k=(left+right)/2;
swap(a,left,k);
for (i=left+1;i<=right;i++)
{
if (a[i] < a[left])
{
swap(a,++temp,i);
}
}

swap(a,left,temp); //swap a[left] and a[temp]
quick(a,left,temp-1);
quick(a,temp+1,right);
}

C program to create mirror copy of a tree

Question:Write a C program to create a mirror copy of a tree left nodes become right and right nodes become left)

Solution:


#include
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

tree mirror_copy(tree T)
{
if(T==NULL)
return T;
else
{
tree temp1=mirror_copy(T->left);
tree temp2=mirror_copy(T->right);
T->left=temp2;
T->right=temp1;
return T;
}
}

Solutions to Amazon Intern Interview Questions

Click here for the questions

1)Place a red ball in a urn and all the further balls in the other urn.The probability for picking out the red ball is now greater than 0.5.

2)If v<=2V then the position is (v*L)/(2*V) from the starting point else it is 2*L -(v*L)/(2*V) from the starting point.



4)If we know the process then we can kill it by killall -9 "process name" else we can kill it using its process id obtained by the command ps -x by kill -9 "processid" .

5)Top command displays all the Linux tasks running at that particular time.It provides their running time and the resources used.

6)The number appearing 2 times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n).
For floating numbers multiply it with 100 and proceed.

Traversals of a Binary Tree

Write C code to implement the preorder(), inorder() and postorder() traversals. Whats their time complexities?


#include
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

void inorder_print(tree T)
{
if (T!=NULL)
{
printf("%d\n",T->data);
inorder_print(T->left);
inorder_print(T->right);
}
}

void postorder_print(tree T)
{
if (T==NULL)
{
return;
}
postorder_print(T->left);
postorder_print(T->right);
printf("%d\n",T->data);
}

void preorder_print(tree T)
{
if (T==NULL)
{
return;
}
printf("%d\n",T->data);
preorder_print(T->left);
preorder_print(T->right);

}


Each of them traverse all the nodes.
So the complexity is O(N).