#include <stdio.

h>

int reverse_digits ( int number, int* digits )

{
int n_digits = 0;
int rev_number = 0;

while ( number ) {
rev_number *= 10;
rev_number += number % 10;
number /= 10;
n_digits++;
}

*( digits ) = n_digits;
return ( rev_number );
}

int palindrome ( int number, int digits )

{
int flag = 1;

while ( number ) {
if ( ( number % 10 ) != ( number / (int)
pow ( 10, digits - 1 ) ) && ( digits > 1 ) ) {
flag = 0;
break;
}

// removing first and last digits

if ( 1 < ( digits -= 2 ) ) {
number /= 10;
number = number % (int) pow ( 10,
digits );
} else break;
}

return ( flag );
}

int main ( int argc, char* argv [] )

{
int number = 123;
int digits = 0;

int rev_number = 0;

rev_number = reverse_digits ( number, &digits );

if ( !palindrome ( number, digits ) ) {

printf ("\n NOT Palindrome, creating
Palindrome");
/**
* if you need 12321 use digits - 1
* if you need 123321 use digits
*/
number *= (int) pow ( 10, ( digits - 1 ) );
number += rev_number % (int) pow ( 10, (
digits - 1 ) );
}

printf ( "\n The Number: %d", number );

return ( 0 );
}
 

Write a C program to check for palindromes.

An example of a palidrome is "avon sees nova"

There a number of ways in which we can find out if a string is a palidrome or not. Here are a few sample C
programs...

Method1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

void isPalindrome(char *string);

int main()
{
isPalindrome("avon sees nova");
isPalindrome("a");
isPalindrome("avon sies nova");
isPalindrome("aa");
isPalindrome("abc");
isPalindrome("aba");
isPalindrome("3a2");
exit(0);
}

void isPalindrome(char *string)

{
char *start, *end;

if(string)
{
start = string;
end = string + strlen(string) - 1;
while((*start == *end) && (start!=end))
{
if(start<end)start++;
if(end>start)end--;
}

if(*start!=*end)
{
printf("\n[%s] - This is not a palidrome!\n", string);
}
else
{
printf("\n[%s] - This is a palidrome!\n", string);
}
}
printf("\n\n");
}

Method2

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int isPalindrome(char string[]);

int main()
{
isPalindrome("avon sees nova");
isPalindrome("a");
isPalindrome("avon sies nova");
isPalindrome("aa");
isPalindrome("abc");
isPalindrome("aba");
isPalindrome("3a2");
return(0);
}

int isPalindrome(char string[])

{
int count, countback, end, N;

N = strlen(string);
end = N-1;

for((count=0, countback = end); count <= (end/2); ++count,--countback)

{
if(string[count]!=string[countback])
{
return(1);
}
}

printf("\n[%s] is a palidrome!\n", string);

return(0);
}
 

Write a C program to implement a Generic Linked List.

Here is a C program which implements a generic linked list. This is also one of the very popular interview questions
thrown around. The crux of the solution is to use the void C pointer to make it generic. Also notice how we use
function pointers to pass the address of different functions to print the different generic data.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct list {

void *data;
struct list *next;
} List;

struct check {
int i;
char c;
double d;
} chk[] = { { 1, 'a', 1.1 },
{ 2, 'b', 2.2 },
{ 3, 'c', 3.3 } };

void insert(List **, void *, unsigned int);

void print(List *, void (*)(void *));
void printstr(void *);
void printint(void *);
void printchar(void *);
void printcomp(void *);

List *list1, *list2, *list3, *list4;

int main(void)
{
char c[] = { 'a', 'b', 'c', 'd' };
int i[] = { 1, 2, 3, 4 };
char *str[] = { "hello1", "hello2", "hello3", "hello4" };

list1 = list2 = list3 = list4 = NULL;

insert(&list1, &c[0], sizeof(char));

insert(&list1, &c[1], sizeof(char));
insert(&list1, &c[2], sizeof(char));
insert(&list1, &c[3], sizeof(char));

insert(&list2, &i[0], sizeof(int));

insert(&list2, &i[1], sizeof(int));
insert(&list2, &i[2], sizeof(int));
insert(&list2, &i[3], sizeof(int));

insert(&list3, str[0], strlen(str[0])+1);

insert(&list3, str[1], strlen(str[0])+1);
insert(&list3, str[2], strlen(str[0])+1);
insert(&list3, str[3], strlen(str[0])+1);

insert(&list4, &chk[0], sizeof chk[0]);

insert(&list4, &chk[1], sizeof chk[1]);
insert(&list4, &chk[2], sizeof chk[2]);

printf("Printing characters:");
print(list1, printchar);
printf(" : done\n\n");

printf("Printing integers:");
print(list2, printint);
printf(" : done\n\n");

printf("Printing strings:");
print(list3, printstr);
printf(" : done\n\n");

printf("Printing composite:");
print(list4, printcomp);
printf(" : done\n");

return 0;
}

void insert(List **p, void *data, unsigned int n)

{
List *temp;
int i;

/* Error check is ignored */

temp = malloc(sizeof(List));
temp->data = malloc(n);
for (i = 0; i < n; i++)
*(char *)(temp->data + i) = *(char *)(data + i);
temp->next = *p;
*p = temp;
}

void print(List *p, void (*f)(void *))

{
while (p)
{
(*f)(p->data);
p = p->next;
}
}

void printstr(void *str)

{
printf(" \"%s\"", (char *)str);
}

void printint(void *n)

{
printf(" %d", *(int *)n);
}

void printchar(void *c)

{
printf(" %c", *(char *)c);
}

void printcomp(void *comp)

{
struct check temp = *(struct check *)comp;
printf(" '%d:%c:%f", temp.i, temp.c, temp.d);
}
 

How do you reverse a linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new
linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you
would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but
you are not changing them when reversing the linked list).
 

