Loading....
Coupon Accepted Successfully!

 

Question 21

Write C code to implement the Binary Search algorithm.


Here is a C function


int binarySearch(int arr[],int size, int item)
{
   int left, right, middle;
   left  = 0;
   right = size-1;

   while(left<=right)
   {
      middle = ((left + right)/2);

      if(item == arr[middle])
      {
        return(middle);
      }
      
      if(item > arr[middle])
      {
        left  = middle+1;
      }
      else
      {
        right = middle-1;
      }
   }

   return(-1);
}




Note that the Binary Search algorithm has a prerequisite that the array passed to it must be already sorted in ascending order. This will not work on an unsorted array. The complexity of this algorithm is O(log(n)).


Question 22

Wite code to evaluate a polynomial.



typedef struct node
{
  float cf;
  float px;
  float py;
  struct node *next;
}mynode;



float evaluate(mynode *head)
{
   float x,y,sum;
   sum = 0;
   mynode *poly;

   for(poly = head->next; poly != head; poly = poly->next)
   {
     sum = sum + poly->cf * pow(x, poly->px) * pow(y, poly->py);
   }

   return(sum);
}



Question 23

Write a C program to reverse a string


There are a number of ways one can reverse strings. Here are a few of them. These should be enough to impress the interviewer! The methods span from recursive to non-recursive (iterative).

Also note that there is a similar question about reversing the words in a sentence, but still keeping the words in place. That is


I am a good boy


would become


boy good a am I


This is dealt with in another question. Here I only concentrate on reversing strings. That is


I am a good boy


would become


yob doog a ma I



Here are some sample C programs to do the same


Method1 (Recursive)


#include 

static char str[]="STRING TO REVERSE";

int main(int argc, char *argv)
{
   printf("\nOriginal string : [%s]", str);

   // Call the recursion function
   reverse(0);

   printf("\nReversed string : [%s]", str);
   return(0);
}

int reverse(int pos)
{
   // Here I am calculating strlen(str) everytime. 
   // This can be avoided by doing this computation
   // earlier and storing it somewhere for later use.

   if(pos<(strlen(str)/2))
   {
      char ch;

      // Swap str[pos] and str[strlen(str)-pos-1]
      ch = str[pos];
      str[pos]=str[strlen(str)-pos-1];
      str[strlen(str)-pos-1]=ch;
       
      // Now recurse!
      reverse(pos+1);
   }
}






Method2


#include  
#include  
#include  

void ReverseStr ( char *buff, int start, int end ) 

   char tmp ; 

   if ( start >= end ) 
   { 
      printf ( "\n%s\n", buff ); 
      return; 
   } 

   tmp = *(buff + start); 
   *(buff + start) = *(buff + end); 
   *(buff + end) = tmp ; 

   ReverseStr (buff, ++start, --end ); 



int main() 

   char buffer[]="This is Test"; 
   ReverseStr(buffer,0,strlen(buffer)-1); 
   return 0; 
}





Method3


public static String reverse(String s) 
{    
    int N = s.length();    
    if (N <= 1) return s;    
    String left = s.substring(0, N/2);    
    String right = s.substring(N/2, N);    
    return reverse(right) + reverse(left);
}






Method4

