Loading....
Coupon Accepted Successfully!

 

Question 1

Write your own C program to implement the atoi() function


The prototype of the atoi() function is ...


int atoi(const char *string);



Here is a C program which explains a different way of coding the atoi() function in the C language.


#include

int myatoi(const char *string);

int main(int argc, char* argv[])
{
  printf("\n%d\n", myatoi("1998")); 
  getch();
  return(0);
}

int myatoi(const char *string)
{
    int i;
    i=0;
    while(*string)
    {
        i=(i<<3) + (i<<1) + (*string - '0');
        string++;

        // Dont increment i!

    }
    return(i);
}



Try working it out with a small string like "1998", you will find out it does work!.




Ofcourse, there is also the trivial method ....


"1998" == 8 + (10 * 9) + (100 * 9) + (1 * 1000) = 1998 



This can be done either by going from right to left or left to right in the string

One solution is given below



int myatoi(const char* string) 
{
  int value = 0; 
 
  if (string)
  {
    while (*string && (*string <= '9' && *string >= '0')) 
    {
      value = (value * 10) + (*string - '0');
      string++;
    }
  } 
  return value; 





Note that these functions have no error handling incorporated in them (what happens if someone passes non-numeric data (say "1A998"), or negative numeric strings (say "-1998")). I leave it up to you to add these cases. The essense is to understand the core logic first.


Question 2

Implement the memmove() function. What is the difference between the memmove() and memcpy() function?


One more most frequently asked interview question!.

memmove() offers guaranteed behavior if the source and destination arguments overlap. memcpy() makes no such guarantee, and may therefore be more efficient to implement. It's always safer to use memmove().

Note that the prototype of memmove() is ...


void *memmove(void *dest, const void *src, size_t count);



Here is an implementation..



#include 
#include 

void *mymemmove(void *dest, const void *src, size_t count);

int main(int argc, char* argv[])
{
  char *p1, *p2;
  char *p3, *p4;
  int  size;
  
  printf("\n--------------------------------\n");
  
  /* ----------------------------------------
   * 
   * CASE 1 : From (SRC)     *
   *     +--+---------------------+--+
   *     |  |                     |  |
   *     +--+---------------------+--+
   *     ^  ^
   *     |  |
   *   From To
   *
   * --------------------------------------- */
 
  p1 = (char *) malloc(12);
  memset(p1,12,'\0');
  size=10;

  strcpy(p1,"ABCDEFGHI");
  
  p2 = p1 + 2;

  printf("\n--------------------------------\n");
  printf("\nFrom (before) = [%s]",p1);
  printf("\nTo (before)   = [%s]",p2);

  mymemmove(p2,p1,size);

  printf("\n\nFrom (after) = [%s]",p1);
  printf("\nTo (after)   = [%s]",p2);

  printf("\n--------------------------------\n");



  /* ----------------------------------------
   * 
   * CASE 2 : From (SRC) > To (DEST) 
   *
   *     +--+---------------------+--+
   *     |  |                     |  |
   *     +--+---------------------+--+
   *     ^  ^
   *     |  |
   *    To From
   *
   * --------------------------------------- */


  p3 = (char *) malloc(12);
  memset(p3,12,'\0');
  p4 = p3 + 2;

  strcpy(p4, "ABCDEFGHI");

  printf("\nFrom (before) = [%s]",p4);
  printf("\nTo (before)   = [%s]",p3);

  mymemmove(p3, p4, size);

  printf("\n\nFrom (after) = [%s]",p4);
  printf("\nTo (after)   = [%s]",p3);

  printf("\n--------------------------------\n");


  /* ----------------------------------------
   * 
   * CASE 3 : No overlap
   *
   * --------------------------------------- */
 
  p1 = (char *) malloc(30);
  memset(p1,30,'\0');
  size=10;

  strcpy(p1,"ABCDEFGHI");
  
  p2 = p1 + 15;

  printf("\n--------------------------------\n");
  printf("\nFrom (before) = [%s]",p1);
  printf("\nTo (before)   = [%s]",p2);

  mymemmove(p2,p1,size);

  printf("\n\nFrom (after) = [%s]",p1);
  printf("\nTo (after)   = [%s]",p2);

  printf("\n--------------------------------\n");

  printf("\n\n");
  
  return 0;
}



void *mymemmove(void *to, const void *from, size_t size)
{
    unsigned char *p1;      
    const unsigned char *p2;

    p1 = (unsigned char *) to;
    p2 = (const unsigned char *) from;

    p2 = p2 + size;

    // Check if there is an overlap or not.
    while (p2 != from && --p2 != to);


    if (p2 != from) 
    {
        // Overlap detected!

        p2  = (const unsigned char *) from;
        p2  = p2 + size;
        p1  = p1 + size;

        while (size-- != 0) 
        {
            *--p1 = *--p2;
        } 
    } 
    else 
    {
        // No overlap OR they overlap as CASE 2 above.
        // memcopy() would have done this directly.
 
        while (size-- != 0) 
        {
            *p1++ = *p2++;
        }
    }

    return(to);
}






And here is the output


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

From (before) = [ABCDEFGHI]
To   (before) = [CDEFGHI]


From (after) = [ABABCDEFGHI]
To   (after) = [ABCDEFGHI]

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

From (before) = [ABCDEFGHI]
To   (before) = [α╙ABCDEFGHI]


From (after) = [CDEFGHI]
To   (after) = [ABCDEFGHI]

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

From (before) = [ABCDEFGHI]
To   (before) = [FEδ‼&:F]


From (after) = [ABCDEFGHI]
To (after)   = [ABCDEFGHI]

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




So then, whats the difference between the implementation of memmove() and memcpy(). Its just that memcpy() will not care if the memories overlap and will either copy from left to right or right to left without checking which method to used depending on the type of the overlap. Also note that the C code proves that the results are the same irrespective of the Endian-ness of the machine.



**


Question 3

Write a C program to implement the strlen() function


The prototype of the strlen() function is...


size_t strlen(const char *string);


Here is some C code which implements the strlen() function....


int my_strlen(char *string)
{
  int length;
  for (length = 0; *string != '\0', string++)
  {
    length++;
  }
  return(length);
}





Also, see another example


int my_strlen(char *s)
{
  char *p=s;

  while(*p!='\0')
    p++;

  return(p-s);
}



Question 4

Write C code to implement the strstr() (search for a substring) function.


This is also one of the most frequently asked interview questions. Its asked almost 99% of the times. Here are a few C programs to implement your own strstr() function.

There are a number of ways to find a string inside another string. Its important to be aware of these algorithms than to memorize them. Some of the fastest algorithms are quite tough to understand!.


Method1

The first method is the classic Brute force method. The Brute Force algorithm checks, at all positions in the text between 0 and (n-m), if an occurrence of the pattern starts at that position or not. Then, after each successfull or unsuccessful attempt, it shifts the pattern exactly one position to the right. The time complexity of this searching phase is O(mn). The expected number of text character comparisons is 2n.

Here 'n' is the size of the string in which the substring of size 'm' is being searched for.

Here is some code (which works!)



#include

void BruteForce(char *x /* pattern */, 
                int m   /* length of the pattern */, 
                char *y /* actual string being searched */, 
                int n   /* length of this string */)
{
   int i, j;
   printf("\nstring    : [%s]"
          "\nlength    : [%d]"
          "\npattern   : [%s]"
          "\nlength    : [%d]\n\n", y,n,x,m);


   /* Searching */
   for (j = 0; j <= (n - m); ++j)
   {
      for (i = 0; i          if (i >= m) {printf("\nMatch found at\n\n->[%d]\n->[%s]\n",j,y+j);}
   }
}


int main()
{
  char *string  = "hereroheroero";
  char *pattern = "hero";

  BF(pattern,strlen(pattern),string,strlen(string));
  printf("\n\n");
  return(0);
}





This is how the comparison happens visually


hereroheroero
   !
hero


hereroheroero
 !
 hero


hereroheroero
  !
  hero


hereroheroero
   !
   hero


hereroheroero
    !
    hero


hereroheroero
     !
     hero


hereroheroero
      |||| ----> Match!
      hero


hereroheroero
       !
       hero


hereroheroero
        ! 
        hero


hereroheroero
         !
         hero

         






Method2

The second method is called the Rabin-Karp method.

Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string "window" looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used. Hashing a string involves computing a numerical value from the value of its characters using a hash function.

The Rabin-Karp method uses the rule that if two strings are equal, their hash values must also be equal. Note that the converse of this statement is not always true, but a good hash function tries to reduce the number of such hash collisions. Rabin-Karp computes hash value of the pattern, and then goes through the string computing hash values of all of its substrings and checking if the pattern's hash value is equal to the substring hash value, and advancing by 1 character every time. If the two hash values are the same, then the algorithm verifies if the two string really are equal, rather than this being a fluke of the hashing scheme. It uses regular string comparison for this final check. Rabin-Karp is an algorithm of choice for multiple pattern search. If we want to find any of a large number, say k, fixed length patterns in a text, a variant Rabin-Karp that uses a hash table to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for. Other algorithms can search for a single pattern in time order O(n), hence they will search for k patterns in time order O(n*k). The variant Rabin-Karp will still work in time order O(n) in the best and average case because a hash table allows to check whether or not substring hash equals any of the pattern hashes in time order of O(1).

Here is some code (not working though!)


#include

hashing_function()
{
  // A hashing function to compute the hash values of the strings.
  ....
}

void KarpRabinR(char *x, int m, char *y, int n) 
{
   int hx, hy, i, j;

   printf("\nstring    : [%s]"
          "\nlength    : [%d]"
          "\npattern   : [%s]"
          "\nlength    : [%d]\n\n", y,n,x,m);


   /* Preprocessing  phase */
   Do preprocessing here..

   /* Searching */
   j = 0;
   while (j <= n-m) 
   {
      if (hx == hy && memcmp(x, y + j, m) == 0)
      {
         // Hashes match and so do the actual strings!
         printf("\nMatch found at : [%d]\n",j);
      }

      hy = hashing_function(y[j], y[j + m], hy);
      ++j;
   }
}


int main()
{

  char *string="hereroheroero";
  char *pattern="hero";

  KarpRabin(pattern,strlen(pattern),string,strlen(string));

  printf("\n\n");
  return(0);

}




This is how the comparison happens visually


hereroheroero
   !
hero


hereroheroero
 !
 hero


hereroheroero
  !
  hero


hereroheroero
   !
   hero


hereroheroero
    !
    hero


hereroheroero
     !
     hero


hereroheroero
      |||| ----> Hash values match, so do the strings!
      hero


hereroheroero
       !
       hero


hereroheroero
        ! 
        hero


hereroheroero
         !
         hero

         




Method3

The Knuth-Morris-Pratt or the Morris-Pratt algorithms are extensions of the basic Brute Force algorithm. They use precomputed data to skip forward not by 1 character, but by as many as possible for the search to succeed.

Here is some code


void preComputeData(char *x, int m, int Next[]) 
{
   int i, j;
   i = 0;
   j = Next[0] = -1;

   while (i     {
      while (j > -1 && x[i] != x[j])
         j = Next[j];
      Next[++i] = ++j;

   }
}


void MorrisPrat(char *x, int m, char *y, int n) 
{
   int i, j, Next[1000];

   /* Preprocessing */
   preComputeData(x, m, Next);

   /* Searching */
   i = j = 0;
   while (j     {
      while (i > -1 && x[i] != y[j])
         i = Next[i];
      i++;
      j++;
      if (i >= m) 
      {
         printf("\nMatch found at : [%d]\n",j - i);
         i = Next[i];
      }
   }
}


int main()
{
  char *string="hereroheroero";
  char *pattern="hero";

  MorrisPrat(pattern,strlen(pattern),string,strlen(string));

  printf("\n\n");
  return(0);
}




This is how the comparison happens visually


hereroheroero
   !
hero


hereroheroero
   !
   hero


hereroheroero
    !
    hero


hereroheroero
     !
     hero



hereroheroero
      |||| ----> Match found!
      hero


hereroheroero
          !
          hero





Method4

The Boyer Moore algorithm is the fastest string searching algorithm. Most editors use this algorithm.

It compares the pattern with the actual string from right to left. Most other algorithms compare from left to right. If the character that is compared with the rightmost pattern symbol does not occur in the pattern at all, then the pattern can be shifted by m positions behind this text symbol.


The following example illustrates this situation.

Example:


0 1 2 3 4 5 6 7 8 9 ... 
a b b a d a b a c b a  
        | |
b a b a c |       
  <------ |
          |
          b a b a c  



The comparison of "d" with "c" at position 4 does not match. "d" does not occur in the pattern. Therefore, the pattern cannot match at any of the positions 0,1,2,3,4, since all corresponding windows contain a "d". The pattern can be shifted to position 5. The best case for the Boyer-Moore algorithm happens if, at each search attempt the first compared character does not occur in the pattern. Then the algorithm requires only O(n/m) comparisons .

Bad character heuristics

This method is called bad character heuristics. It can also be applied if the bad character (the character that causes a mismatch), occurs somewhere else in the pattern. Then the pattern can be shifted so that it is aligned to this text symbol. The next example illustrates this situation.


Example:


0 1 2 3 4 5 6 7 8 9 ... 
a b b a b a b a c b a 
        | 
b a b a c  
    <----
    |      
    b a b a c     




Comparison between "b" and "c" causes a mismatch. The character "b" occurs in the pattern at positions 0 and 2. The pattern can be shifted so that the rightmost "b" in the pattern is aligned to "b".


Good suffix heuristics

Sometimes the bad character heuristics fails. In the following situation the comparison between "a" and "b" causes a mismatch. An alignment of the rightmost occurence of the pattern symbol a with the text symbol a would produce a negative shift. Instead, a shift by 1 would be possible. However, in this case it is better to derive the maximum possible shift distance from the structure of the pattern. This method is called good suffix heuristics.

Example:


0 1 2 3 4 5 6 7 8 9 ... 
a b a a b a b a c b a  
    | | |
c a b a b
    <----
    | | |        
    c a b a b     



The suffix "ab" has matched. The pattern can be shifted until the next occurence of ab in the pattern is aligned to the text symbols ab, i.e. to position 2.


In the following situation the suffix "ab" has matched. There is no other occurence of "ab" in the pattern.Therefore, the pattern can be shifted behind "ab", i.e. to position 5.

Example:


0 1 2 3 4 5 6 7 8 9 ... 
a b c a b a b a c b a  
    | | |
c b a a b        
          c b a a b  




In the following situation the suffix "bab" has matched. There is no other occurence of "bab" in the pattern. But in this case the pattern cannot be shifted to position 5 as before, but only to position 3, since a prefix of the pattern "ab" matches the end of "bab". We refer to this situation as case 2 of the good suffix heuristics.

Example:


0 1 2 3 4 5 6 7 8 9 ... 
a a b a b a b a c b a  
  | | | |
a b b a b        
      a b b a b    




The pattern is shifted by the longest of the two distances that are given by the bad character and the good suffix heuristics.

The Boyer-Moore algorithm uses two different heuristics for determining the maximum possible shift distance in case of a mismatch: the "bad character" and the "good suffix" heuristics. Both heuristics can lead to a shift distance of m. For the bad character heuristics this is the case, if the first comparison causes a mismatch and the corresponding text symbol does not occur in the pattern at all. For the good suffix heuristics this is the case, if only the first comparison was a match, but that symbol does not occur elsewhere in the pattern.


A lot of these algorithms have been explained here with good visualizations. Remember, again that its sufficient to know the basic Brute force algorithm and be aware of the other methods. No one expects you to know every possible algorithm on earth.


Question 5

Write your own printf() function in C


This is again one of the most frequently asked interview questions. Here is a C program which implements a basic version of printf(). This is a really, really simplified version of printf(). Note carefully how floating point and other compilcated support has been left out. Also, note how we use low level puts() and putchar(). Dont make a fool of yourself by using printf() within the implementation of printf()!


#include
#include

main()
{
    void myprintf(char *,...);
    char * convert(unsigned int, int);
    int i=65;
    char str[]="This is my string";
    myprintf("\nMessage = %s%d%x",str,i,i);
}

void myprintf(char * frmt,...)
{

    char *p;
    int i;
    unsigned u;
    char *s;
    va_list argp;


    va_start(argp, fmt);

    p=fmt;
    for(p=fmt; *p!='\0';p++)
    {
        if(*p=='%')
        {
            putchar(*p);continue;
        }

        p++;

        switch(*p)
        {
            case 'c' : i=va_arg(argp,int);putchar(i);break;
            case 'd' : i=va_arg(argp,int);
                            if(i<0){i=-i;putchar('-');}puts(convert(i,10));break;
            case 'o': i=va_arg(argp,unsigned int); puts(convert(i,8));break;
            case 's': s=va_arg(argp,char *); puts(s); break;
            case 'u': u=va_arg(argp,argp, unsigned int); puts(convert(u,10));break;
            case 'x': u=va_arg(argp,argp, unsigned int); puts(convert(u,16));break;
            case '%': putchar('%');break;
        }
    }

    va_end(argp);
}

char *convert(unsigned int, int)
{
    static char buf[33];
    char *ptr;
    
    ptr=&buf[sizeof(buff)-1];
    *ptr='\0';
    do
    {
        *--ptr="0123456789abcdef"[num%base];
        num/=base;
    }while(num!=0);
    return(ptr);
}



Question 6

Implement the strcpy() function.


Here are some C programs which implement the strcpy() function. This is one of the most frequently asked C interview questions.


Method1


char *mystrcpy(char *dst, const char *src)
{
  char *ptr;
  ptr = dst;
  while(*dst++=*src++);
  return(ptr);
}



The strcpy function copies src, including the terminating null character, to the location specified by dst. No overflow checking is performed when strings are copied or appended. The behavior of strcpy is undefined if the source and destination strings overlap. It returns the destination string. No return value is reserved to indicate an error.

Note that the prototype of strcpy as per the C standards is


char *strcpy(char *dst, const char *src);


Notice the const for the source, which signifies that the function must not change the source string in anyway!.

Method2


char *my_strcpy(char dest[], const char source[])
{
  int i = 0;
  while (source[i] != '\0')
  {
    dest[i] = source[i];
    i++;
  }
  dest[i] = '\0';
  return(dest);
}



Simple, isn't it?


Question 7

Implement the strcmp(str1, str2) function.


There are many ways one can implement the strcmp() function. Note that strcmp(str1,str2) returns a -ve number if str1 is alphabetically above str2, 0 if both are equal and +ve if str2 is alphabetically above str1.

Here are some C programs which implement the strcmp() function. This is also one of the most frequently asked interview questions. The prototype of strcmp() is


int strcmp( const char *string1, const char *string2 );



Here is some C code..


#include 

int mystrcmp(const char *s1, const char *s2);

int main()
{
  printf("\nstrcmp() = [%d]\n", mystrcmp("A","A"));
  printf("\nstrcmp() = [%d]\n", mystrcmp("A","B"));
  printf("\nstrcmp() = [%d]\n", mystrcmp("B","A"));
  return(0);
}

int mystrcmp(const char *s1, const char *s2)
{
    while (*s1==*s2)
    {
        if(*s1=='\0')
           return(0);
        s1++;
        s2++;
    }
    return(*s1-*s2);
}



And here is the output...


strcmp() = [0]
strcmp() = [-1]
strcmp() = [1]



Question 8

Implement the substr() function in C.


Here is a C program which implements the substr() function in C.


int main()
{
  char str1[] = "India";
  char str2[25];

  substr(str2, str1, 1, 3);
  printf("\nstr2 : [%s]", str2);
  return(0);
}

substr(char *dest, char *src, int position, int length)
{
    dest[0]='\0';
    strncat(dest, (src + position), length);
}



Question 9

Write your own copy() function


Here is some C code that simulates a file copy action.



#include               /* standard I/O routines. */
#define MAX_LINE_LEN 1000 /* maximum line length supported. */


void main(int argc, char* argv[])
{
    char* file_path_from;
    char* file_path_to;
    FILE* f_from;
    FILE* f_to;
    char buf[MAX_LINE_LEN+1];

    file_path_from = "";
    file_path_to   = "";

    f_from = fopen(file_path_from, "r");
    if (!f_from) {exit(1);}

    f_to = fopen(file_path_to, "w+");
    if (!f_to) {exit(1);}

    /* Copy source to target, line by line. */
    while (fgets(buf, MAX_LINE_LEN+1, f_from)) 
    {
        if (fputs(buf, f_to) == EOF){exit(1);}
    }

    if (!feof(f_from)){exit(1);}

    if (fclose(f_from) == EOF) {exit(1);}
    if (fclose(f_to) == EOF)   {exit(1);}
     
    return(0);
}




Question 10

Write C programs to implement the toupper() and the isupper() functions


toUpper()


int toUpper(int ch)
{
    if(ch>='a' && c<='z')
        return('A' + ch - 'a');
    else
        return(ch);
}




isUpper()


int isUpper(int ch)
{
    if(ch>='A' && ch <='Z')
       return(1); //Yes, its upper!
    else 
       return(0); // No, its lower!





Its important to know that the upper and lower case alphabets have corresponding integer values.


A-Z - 65-90
a-z - 97-122






Another way to do this conversion is to maintain a correspondance between the upper and lower case alphabets. The program below does that. This frees us from the fact that these alphabets have a corresponding integer values. I dont know what one should do for non-english alphabets. Do other languages have upper and lower case letters in the first place :) !



#include 

#define UPPER   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER   "abcdefghijklmnopqrstuvwxyz"

int toUpper(int c) 
{
    const char *upper;
    const char *const lower = LOWER;
        
    // Get the position of the lower case alphabet in the LOWER string using the strchr() function ..
    upper = ( ((CHAR_MAX >= c)&&(c > '\0')) ? strchr(lower, c) : NULL);

   
    // Now return the corresponding alphabet at that position in the UPPER string ..
    return((upper != NULL)?UPPER[upper - lower] : c);
}





Note that these routines dont have much error handling incorporated in them. Its really easy to add error handling to these routines or just leave it out (as I like it). This site consciously leaves out error handling for most of the programs to prevent unwanted clutter and present the core logic first.


**



{C}




Test Your Skills Now!
Take a Quiz now
Reviewer Name