How do you reverse a singly linked list? How do you reverse a doubly linked
list? Write a C program to do the same.

This is THE most frequently asked interview question. The most!.

Singly linked lists

Here are a few C programs to reverse a singly linked list.

Method1 (Iterative)

#include <stdio.h>

// Variables
typedef struct node
{
int value;
struct node *next;
}mynode;

// Globals (not required, though).

mynode *head, *tail, *temp;

// Functions
void add(int value);
void iterative_reverse();
void print_list();

// The main() function

int main()
{
head=(mynode *)0;

// Construct the linked list.

add(1);
add(2);
add(3);

//Print it
print_list();

// Reverse it.
iterative_reverse();

//Print it again
print_list();

return(0);
}

// The reverse function

void iterative_reverse()
{
mynode *p, *q, *r;

if(head == (mynode *)0)

{
return;
}
p = head;
q = p->next;
p->next = (mynode *)0;

while (q != (mynode *)0)

{
r = q->next;
q->next = p;
p = q;
q = r;
}

head = p;
}

// Function to add new nodes to the linked list

void add(int value)
{
temp = (mynode *) malloc(sizeof(struct node));
temp->next=(mynode *)0;
temp->value=value;

if(head==(mynode *)0)
{
head=temp;
tail=temp;
}
else
{
tail->next=temp;
tail=temp;
}
}

// Function to print the linked list.

void print_list()
{
printf("\n\n");
for(temp=head; temp!=(mynode *)0; temp=temp->next)
{
printf("[%d]->",(temp->value));
}
printf("[NULL]\n\n");
}

Method2 (Recursive, without using any temporary variable)

#include <stdio.h>

// Variables
typedef struct node
{
int value;
struct node *next;
}mynode;

// Globals.
mynode *head, *tail, *temp;

// Functions
void add(int value);
mynode* reverse_recurse(mynode *root);
void print_list();

// The main() function

int main()
{
head=(mynode *)0;

// Construct the linked list.

add(1);
add(2);
add(3);

//Print it
print_list();

// Reverse it.
if(head != (mynode *)0)
{
temp = reverse_recurse(head);
temp->next = (mynode *)0;
}

//Print it again
print_list();

return(0);
}

// Reverse the linked list recursively

//

// This function uses the power of the stack to make this

// *magical* assignment
//
// node->next->next=node;
//
// :)

mynode* reverse_recurse(mynode *root)

{
if(root->next!=(mynode *)0)
{
reverse_recurse(root->next);
root->next->next=root;
return(root);
}
else
{
head=root;
}
}

// Function to add new nodes to the linked list.