for(int i = 0, j = reversed.Length - 1; i  { 
    char temp = reversed[i]; 
    reversed[i] = reversed[j]; 
    reversed[j] = temp; 

return new String(reversed); 






Method5


public static String reverse(String s) 
{   
   int N = s.length();   
   String reverse = "";   
   for (int i = 0; i          reverse = s.charAt(i) + reverse;   
   return reverse;
}






Method6

public static String reverse(String s) 
{    
   int N = s.length();    
   char[] a = new char[N];    
   for (int i = 0; i         a[i] = s.charAt(N-i-1);    
   String reverse = new String(a);    
   return reverse;
}






Isn't that enough?


Question 24

Write code to add two polynomials


Here is some pseudocode


mynode *polynomial_add(mynode *h1, mynode *h2, mynode *h3)
{
   mynode *p1, *p2;
   int x1, x2, y1, y2, cf1, cf2, cf;

   p1 = h1->next;
  
   while(p1!=h1)
   {
      x1  = p1->px;
      y1  = p1->py;
      cf1 = p1->cf;

      // Search for this term in the second polynomial
  
      p2 = h2->next;
   
      while(p2 != h2)
      {
         x2  = p2->px;
         y2  = p2->py;
         cf2 = p2->cf;
    
         if(x1 == x2 && y1 == y2)break;

         p2 = p2->next;

      }


      if(p2 != h2)
      {
          // We found something in the second polynomial.
          
          cf = cf1 + cf2;
          p2->flag = 1;
 
          if(cf!=0){h3=addNode(cf,x1,y1,h3);}
      }
      else
      {
         h3=addNode(cf,x1,y1,h3);
      }

      p1 = p1->next;

   }//while


   // Add the remaining elements of the second polynomail to the result

   while(p2 != h2)
   {
      if(p2->flag==0)
      {
          h3=addNode(p2->cf, p2->px, p2->py, h3);
      }
      p2=p2->next;
   }

   return(h3);
}



Question 25

Write a program to add two long positive numbers (each represented by linked lists).


Check out this simple implementation


mynode *long_add(mynode *h1, mynode *h2, mynode *h3)
{
  mynode *c, *c1, *c2;
  int sum, carry, digit;
 
  carry = 0;
  c1 = h1->next;
  c2 = h2->next;
  
  while(c1 != h1 && c2 != h2)
  {
     sum   = c1->value + c2->value + carry;
     digit = sum % 10;
     carry = sum / 10;

     h3 = insertNode(digit, h3);
  
     c1 = c1->next;
     c2 = c2->next;
  }

  if(c1 != h1)
  {
     c = c1;
     h = h1;
  }
  else
  {
     c = c2; 
     h = h2;
  }

  while(c != h)
  {
    sum   = c->value + carry;
    digit = sum % 10;
    carry = sum / 10;
    h3 = insertNode(digit, h3);
    c = c->next;
  }

  if(carry==1)
  {
     h3 = insertNode(carry, h3);
  }

  return(h3);
}



Question 26

How do you compare floating point numbers?


This is Wrong!.


double a, b;

if(a == b)
{
  ...
}




The above code might not work always. Thats because of the way floating point numbers are stored.

A good way of comparing two floating point numbers is to have a accuracy threshold which is relative to the magnitude of the two floating point numbers being compared.


#include 
if(fabs(a - b) <= accurary_threshold * fabs(a))



There is a lot of material on the net to know how floating point numbers can be compared. Got for it if you really want to understand.



Another way which might work is something like this. I have not tested it!



int compareFloats(float f1, float f2)
{
  char *b1, *b2; 
  int i; 

  b1 = (char *)&f1; 
  b2 = (char *)&f2; 

  /* Assuming sizeof(float) is 4 bytes) */ 

  for (i = 0; i<4; i++, b1++, b2++) 
  {
    if (*b1 != *b2) 
    {
      return(NOT_EQUAL); /* You must have defined this before */ 
    }
  }

  return(EQUAL);
}



Question 27

What's a good way to implement complex numbers in C?


Use structures and some routines to manipulate them.


Question 28

How can I display a percentage-done indication on the screen?


The character '\r' is a carriage return without the usual line feed, this helps to overwrite the current line. The character '\b' acts as a backspace, and will move the cursor one position to the left.


Question 29

Write a program to check if a given year is a leap year or not?


Use this if() condition to check if a year is a leap year or not


if(year % 4 == 0 && (year % 100 != 0 || year % 400 == 0))



Question 30

Is there something we can do in C but not in C++?


I have a really funny answer

Declare variable names that are keywords in C++ but not C.


#include 
int main(void)
{
  int old, new=3;
  return 0;
}



This will compile in C, but not in C++!






Test Your Skills Now!
Take a Quiz now
Reviewer Name