C-Interview Questions level 9

Answer:- When an array is declared, dimension of array should be specified so that compiler can allocate memory for the array. When array of pointers to strings is declared its elements would contain garbage addresses. These addresses would be passed to scanf( ). So strings can be received but they would get stored at unkown locations. This is unsafe.

Answer:- If in a program a variable is to take only two values 1 and 0, we really need only a single bit to store it. Similarly, if a variable is to take values from 0 to 3, then two bits are sufficient to store these values. And if a variable is to take values from 0 through 7, then three bits will be enough, and so on. Why waste an entire integer when one or two or three bits will do? Because there aren't any one bit or two bit or three bit data types available in C. However, when there are several variables whose maximum values are small enough to pack into a single memory location, we can use `bit fields' to store several values in a single integer. Bit fields are discussed in most standard C texts. They are usually used when we want to store assorted information which can be accommodated in 1, 2, 3 bits etc. For example, the following data about an employee can be easily stored using bit fields. male or female single, married, divorced or widowed have one of the eight different hobbies can choose from any of the fifteen different schemes proposed by the company to pursue his/her hobby. This means we need one bit to store gender, two to store marital status, three for hobby, and four for scheme (with one value used for those who are not desirous of availing any of the schemes). We need ten bits altogether, which means we can pack all this information into a single integer, since an integer is 16 bits long. At times we may need to store several True or False statuses. In such cases instead of using bit fields using an array of bits would be more sensible. On this array we may be required to perform the following operations: Set a bit (make it 1). Clear a bit (make it 0). Test the status of a bit in the array. Reach the appropriate bit slot in the array. Generate a bit mask for setting and clearing a bit. We can implement these operations using macros given below: #define CHARSIZE 8 #define MASK ( y ) ( 1 << y % CHARSIZE ) #define BITSLOT ( y ) ( y / CHARSIZE ) #define SET ( x, y ) ( x[BITSLOT( y )] |= MASK( y ) ) #define CLEAR ( x, y ) ( x[BITSLOT( y )] &= ~MASK( y ) ) #define TEST ( x, y ) ( x[BITSLOT( y )] & MASK( y ) ) #define NUMSLOTS ( n ) ( ( n + CHARSIZE - 1) / CHARSIZE ) Using these macros we can declare an array of 50 bits be saying, char arr[NUMSLOTS(50)] ; To set the 20th bit we can say, SET(arr, 20 ) ; And if we are to test the status of 40th bit we may say, if ( TEST ( arr, 40 ) ) Using bit arrays often results into saving a lot of precious memory. For example, the following program which implements the Sieve of Eratosthenes for generating prime numbers smaller than 100 requires only 13 bytes. Had we implemented the same logic using an array of integers we would have required an array of 100 integers, that is 200 bytes.

 
      #include 
      #include 

      #define MAX 100

      main( )
      { 
      char arr[NUMSLOTS( MAX )] ;
      int i, j ;

      memset ( arr, 0, NUMSLOTS( MAX ) ) ;
      for ( i = 2 ; i < MAX ; i++ )
      { 
      if ( !TEST ( arr, i ) )
      { 
      printf ( "\n%d", i ) ;
      for ( j = i + i ; j < MAX ; j += i ) 
      SET ( arr, j ) ; 
      } 
      } 
      }
      