void add(int value)
{
temp = (mynode *) malloc(sizeof(struct node));
temp->next=(mynode *)0;
temp->value=value;

if(head==(mynode *)0)
{
head=temp;
tail=temp;
}
else
{
tail->next=temp;
tail=temp;
}
}

// Function to print the linked list.

void print_list()
{
printf("\n\n");
for(temp=head; temp!=(mynode *)0; temp=temp->next)
{
printf("[%d]->",(temp->value));
}
printf("[NULL]\n\n");
}
Method3 (Recursive, but without ANY global variables. Slightly messy!)

#include <stdio.h>

// Variables
typedef struct node
{
int value;
struct node *next;
}mynode;

// Functions
void add(mynode **head, mynode **tail, int value);
mynode* reverse_recurse(mynode *current, mynode *next);
void print_list(mynode *);

int main()
{
mynode *head, *tail;
head=(mynode *)0;

// Construct the linked list.

add(&head, &tail, 1);
add(&head, &tail, 2);
add(&head, &tail, 3);

//Print it
print_list(head);

// Reverse it.
head = reverse_recurse(head, (mynode *)0);

//Print it again
print_list(head);

getch();
return(0);
}

// Reverse the linked list recursively

mynode* reverse_recurse(mynode *current, mynode *next)
{
mynode *ret;

if(current==(mynode *)0)
{
return((mynode *)0);
}

ret = (mynode *)0;

if (current->next != (mynode *)0)
{
ret = reverse_recurse(current->next, current);
}
else
{
ret = current;
}

current->next = next;
return ret;
}

// Function to add new nodes to the linked list.

// Takes pointers to pointers to maintain the
// *actual* head and tail pointers (which are local to main()).

void add(mynode **head, mynode **tail, int value)

{
mynode *temp1, *temp2;

temp1 = (mynode *) malloc(sizeof(struct node));

temp1->next=(mynode *)0;
temp1->value=value;

if(*head==(mynode *)0)
{
*head=temp1;
*tail=temp1;
}
else
{
for(temp2 = *head; temp2->next!= (mynode *)0; temp2=temp2->next);
temp2->next = temp1;
*tail=temp1;
}
}

// Function to print the linked list.

void print_list(mynode *head)
{
mynode *temp;
printf("\n\n");
for(temp=head; temp!=(mynode *)0; temp=temp->next)
{
printf("[%d]->",(temp->value));
}
printf("[NULL]\n\n");
}

Doubly linked lists

This is really easy, just keep swapping the prev and next pointers and at the end swap the head and the tail:)

#include<stdio.h>
#include<ctype.h>

typedef struct node

{
int value;
struct node *next;
struct node *prev;
}mynode ;

mynode *head, *tail;

void add_node(int value);
void print_list();
void reverse();

