Some Basics of Computer Science, good for interview preparations 
( All the programs have been run on Fedora 11, gcc (GCC) 4.4.1 20090725 (Red Hat 4.4.1-2) )
Creating a Linked List
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
// Synonym for the basic DS as mynode
typedef struct node mynode;
//Basic Linked list DS
struct node {
int value;
mynode *next;
};
mynode *a,*b;
//Typecasting and allocating memory
a = (mynode *) malloc(sizeof(mynode));
b = (mynode *) malloc(sizeof(mynode));
b->value=100;
b->next=NULL;
a->value=10;
a->next=b;
//Output is 10
printf(”%d”,*(a));
//Output is 100
printf(”\n%d”,*(a->next));
return 0;
}
Removing Duplicates from a Linked List
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
// Synonym for the basic DS as mynode
typedef struct node mynode;
//Basic Linked list DS
struct node {
int value;
mynode *next;
};
mynode *a,*b,*c,*d;
//Typecasting and allocating memory
a = (mynode *) malloc(sizeof(mynode));
b = (mynode *) malloc(sizeof(mynode));
c = (mynode *) malloc(sizeof(mynode));
d = (mynode *) malloc(sizeof(mynode));
d->value=400;
d->next=NULL;
c->value=100;
c->next=d;
b->value=100;
b->next=c;
a->value=10;
a->next=b;
//Creating a copy of node to traverse, don play with the head node variable
mynode *current;
current = (mynode *) malloc(sizeof(mynode));
current=a;
//Start if there is next node
while (current->next != NULL) {
//Compare the value of current node to the valude of next node
if(current->value == current->next->value) {
mynode *temp;
//Creating a temporary node
temp = (mynode *) malloc(sizeof(mynode));
temp=current->next->next;
//Assigning the pointer of next node to the current
free(current->next);
current->next=temp;
}
else current=current->next;
}
//Print the elements of the node
while (a!=NULL) {
printf(”\n The Node Value = %d “,a->value);
a=a->next;
}
return 0;
}
Basic Binary Tree Declaration and Lookup
#include <stdio.h>
#include <stdlib.h>
// Synonym for the basic DS as mynode
typedef struct node mynode;
static int ret=0;
//Basic Binary tree DS
struct node {
int value;
mynode *left;
mynode *right;
};
mynode *a,*b,*c,*d,*e;
//Recursively looking for that node depending on whether to go left/right child
static int lookup (mynode *what, int target) {
if(what == NULL) return 0;
if(target == what->value) {
return 1;
}
if(target <= what->value ) return(lookup(what->left,target));
else return(lookup(what->right,target));
return 0;
}
int main (int argc, char *argv[]) {
//Typecasting and allocating memory
a = (mynode *) malloc(sizeof(mynode));
b = (mynode *) malloc(sizeof(mynode));
c = (mynode *) malloc(sizeof(mynode));
d = (mynode *) malloc(sizeof(mynode));
e = (mynode *) malloc(sizeof(mynode));
e->value=60;
e->left=e->right=NULL;
d->value=30;
d->left=c->right=NULL;
c->value=30;
c->left=c->right=NULL;
b->value=40;
b->left=c;
b->right=d;
a->value=50;
a->left=b;
a->right=e;
ret=lookup(a,30);
//A value of 1 means node is found
printf(”%d”,ret);
return 0;
}
Insert a new Node in Binary Tree and Look for it
#include
#include
// Synonym for the basic DS as mynode
typedef struct node mynode;
static int ret=0;
//Basic Binary tree DS
struct node {
int value;
mynode *left;
mynode *right;
};
mynode *a,*b,*c,*d,*e;
//Create a new node with NULL left and right nodes, takes the value of node as the parameter
struct node* createNewNode (int value) {
mynode *tmp;
tmp = (mynode *) malloc(sizeof(mynode));
tmp->value=value;
tmp->left=NULL;
tmp->right=NULL;
return tmp;
}
//Insert a new node to the tree by recursively traversing and adding when node has NULL left/right node
struct node* insert (struct node* whichNode, int value) {
if(whichNode == NULL) return createNewNode(value);
if(value <= whichNode->value) whichNode->left = insert(whichNode->left,value);
else whichNode->right = insert(whichNode->right,value);
return whichNode;
}
//Lookup for a particular Node value
static int lookup (mynode *what, int target) {
if(what == NULL) return 0;
if(target == what->value) {
return 1;
}
if(target <= what->value ) return(lookup(what->left,target));
else return(lookup(what->right,target));
return 0;
}
int main (int argc, char *argv[]) {
//Typecasting and allocating memory
a = (mynode *) malloc(sizeof(mynode));
b = (mynode *) malloc(sizeof(mynode));
c = (mynode *) malloc(sizeof(mynode));
d = (mynode *) malloc(sizeof(mynode));
e = (mynode *) malloc(sizeof(mynode));
e->value=60;
e->left=e->right=NULL;
d->value=30;
d->left=c->right=NULL;
c->value=30;
c->left=c->right=NULL;
b->value=40;
b->left=c;
b->right=d;
a->value=50;
a->left=b;
a->right=e;
//Inserting a Node of value 20
insert(a,20);
//Looking up for the newly inserted value
ret=lookup(a,20);
//A value of 1 means node is found
printf(”%d”,ret);
return 0;
}
Sorting ( Insertion, Bubble, Selection Sorts)
#include
#include
int main (int argc, char *argv []) {
int a[] ={10,5,4,5,3};
insertion(5,a);
bubble (5,a);
selection(5,a);
return 0;
}
int insertion (int len, int *arr) {
int i,j,k;
int whereToInsert=-1;
for(i=1;i=0;j–) {
if(arr[j] > arr[i]) {
whereToInsert=j;
}
}
if(whereToInsert >-1 )
insertElement(arr,i,whereToInsert,len);
}
printArray(arr,len);
}
int insertElement (int *arr, int end, int start, int len) {
int temp=arr[start];
int temp2=arr[end];
int i=0;
int j=0;
for(i=end;i>start;i–) {
arr[i]=arr[i-1];
}
arr[start]=temp2;
}
int printArray(int *arr, int len) {
int i=0;
printf(”\n”);
for(i=0;i
printf(”\t%d”,arr[i]);
}
int bubble (int len, int *arr) {
int i=0,temp,j=0;
for(i=0;i
for(j=0;j<(len-i-1);i++) { if(arr[j] > arr[j+1]) {
temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
printArray(arr,len);
}
int selection (int len, int *arr) {
int i=0,j=0,min=-1,temp=0;
for(i=0;i
for(j=i+1;j
if(arr[j] < min) {
min=arr[j];
temp=arr[j];
arr[j]=arr[i];
arr[i]=arr[j];
}
}
}
printArray(arr,len);
}
Time Complexities of Sorting Algorithms
Average Worst Memory
Bubble n2 n2 1
Selection n2 n2 1
Insertion n2 n2 1
Mergesort nlogn nlogn n
Binary nlogn nlogn n
Heapsort nlogn nlogn n
quicksort nlogn n2 logn
Awesome Links
Binary Trees
http://cslibrary.stanford.edu/110/BinaryTrees.html
Complete Collections
http://profile.iiita.ac.in/pkmallick_03/
SQL Tutorials
http://www.db.cs.ucdavis.edu/teaching/sqltutorial/