Answer:- Though C language doesn't fully support encapsulation as C++ does, there is a simple technique through which we can implement encapsulation in C. The technique that achieves this is modular programming in C. Modular programming requires a little extra work from the programmer, but pays for itself during maintenance. To understand this technique let us take the example of the popular stack data structure. There are many methods of implementing a stack (array, linked list, etc.). Information hiding teaches that users should be able to push and pop the stack's elements without knowing about the stack's implementation. A benefit of this sort of information hiding is that users don't have to change their code even if the implementation details change. Consider the following scenario: To be able to appreciate the benefits of modular programming and thereby information hiding, would first show a traditional implementation of the stack data structure using pointers and a linked list of structures. The main( ) function calls the push( ) and pop( ) functions.

      #include 
      typedef int element ;
      void initialize_stack ( struct node ** ) ;
      void push ( struct node **, element ) ;
      element pop ( struct node * ) ;
      int isempty ( struct node * ) ;
      struct node
      {
      element data ;
      struct node *next ;
      } ;
      void main( )
      {
      struct node *top ;
      element num ;
      initialize_stack ( &top ) ;
      push ( &top, 10 ) ;
      push ( &top, 20 ) ;
      push ( &top, 30 ) ;
      if ( isempty ( top ) )
      printf ( "\nStack is empty" ) ;
      else
      {
      num = pop ( top ) ;
      printf ( "\n Popped %d", num ) ;
      }
      }
      void initialize_stack ( struct node **p )
      {
      *p = NULL ;
      }
      void push ( struct node **p, element n )
      {
      struct node *r ;
      r = ( struct node *) malloc ( sizeof ( struct node ) ) ;
      r -> data = n ;
      if ( *p == NULL )
      r -> next = NULL ;
      else
      r -> next = *p ;
      *p = r ;
      }
      element pop ( struct node *p )
      {
      element n ;
      struct node *r ;
      n = p -> data ;
      r = p ;
      p = p -> next ;
      free ( r ) ;
      return ( n ) ;
      }
      int isempty ( struct node *p )
      {
      if ( p == NULL )
      return ( -1 ) ;
      else
      return ( 0 ) ;
      

Notice how the specific implementation of the data structure is strewn throughout main( ). main( ) must see the definition of the structure node to use the push( ), pop( ), and other stack functions. Thus the implementation is not hidden, but is mixed with the abstract operations. Data Structures Radix Sort This sorting technique is based on the values of the actual digits in the positional representations of the numbers being sorted. Using the decimal base, for example, where the radix is 10, the numbers can be partitioned into ten groups on the sorter. For example, to sort a collection of numbers where each number is a four-digit number, then, All the numbers are first sorted according to the the digit at unit's place. In the second pass, the numbers are sorted according to the digit at tenth place. In the third pass, the numbers are sorted according to the digit at hundredth place. In the forth and last pass, the numbers are sorted according to the digit at thousandth place. During each pass, each number is taken in the order in which it appears in partitions from unit's place onwards. When these actions have been performed for each digit, starting with the least significant and ending with most significant, the numbers are sorted. This sorting method is called the radix sort. Let us take another example. Suppose we have a list of names. To sort these names using radix sort method we will have to classify them into 26 groups The list is first sorted on the first letter of each name, i.e. the names are arranged in 26 classes, where the first class consists of those names that begin with alphabet 'A', the second class consists of those names that begin with alphabet 'B' and so on. During the second pass each class is alphabetized according to the second letter of the name, and so on.

Answer:- Consider the following program:

 
      #include 
      void main( )
      {
      float i ;
      i = pow ( -2, 3 ) ;
      printf ( "%f", i ) ;
      }
       
      int matherr ( struct exception *a )
      {
      if ( a -> type == DOMAIN )
      {
      if ( !strcmp ( a -> name, "pow" ) )
      {
      a -> retval = pow ( - ( a -> arg1 ), a -> arg2 ) ;
      return 1 ;
      }
      }
      return 0 ;
      }
       

If we pass a negative value in pow( ) function a run time error occurs. If we wish to get the proper output even after passing a negative value in the pow( ) function we must handle the run time error. For this, we can define a function matherr( ) which is declared in the 'math.h' file. In this function we can detect the run-time error and write our code to correct the error. The elements of the exception structure receives the function name and arguments of the function causing the exception. Data Structures AVL Trees For ideal searching in a binary search tree, the heights of the left and right sub-trees of any node should be equal. But, due to random insertions and deletions performed on a binary search tree, it often turns out to be far from ideal. A close approximation to an ideal binary search tree is achievable if it can be ensured that the difference between the heights of the left and the right sub trees of any node in the tree is at most one. A binary search tree in which the difference of heights of the right and left sub-trees of any node is less than or equal to one is known as an AVL tree. AVL tree is also called as Balanced Tree. The name "AVL Tree" is derived from the names of its inventors who are Adelson-Veilskii and Landi. A node in an AVL tree have a new field to store the "balance factor" of a node which denotes the difference of height between the left and the right sub-trees of the tree rooted at that node. And it can assume one of the three possible values {-1,0,1}.

Answer:- main( ) { long steps, fval, bstp, cnt1 ; int num, unit, box[2][13], cnt2, cnt3, cnt4 ; printf ( "Enter Number " ) ; scanf ( "%d", &num ) ; num = num < 1 ? 1 : num > 12 ? 12 : num ; for ( steps = 1, cnt1 = 2 ; cnt1 <= num ; steps *= cnt1++ ) ; for ( cnt1 = 1 ; cnt1 <= steps ; cnt1++ ) { for ( cnt2 = 1 ; cnt2 <= num ; cnt2++ ) box[0][cnt2] = cnt2 ; for ( fval = steps, bstp = cnt1, cnt2 = 1 ; cnt2 <= num ; cnt2++ ) { if ( bstp == 0 ) { cnt4=num ; while ( box[0][cnt4] == 0 ) cnt4-- ; } else { fval /= num - cnt2 + 1 ; unit = ( bstp + fval - 1 ) / fval ; bstp %= fval ; for ( cnt4 = 0, cnt3 = 1 ; cnt3 <= unit ; cnt3++ ) while ( box[0][++cnt4] == 0 ) ; } box[1][cnt2] = box[0][cnt4] ; box[0][cnt4] = 0 ; } printf ( "\nSeq.No.%ld:", cnt1 ) ; for ( cnt2 = 1 ; cnt2 <= num ; cnt2++ ) printf ( " %d", box[1][cnt2] ) ; } } This program computes the total number of steps. But instead of entering into the loop of the first and last combination to be generated it uses a loop of 1 to number of combinations. For example, in case of input being 5 the number of possible combinations would be factorial 5, i.e. 120. The program suffers from the limitation that it cannot generate combinations for input beyond 12 since a long int cannot handle the resulting combinations. Data Structures Hashing... Hashing or hash addressing is a searching technique. Usually, search of an element is carried out via a sequence of comparisons. Hashing differs from this as it is independent of the number of elements n in the collection of data. Here, the address or location of an element is obtained by computing some arithmetic function. Hashing is usually used in file management. The general idea is of using the key to determine the address of a record. For this, a function fun( ) is applied to each key, called the hash function. Some of the popular hash functions are: 'Division' method, 'Midsquare' method, and 'Folding' method. Two records cannot occupy the same position. Such a situation is called a hash collision or a hash clash. There are two basic methods of dealing with a hash clash. The first technique, called rehashing, involves using secondary hash function on the hash key of the item. The rehash function is applied successively until an empty position is found where the item can be inserted. If the hash position of the item is found to be occupied during a search, the rehash function is again used to locate the item. The second technique, called chaining, builds a linked list of all items whose keys hash to the same values. During search, this short linked list is traversed sequentially for the desired key. This technique involves adding an extra link field to each table position.

Answer:- Suppose some memory space becomes reusable because a node is released from a linked list. Hence, we want the space to be available for future use. One way to bring this about is to immediately reinsert the space into the free-storage list. However, this method may be too time-consuming for the operating system. The operating system may periodically collect all the deleted space onto the free-storage list. The technique that does this collection is called Garbage Collection. Garbage Collection usually takes place in two steps: First the Garbage Collector runs through all lists, tagging whose cells are currently in use, and then it runs through the memory, collecting all untagged space onto the free-storage list. The Garbage Collection may take place when there is only some minimum amount of space or no space at all left in the free-storage list, or when the CPU is idle and has time to do the collection. Generally speaking, the Garbage Collection is invisible to the programmer.

Answer:- The function difftime( ) finds the difference between two times. It calculates the elapsed time in seconds and returns the difference between two times as a double value.

 
      #include 
      #include 
      #include 
       
      main( )
      {
      int a[] = { 2, -34, 56, 78, 112, 33, -7, 11, 45, 29, 6 } ;
      int s ;
      time_t t1, t2 ;  // time_t defines the value used for time function
       
      s = sizeof ( a ) / 2 ;
      t1 = time ( NULL ) ;
      sel_sort ( a, s ) ; // sort array by selection sort
      bub_sort ( a, s ) ; // sort array by bubble sort method
      t2 = time ( NULL ) ;
      printf ( "\nThe difference between two function calls is %f", difftime ( 
      t2, t1 ) ) ;
      }
       

In the above program we have called difftime( ) function that returns the time elapsed from t1 to t2.

Answer:- This can achieved through the use of suppression char '*' in the format string of printf( ) which is shown in the following program.

     main( )
      {
      int  p  =  2 ;
      float  n  =  12.126487687 ;
      printf ( "%.*f",p, n ) ;
      }
      

Answer:- 'const char *p' and 'char const *p' are the same, i.e. p points to a constant character. On the other hand, 'char* const p' means p is a constant pointer pointing to a character which means we cannot change the pointer p but we can change the character which p is pointing to.

Answer:- A null pointer is a pointer which doesn't point anywhere. A NULL macro is used to represent the null pointer in source code. It has a value 0 associated with it. The ASCII NUL character has all its bits as 0 but doesn't have any relationship with the null pointer. The null string is just another name for an empty string "". System Utility