int main()
{

head=NULL;
tail=NULL;

add_node(1);
add_node(2);
add_node(3);
add_node(4);
add_node(5);

print_list();

reverse();

print_list();

return(1);

void add_node(int value)

{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(head == NULL)
{

printf("\nAdding a head pointer\n");

head=temp;
tail=temp;
temp->value=value;

}
else
{

for(cur=head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
tail=temp;

void print_list()
{
mynode *temp;

printf("\n--------------------------------\n");
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("\n[%d]\n",temp->value);
}

void reverse()
{
mynode *cur, *temp, *save_next;
if(head==tail)return;
if(head==NULL || tail==NULL)return;
for(cur=head;cur!=NULL;)
{
printf("\ncur->value : [%d]\n",cur->value);
temp=cur->next;
save_next=cur->next;
cur->next=cur->prev;
cur->prev=temp;
cur=save_next;
}

temp=head;
head=tail;
tail=temp;
}
Having shown all these different methods, if someone can mail me a really, really good practical application of
reversing a linked list (singly or doubly linked list), I would be really thankful to them. I have not found one good
application of this. All I see is an urge to understand how well the candidate handles the pointer manipulation.
 

Given only a pointer to a node to be deleted in a singly linked list, how do

you delete it?

This is a very good interview question

The solution to this is to copy the data from the next node into this node and delete the next node!. Ofcourse this
wont work if the node to be deleted is the last node. Mark it as dummy in that case. If you have a Circular linked
list, then this might be all the more interesting. Try writing your own C program to solve this problem. Having a doubly
linked list is always better.
 

How do you sort a linked list? Write a C program to sort a linked list.

This is a very popular interview question, which most people go wrong. The ideal solution to this problem is to
keep the linked list sorted as you build it. Another question on this website teaches you how to insert elements into
a linked list in the sorted order. This really saves a lot of time which would have been required to sort it.

However, you need to Get That Job....

Method1 (Usual method)

The general idea is to decide upon a sorting algorithm (say bubble sort). Then, one needs to come up with different
scenarios to swap two nodes in the linked list when they are not in the required order. The different scenarios would
be something like

1. When the nodes being compared are not adjacent and one of them is the firs
t node.
2. When the nodes being compared are not adjacent and none of them is the fir
st node
3. When the nodes being compared are adjacent and one of them is the first no
de.
4. When the nodes being compared are adjacent and none of them is the first n
ode.

One example bubble sort for a linked list goes like this (working C code!)....
#include<stdio.h>
#include<ctype.h>

typedef struct node

{
int value;
struct node *next;
struct node *prev;
}mynode ;

void add_node(struct node **head, int *count, int value);

void print_list(char *listName, struct node *head);
mynode *bubbleSort(mynode *head, int count);

int main()
{
mynode *head;
int count = 0;

head = (struct node *)NULL;

add_node(&head, &count, 100);

add_node(&head, &count, 3);
add_node(&head, &count, 90);
add_node(&head, &count, 7);
add_node(&head, &count, 9);

print_list("myList(BEFORE)", head);
head = bubbleSort(head, count);
print_list("myList(AFTER) ", head);

getch();
return(0);

mynode *bubbleSort(mynode *head, int count)

{
int i, j;
mynode *p0, *p1, *p2, *p3;

for(i = 1; i < count; i++)

{
p0 = (struct node *)NULL;
p1 = head;
p2 = head->next;
p3 = p2->next;

for(j = 1; j <= (count - i); j++)

{
if(p1->value > p2->value)
{
// Adjust the pointers...
p1->next = p3;
p2->next = p1;
if(p0)p0->next=p2;

// Set the head pointer if it was changed...

if(head == p1)head=p2;

// Progress the pointers

p0 = p2;
p2 = p1->next;
p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;

}
else
{
// Nothing to swap, just progress the pointers...
p0 = p1;
p1 = p2;
p2 = p3;
p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;
}
}
}

return(head);
}

void add_node(struct node **head, int *count, int value)

{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}

*count = *count + 1;
}
void print_list(char *listName, struct node *head)
{
mynode *temp;

printf("\n[%s] -> ", listName);

for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}

printf("NULL\n");

As you can see, the code becomes quite messy because of the pointer logic. Thats why I have not elaborated too
much on the code, nor on variations such as sorting a doubly linked list. You have to do it yourself once to
understand it.

Method2 (Divide and Conquer using Merge Sort)

Here is some cool working C code...

#include<stdio.h>
#include<ctype.h>

typedef struct node

{
int value;
struct node *next;
struct node *prev;
}mynode ;

void add_node(struct node **head, int value);

void print_list(char *listName, struct node *head);
void mergeSort(struct node** headRef);
struct node *merge2SortedLLs(struct node *head1, struct node *head2);
void splitLLInto2(struct node* source, struct node** frontRef, struct node**
backRef);

// The main function..

int main()
{
mynode *head;
head = (struct node *)NULL;
add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);

print_list("myList", head);
mergeSort(&head);
print_list("myList", head);

getch();
return(0);
}

// This is a recursive mergeSort function...

void mergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;

// Base case -- length 0 or 1

if ((head == NULL) || (head->next == NULL))
{
return;
}

// Split head into 'a' and 'b' sublists

splitLLInto2(head, &a, &b);

// Recursively sort the sublists

mergeSort(&a);
mergeSort(&b);

// Merge the two sorted lists together

*headRef = merge2SortedLLs(a, b);
}

// This is an iterative function that joins two already sorted

// Linked lists...
struct node *merge2SortedLLs(struct node *head1, struct node *head2)
{
struct node *a, *b, *c, *newHead, *temp;

a = head1;
b = head2;
c = (struct node *)NULL;
newHead = (struct node*)NULL;

if(a==NULL)return(b);
else if(b==NULL)return(a);

while(a!=NULL && b!=NULL)

{
if(a->value < b->value)
{
//printf("\na->value < b->value\n");
if(c==NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}
a = a->next;
}
else if(a->value > b->value)
{
//printf("\na->value > b->value\n");
if(c==NULL)
{
c = b;
}
else
{
c->next = b;
c = c->next;
}
b = b->next;
}
else
{
// Both are equal.
// Arbitraritly chose to add one of them and make
// sure you skip both!

if(c == NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}

a = a->next;
b = b->next;
}

// Make sure the new head is set...

if(newHead == NULL)
newHead = c;

if(a==NULL && b==NULL)

return(newHead);

if(a==NULL)
c->next = b;
else if(b==NULL)
c->next = a;

return(newHead);

// Uses the fast/slow pointer strategy

//
// This efficient code splits a linked list into two using
// the same technique as the one used to find the
// middle of a linked list!

void splitLLInto2(struct node* source, struct node** frontRef, struct node**

backRef)
{
struct node* fast;
struct node* slow;

if (source==NULL || source->next==NULL)
{
// length < 2 cases
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->next;
// Advance 'fast' two nodes, and advance 'slow' one node
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
// 'slow' is before the midpoint in the list, so split it in two
// at that point.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}

void add_node(struct node **head, int value)

{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}

void print_list(char *listName, struct node *head)

{
mynode *temp;

printf("\n[%s] -> ", listName);

for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}

printf("NULL\n");

The code to merge two already sorted sub-linked lists into a sorted linked list could be either iterative or
recursive. You already saw the iterative version above. Here is a recursive version of the same...

Recursive solution to merge two already sorted linked lists into a single linked list

struct node* sortedMergeRecursive(struct node* a, struct node* b)

{
struct node* result = NULL;
if (a==NULL) return(b);
else if (b==NULL) return(a);

// Pick either a or b, and recur

if (a->data <= b->data)
{
result = a;
result->next = sortedMergeRecursive(a->next, b);
}
else
{
result = b;
result->next = sortedMergeRecursive(a, b->next);
}

return(result);
}

Also, see how the splitLLInto2() function uses the same technique used to find the middle of a linked list to split a
linked list into two without having to keep a count of the number of nodes in the linkes list!

Here is another solution (not that great, though) to split a linked list into two. It used the count of the number of nodes
to decide where to split

void splitLLInto2(struct node* source,struct node** frontRef, struct node** b

ackRef)
{
int len = Length(source); //Get the length of the original LL..
int i;
struct node* current = source;

if (len < 2)
{
*frontRef = source;
*backRef = NULL;
}
else
{
int hopCount = (len-1)/2;

for (i = 0; i<hopCount; i++)

{
current = current->next;
}

// Now cut at current

*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}
Using recursive stack space proportional to the length of a list is not recommended. However, the recursion in this
case is ok ? it uses stack space which is proportional to the log of the length of the list. For a 1000 node list, the
recursion will only go about 10 deep. For a 2000 node list, it will go 11 deep. If you think about it, you can see that
doubling the size of the list only increases the depth by 1.
 

How to declare a structure of a linked list?

The right way of declaring a structure for a linked list in a C program is

struct node {
int value;
struct node *next;
};
typedef struct node *mynode;

Note that the following are not correct

typedef struct {
int value;
mynode next;
} *mynode;

The typedef is not defined at the point where the "next" field is declared.

struct node {
int value;
struct node next;
};
typedef struct node mynode;

You can only have pointer to structures, not the structure itself as its recursive!
 

How do you reverse a linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new
linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you
would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but
you are not changing them when reversing the linked list).
 
How would you detect a loop in a linked list? Write a C program to detect a
loop in a linked list.

This is also one of the classic interview questions

There are multiple answers to this problem. Here are a few C programs to attack this problem.

Brute force method

Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.

typedef struct node

{
void *data;
struct node *next;
}mynode;

mynode * find_loop(NODE * head)

{
mynode *current = head;

while(current->next != NULL)
{
mynode *temp = head;
while(temp->next != NULL && temp != current)
{
if(current->next == temp)
{
printf("\nFound a loop.");
return current;
}
temp = temp->next;
}
current = current->next;
}
return NULL;
}

Visited flag

Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a
node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method

Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop,
the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code

p=head;
q=head->next;

while(p!=NULL && q!=NULL)

{
if(p==q)
{
//Loop detected!
exit(0);
}
p=p->next;
q=(q->next)?(q->next->next):q->next;
}

// No loop.

The next question is how do you delete/eliminate the loop in a linked list once you detect it? I leave it up to you to
do that!
 

How do you find the middle of a linked list? Write a C program to return the
middle of a linked list

Another popular interview question

Here are a few C program snippets to give you an idea of the possible solutions.

Method1 (Uses one slow pointer and one fast pointer)

#include<stdio.h>
#include<ctype.h>

typedef struct node

{
int value;
struct node *next;
struct node *prev;
}mynode ;

void add_node(struct node **head, int value);

void print_list(char *listName, struct node *head);
void getTheMiddle(mynode *head);

// The main function..

int main()
{
mynode *head;
head = (struct node *)NULL;

add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
add_node(&head, 555);
add_node(&head, 55);

print_list("myList", head);
getTheMiddle(head);

getch();
return(0);
}

// This function uses one slow and one fast

// pointer to get to the middle of the LL.
//
// The slow pointer is advanced only by one node
// and the fast pointer is advanced by two nodes!

void getTheMiddle(mynode *head)

{
mynode *p = head;
mynode *q = head;

if(q!=NULL)
{
while((q->next)!=NULL && (q->next->next)!=NULL)
{
p=(p!=(mynode *)NULL?p->next:(mynode *)NULL);
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
}
printf("The middle element is [%d]",p->value);
}
}

// Function to add a node

void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}

// Function to print the linked list...

void print_list(char *listName, struct node *head)
{
mynode *temp;

printf("\n[%s] -> ", listName);

for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}

printf("NULL\n");

Here p moves one step, where as q moves two steps, when q reaches end, p will be at the middle of the linked list.

Method2(Uses a counter)

#include<stdio.h>
#include<ctype.h>

typedef struct node

{
int value;
struct node *next;
struct node *prev;
}mynode ;

void add_node(struct node **head, int value);

void print_list(char *listName, struct node *head);
mynode *getTheMiddle(mynode *head);

// The main function..

int main()
{
mynode *head, *middle;
head = (struct node *)NULL;

add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
add_node(&head, 555);
add_node(&head, 55);

print_list("myList", head);
middle = getTheMiddle(head);
printf("\nMiddle node -> [%d]\n\n", middle->value);

getch();
return(0);
}

// Function to get to the middle of the LL

mynode *getTheMiddle(mynode *head)
{
mynode *middle = (mynode *)NULL;
int i;

for(i=1; head!=(mynode *)NULL; head=head->next,i++)

{
if(i==1)
middle=head;
else if ((i%2)==1)
middle=middle->next;
}

return middle;
}

// Function to add a new node to the LL

void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}

// Function to print the LL

void print_list(char *listName, struct node *head)
{
mynode *temp;

printf("\n[%s] -> ", listName);

for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}

printf("NULL\n");

In a similar way, we can find the 1/3 th node of linked list by changing (i%2==1) to (i%3==1) and in the same way we
can find nth node of list by changing (i%2==1) to (i%n==1) but make sure ur (n<=i).
 

If you are using C language to implement the heterogeneous linked list,

what pointer type will you use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It
is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer
to any type as it is a generic pointer type.

Check out the C program to implement a Generic linked list in the same FAQ.
 

How to compare two linked lists? Write a C program to compare two linked
lists.

Here is a simple C program to accomplish the same.

int compare_linked_lists(struct node *q, struct node *r)
{
static int flag;

if((q==NULL ) && (r==NULL))

{
flag=1;
}
else
{
if(q==NULL || r==NULL)
{
flag=0;
}
if(q->data!=r->data)
{
flag=0;
}
else
{
compare_linked_lists(q->link,r->link);
}
}
return(flag);
}

Another way is to do it on similar lines as strcmp() compares two strings, character by character (here each node is
like a character).
 

How to create a copy of a linked list? Write a C program to create a copy of

a linked list.

Check out this C program which creates an exact copy of a linked list.

copy_linked_lists(struct node *q, struct node **s)

{
if(q!=NULL)
{
*s=malloc(sizeof(struct node));
(*s)->data=q->data;
(*s)->link=NULL;
copy_linked_list(q->link, &((*s)->link));
}
}
 
Write a C program to free the nodes of a linked list

Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this
wrong.

This is the wrong way to do it

struct list *listptr, *nextptr;

for(listptr = head; listptr != NULL; listptr = listptr->next)
{
free(listptr);
}

If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do
something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can
cause unpredictable results!

This is the right way to do it

struct list *listptr, *nextptr;

for(listptr = head; listptr != NULL; listptr = nextptr)
{
nextptr = listptr->next;
free(listptr);
}
head = NULL;

After doing this, make sure you also set the head pointer to NULL!
 

Can we do a Binary search on a linked list?

Great C datastructure question!

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will
be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any
element in the array in constant time. This is what makes it so fast. You can get to the middle of the array
just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will
have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a
linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node
contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the
first or the second half of the linked list. Continue doing that with each half-list.
 

Write a C program to return the nth node from the end of a linked list.

Here is a solution which is often called as the solution that uses frames.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer
(ptr1) till the number of increments cross n (which is 6 in this case)

STEP 1 : 1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2 : 1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10

Now, start the second pointer (ptr2) and keep on incrementing it till the first pointer (ptr1) reaches the end of the LL.

STEP 3 : 1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)

So here you have!, the 6th node from the end pointed to by ptr2!

Here is some C code..

struct node
{
int data;
struct node *next;
}mynode;

mynode * nthNode(mynode *head, int n /*pass 0 for last node*/)

{
mynode *ptr1,*ptr2;
int count;

if(!head)
{
return(NULL);
}

ptr1 = head;
ptr2 = head;
count = 0;
while(count < n)
{
count++;
if((ptr1=ptr1->next)==NULL)
{
//Length of the linked list less than n. Error.
return(NULL);
}
}

while((ptr1=ptr1->next)!=NULL)
{
ptr2=ptr2->next;
}

return(ptr2);
}
 

How would you find out if one of the pointers in a linked list is corrupted or
not?

This is a really good interview question. The reason is that linked lists are used in a wide variety of scenarios and
being able to detect and correct pointer corruptions might be a very valuable tool. For example, data blocks
associated with files in a file system are usually stored as linked lists. Each data block points to the next data block. A
single corrupt pointer can cause the entire file to be lost!

• Discover and fix bugs when they corrupt the linked list and not when effect becomes visible in some other
part of the program. Perform frequent consistency checks (to see if the linked list is indeed holding the data
that you inserted into it).
• It is good programming practice to set the pointer value to NULL immediately after freeing the memory
pointed at by the pointer. This will help in debugging, because it will tell you that the object was freed
somewhere beforehand. Keep track of how many objects are pointing to a object using reference counts if
required.
• Use a good debugger to see how the datastructures are getting corrupted and trace down the problem.
Debuggers like ddd on linux and memory profilers like Purify, Electric fence are good starting points.
These tools should help you track down heap corruption issues easily.
• Avoid global variables when traversing and manipulating linked lists. Imagine what would happen if a
function which is only supposed to traverse a linked list using a global head pointer accidently sets the
head pointer to NULL!.
• Its a good idea to check the addNode() and the deleteNode() routines and test them for all types of
scenarios. This should include tests for inserting/deleting nodes at the front/middle/end of the linked list,
working with an empty linked list, running out of memory when using malloc() when allocating memory for
new nodes, writing through NULL pointers, writing more data into the node fields then they can hold
(resulting in corrupting the (probably adjacent) "prev" and "next" pointer fields), make sure bug fixes and
enhancements to the linked list code are reviewed and well tested (a lot of bugs come from quick and dirty
bug fixing), log and handle all possible errors (this will help you a lot while debugging), add multiple levels of
logging so that you can dig through the logs. The list is endless...
• Each node can have an extra field associated with it. This field indicates the number of nodes after this
node in the linked list. This extra field needs to be kept up-to-date when we inserte or delete nodes in the
linked list (It might become slightly complicated when insertion or deletion happens not at end, but anywhere
in the linked list). Then, if for any node, p->field > 0 and p->next == NULL, it surely points to a pointer
corruption.
• You could also keep the count of the total number of nodes in a linked list and use it to check if the list is
indeed having those many nodes or not.

The problem in detecting such pointer corruptions in C is that its only the programmer who knows that the
pointer is corrupted. The program has no way of knowing that something is wrong. So the best way to fix these
errors is check your logic and test your code to the maximum possible extent. I am not aware of ways in C
to recover the lost nodes of a corrupted linked list. C does not track pointers so there is no good way to know if an
arbitrary pointer has been corrupted or not. The platform may have a library service that checks if a pointer points to
valid memory (for instance on Win32 there is a IsBadReadPtr, IsBadWritePtr API.) If you detect a cycle in the link list,
it's definitely bad. If it's a doubly linked list you can verify, pNode->Next->Prev == pNode.

I have a hunch that interviewers who ask this question are probably hinting at something called Smart Pointers in
C++. Smart pointers are particularly useful in the face of exceptions as they ensure proper destruction of
dynamically allocated objects. They can also be used to keep track of dynamically allocated objects shared by
multiple owners. This topic is out of scope here, but you can find lots of material on the Internet for Smart Pointers.

If you have better answers to this question, let me know!

 

Write a C program to insert nodes into a linked list in a sorted fashion

The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of
the list, or a point just before a node which is larger than the new node.

Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being
passed to this function.

// Special case code for the head end

void linkedListInsertSorted(struct node** headReference, struct node* newNode
)
{
// Special case for the head end
if (*headReference == NULL || (*headReference)->data >= newNode->data)
{
newNode->next = *headReference;
*headReference = newNode;
}
else
{
// Locate the node before which the insertion is to happen!
struct node* current = *headReference;
while (current->next!=NULL && current->next->data < newNode->data)
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
 

Write a C program to remove duplicates from a sorted linked list

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent
nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be
noted before the deletion.

// Remove duplicates from a sorted list

void RemoveDuplicates(struct node* head)
{
struct node* current = head;
if (current == NULL) return; // do nothing if the list is empty

// Compare current node with next node

while(current->next!=NULL)
{
if (current->data == current->next->data)
{
struct node* nextNext = current->next->next;
free(current->next);
current->next = nextNext;
}
else
{
current = current->next; // only advance if no deletion
}
}
}
 

How to read a singly linked list backwards?

Use Recursion.
 

How can I search for data in a linked list?

The only way to search a linked list is with a linear search, because the only way a linked list?s members can be
accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data
structure so that searches can be more efficient.
 

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<stdio.h>

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.
 

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 <stdio.h>
#include <string.h>
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) < To (DEST)
*
* +--+---------------------+--+
* | | | |
* +--+---------------------+--+
* ^ ^
* | |
* 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.
 

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<stdio.h>

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 < m && x[i] == y[i + j]; ++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<stdio.h>

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 < m)
{
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 < n)
{
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.
 

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<stdio.h>
#include<stdarg.h>

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);
}
 

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?

 

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 <stdio.h>

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]
 

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);
}

Here is another C program to do the same...

#include <stdio.h>
#include <conio.h>

void mySubstr(char *dest, char *src, int position, int length);

int main()
{
char subStr[100];
char str[]="My Name Is Sweet";

mySubstr(subStr, str, 1, 5);

printf("\nstr = [%s]"
"\nsubStr = [%s]\n\n",
str, subStr);
getch();
return(0);
}

void mySubstr(char *dest, char *src, int position, int length)

{
while(length > 0)
{
*dest = *(src+position);
dest++;
src++;
length--;
}
}
 

Write your own copy() function

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

#include <stdio.h> /* 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 = "<something>";
file_path_to = "<something_else>";

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);
}
 

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 <string.h>

#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 st

ring ..
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.
 
Write a C program to implement your own strdup() function.

Here is a C program to implement the strdup() function.

char *mystrdup(char *s)

{
char *result = (char*)malloc(strlen(s) + 1);
if (result == (char*)0){return (char*)0;}
strcpy(result, s);
return result;
}
 

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);
}
 
Write your own strcat() function

Here is a C function which implements the strcat() function...

/* Function to concatenate string t to end of s; return s */

char *myStrcat(char *s, const char *t)
{
char *p = s;

if (s == NULL || t == NULL)
return s; /* we need not have to do anything */

while (*s)
s++;

while (*s++ = *t++)

;

return p;
}