Tuesday, 17 September 2013

Skip List

HTML Online Editor Sample

 

#include<stdio.h>

#include<stdlib.h>
#include<unistd.h>
#include<iostream>
#include<sys/time.h>
using namespace std;
 
class skiplist
{
private:
struct lnode
{
int key;
lnode* next;
}*lhead;
 
struct snode
{
 
struct lnode *list;
snode *next;
int key;
}*shead;
int count;
public:
skiplist();
void insert(int key);
void insert_skip();
void search(int key);
void  remove(int key);
void print();
void print_skip();
void sort();
bool isempty();
bool insert_in_skip();
~skiplist();
};
skiplist::skiplist()
{
lhead=NULL;
shead=NULL;
count=0;
}
bool skiplist::isempty()
{
 
if(lhead==NULL)
return true;
return false;
}
bool skiplist::insert_in_skip()
{
 
 
if(count%4==0)
return true;
return false;
}
void skiplist::insert(int key)
{
 
if(isempty())
{
lhead=new lnode;
//shead=new snode;
//shead->next=NULL;
lhead->next=NULL;
//shead->key=key;
lhead->key=key;
//shead->list=lhead;
printf("\n Inserted \n");
count++;
return ;
}/*
//if(insert_in_skip())
{
lnode *t=new lnode();
//snode *r=new snode();
t->key=key;
t->next=NULL;
//r->key=key;
///r->next=NULL;
//r->list=NULL;
lnode *p=lhead;
while(p->next!=NULL)
p=p->next;
//snode *q=shead;
while(q->next!=NULL)
q=q->next;
p->next=t;
//q->next=r;
printf("\n Inserted \n");
count++;
return;
}*/
lnode *t=new lnode();
 
t->key=key;
t->next=NULL;
lnode *p=lhead;
while(p->next!=NULL)
p=p->next;
p->next=t;
printf("\n Inserted \n");
count++;
return ;
}
void skiplist::insert_skip()
{
lnode *p=lhead;
shead=new snode();
shead->key=lhead->key;
shead->list=lhead;
int i=1;
while(p)
{
if(i%4==0)
{
snode *s=new snode;
s->key=p->key;
s->list=p;
snode *r=shead;
while(r->next!=NULL)
r=r->next;
r->next=s;
}
p=p->next;
i++;
}
}
 
void skiplist::print()
{
cout<<endl;
lnode *p=lhead;
while(p!=NULL)
{
 
cout<<p->key<<"   ";
p=p->next;
}
}
void skiplist::print_skip()
{
cout<<endl;
snode *p=shead;
while(p)
{
cout<<p->key<<"    ";
p=p->next;
}
}
void skiplist::sort()
{
lnode *p,*q;
p=lhead;
while(p->next!=NULL)
{
q=p->next;
while(q!=NULL)
{
if(q->key<p->key)
{
int temp=q->key;
q->key=p->key;
p->key=temp;
 
}
q=q->next;
}
p=p->next;
}
 
}
 
void skiplist::search(int key)
{
snode *p=shead;
while(p->next!=NULL)
{
if(p->next->key>key)
 
 
{
 
lnode *q=p->list;
while(q!=NULL)
 
{
if(q->key==key)
{
printf("\n Found\n");
return;
}
q=q->next;
}
 
 
}
if(p->next->key==key)
 
{
printf("\n found\n");
return ;
}
p=p->next;
}
 
lnode *q=p->list;
while(q!=NULL)
 
{
if(q->key==key)
{
printf("\n Found\n");
return;
}
q=q->next;
}
printf("\n Not found");
}
 
 
void skiplist::remove(int key)
{
if(lhead->key==key)
{
 
lnode *r=lhead;
lhead=lhead->next;
shead->list=lhead;
shead->key=lhead->key;
delete r;
return;
}
snode *p=shead;
while(p->next!=NULL)
{
if(p->next->key>key)
 
 
{
 
lnode *q=p->list;
while(q->next!=NULL)
 
{
if(q->next->key==key)
{
lnode *r=q->next;
q->next=r->next;
delete r;
printf("\n Found\n");
return;
}
q=q->next;
}
 
 
}
if(p->next->key==key)
 
{
lnode *q=p->list;
while(q->next->key!=key)
q=q->next;
lnode *r=q->next;
q->next=r->next;
snode *s=p->next;
p->next=s->next;
delete r;
delete s;
printf("\n found\n");
return ;
}
p=p->next;
}
 
lnode *q=p->list;
while(q->next!=NULL)
 
{
if(q->next->key==key)
{
lnode * s=q->next;
q->next=s->next;
delete s;
//printf("\n Found\n");
return;
}
q=q->next;
}
printf("\n Not found");
 
 
 
}
skiplist::~skiplist()
{
snode *p=shead;
while(shead!=NULL)
{
p=shead;
p->list=NULL;
shead=shead->next;
delete p;
}
lnode *q=lhead;
while(lhead!=NULL)
{
 
q=lhead;
lhead=lhead->next;
delete q;
}
}
int main()
{
skiplist s;
s.insert(10);
s.insert(9);
s.insert(18);
s.insert(1);
s.insert(100);
s.insert(-15);
s.print();
s.sort();
s.insert_skip();
s.print();
s.print_skip();
struct timeval tv_start,tv_end;
gettimeofday(&tv_start,NULL);
s.search(100);
gettimeofday(&tv_end,NULL);
cout<<endl;
cout<<((tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)/1000000)<<" sec";
 
s.remove(100);
s.remove(10);
s.remove(-15);
s.remove(9);
s.print();
s.print_skip();
return 0;
}
Posted by at No comments:

Linked List for Interview

HTML Online Editor Sample

 

#include<stdio.h>

#include<iostream>
using namespace std;
class linkedlist
{
private:
struct node
{
int key;
node* next;
}*head;
public:
linkedlist();
void insert(int key);
 
int remove(int key);
void swap(int k);
void print();
int count_node();
int find_key(int key);
bool isempty();
void reverse();
void selection_sort();
void bobble_sort();
void insertion_sort();
void quick_sort();
void merge_sort();
void delete_m_n(int m,int n);
int find_middle();
void reverse_k(int k);
void print_recursive();
void print_rec(node *t);
~linkedlist();
 
};
 
linkedlist::linkedlist()
{
head=NULL;
}
 
void linkedlist::insert(int key)
{
if(isempty())
{head=new node();
 
head->key=key;
head->next=NULL;
printf("Inserted  :\n");
return;
}
struct node *t=new node();
t->key=key;
t->next=head;
head=t;
printf("\n Inserted At Begning \n");
return ;
}
 
int linkedlist::remove(int key)
{
int val;
if(isempty())
{
printf("\n lsit is empty ");
return -10000;
}
if(head->key==key)
{
 
struct node *t=head;
head=head->next;
val=t->key;
delete(t);
return val;
 
}
 
struct node *t=head;
while(t->next!=NULL)
{
if(t->next->key==key)
{
node *p=t->next;
t->next=t->next->next;
val=p->key;
delete(p);
return val;
 
 
}
t=t->next;
}
printf("\n key  not present\n");
return -10000;
}
void linkedlist::print()
{
if(isempty())
{
printf("\n lsit is empty  \n");
return ;
 
}
cout<<"\n ***************  list    is  **************************\n";
node *t=head;
while(t)
{
cout<<t->key<< "  ";
t=t->next;
}
cout<<"\n *********************************************************\n";
}
void linkedlist::swap(int k)
{
if(isempty())
{
printf("\n List is Empty\n");
return;
}
int n=count_node();
if(k>n)
{
printf("\n list is small to perform swap operation\n");
return ; 
 
}
if(2*k-1==n)
return;
 
int r=n-k+1;
int i=1;
struct node *x=head;
struct node *x_prev=NULL;
while(i<k)
{
x_prev=x;
x=x->next;
i++;
}
i=1;
struct node *y=head;
struct node *y_prev=NULL;
while(i<r)
 
{
y_prev=y;
y=y->next;
i++;
 
}
/*if(k==r-1||k==r+1)
{
forward_node->next=backward_node->next;
backward_node->next=backward_node->next->next;
 
forward_node->next->next=backward_node;
}
else
{
struct node * p=forward_node->next;
struct node * q=forward_node->next->next;
forward_next->next=backward_node->next;
p->next=backward_node->next->next;
backward_node->next->next=q;
backward_node->next=p;
}
if(k==1)
*/
 
 
if(x_prev)
x_prev->next=y;
if(y_prev)
y_prev->next=x;
 
node *temp = x->next;
    x->next = y->next;
    y->next = temp;
if(k==1)
head=y;
if(k==n)
head=x;
 
}
int linkedlist ::count_node()
{
int count=0;
struct node *t=head;
while(t!=NULL)
{
t=t->next;
count++;
}
return count;
}
 
 
bool linkedlist::isempty()
{
 
if(head==NULL)
return true;
return false;
}
 
linkedlist::~linkedlist()
{
node *t=head;
while(head!=NULL)
{
t=head;
head=head->next;
delete(t);
}
}
void linkedlist::reverse()
{
if(isempty())
 
return;
 
if(head->next==NULL)
return ;
 
node *p=head;
node *q=head->next;
p->next=NULL;
while(q)
{
p=q;
q=q->next;
p->next=head;
head=p;
}
 
}
 
void linkedlist::delete_m_n(int m,int n)
{
if(n==0)
return;
node *p=head;
node *r,*s;
int i=1;
int j=1;
while(p!=NULL)
{
if(i==m&&p->next!=NULL)
{
//printf("\n ram\n");
r=p;
p=p->next;
s=p;
while(p->next!=NULL&&j<n)
{
//cout<<p->key<<endl;
p=p->next;
j++;
 
}
if(p->next==NULL)
{
r->next=NULL;
 
}
else
{
i=1;j=1;
//cout<<p->key<<endl;
r->next=p->next;
p->next=NULL;
p=r->next;
continue;
}
while(s!=NULL)
{
node *t=s;
s=s->next;
delete t;
}
//cout<<p->key<<endl<<i<<endl;
}
i++;
p=p->next;
}
}
int linkedlist::find_middle()
{
node *p,*q;
p=head;
q=head;
while(q->next!=NULL&&q->next->next!=NULL)
{
 
p=p->next;
q=q->next->next;
}
return p->key;
 
}
 
void linkedlist::reverse_k(int k)
{
node *p=head;
}
 
void linkedlist::print_rec(node *t)
{
if(t==NULL)
return;
printf("\n %d",t->key);
print_rec(t->next);
}
void linkedlist::print_recursive()
{
print_rec(head);
}
int main()
{
linkedlist l;
l.insert(10);
l.insert(20);
l.insert(30);
l.insert(100);
l.insert(2);
l.insert(4);
l.insert(50);
l.insert(-10);
l.insert(76);
l.insert(89);
l.insert(0);
l.insert(17);
cout<<l.count_node();
l.print();
//l.swap(4);
l.reverse();
l.print();
//int a,b;
//cin>>a>>b;
l.delete_m_n(1,4);
l.print();
//cout<<l.find_middle();
l.print_recursive();
return 0;
}
Posted by at No comments:

Binary Search Tree Interview Questions

HTML Online Editor Sample

 

#include<stdio.h>

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#include<stack>
 
class bst
{
private:
 
struct bnode
{
bnode *left;
bnode* right;
int key;
}*root;
 
struct snode
{
bnode * input;
snode * next;
}*top;
struct qnode
{
bnode *input;
qnode * next;
}*front;
 
 
public:
bst();
void insert(bnode * &root,int key);
void insertintotree(int key);
void search(bnode * root,int key);
void searchintree(int key);
int find_max(bnode* root);
void delete_node(bnode *&root,int &key);
void deletenodefromtree(int key);
 
void remove(bnode * root);
void mirror(bnode * root);
void maketreemirror();
void heightoftree();
int size();
void scan(bnode * root,int &count);
void lca(bnode* root,int key1,int key2);
void leastcommonancestorofkey(int key1,int key2);
void printinorder();
void printpreorder();
void printpostorder();
void inorder(bnode * root);
void preorder(bnode * root);
void postorder(bnode * root);
int height_tree(bnode *root);
void root_to_leaf(bnode *root);
void printroottoleafpath();
void push(bnode *root);
void pop();
void print_stack(snode *top);
void pathfromroottoleaf();
void print_ancestor(bnode * root,int key);
void printancestoroftree(int key);
 
void print_key(bnode * root,int key1,int key2);
void print_inorder(bnode * root,int key1,int key2);
void printdatabetweentwokey(int key1,int key2);
void kth_smallest(bnode *root,int k,int &count);
void kthsmallestintree(int key);
int get_level(bnode * root,int key);
void getlevelofkey(int key);
void level_order();
void inqueue(bnode * root);
void * dqueue();
bool isempty();
void reverse_level_order();
void leaf_count(bnode* root,int &count);
void totalnoofleaf();
//bool isbst(bnode *root1,bnode *root2);
//bool children_sum_property(bnode* root);
//int diameter(bnode *root);
//void convert_children_sum_tree(bnode* root);
void level_order_spiral();
bool isheight_balanced(bnode* root);
void isheightbalancedtree();
//void inorder_without_recursion();
//void inorder_witout_stack();
//bool is_triplet_zero(bnode* root);
//bool find_sum(int key1,int key2);
//void list_to_tree();
//void tree_to_list();
//void iterative_preorder();
//void iterative_postorder();
~bst();
};
 
bst::bst()
{
 
root=NULL;
top=NULL;
front=NULL;
 
}
int max(int a,int b)
{
 
if(a>=b)
return a;
else return b;
}
 
 
void bst::insert(bnode * &root,int key)
{
if(root==NULL)
{
 
root=new bnode;
root->key=key;
root->left=NULL;
root->right=NULL;
printf("\n Insterted\n");
return;
}
 
if(root->key>key)
insert(root->left,key);
else if(root->key<key)
insert(root->right,key);
else
printf("\n key already present\n");
}
void bst::insertintotree(int key)
{
insert(root,key);
}
void bst::maketreemirror()
{
 
mirror(root);
}
void bst::search(bnode *root,int key)
{
if(root==NULL)
return ;
if(root->key==key)
{
 
printf("\nkey found \n");
 
return ;
}
if(root->key>key)
search(root->left,key);
else if(root->key<key)
search(root->right,key);
 
}
 
 
void bst::searchintree(int key)
{
search(root,key);
 
}
void bst::mirror(bnode *root)
{
if(root==NULL)
return;
bnode* temp=root->left;
root->left=root->right;
root->right=temp;
mirror(root->left);
mirror(root->right);
return;
 
 
}
 
 
void bst::heightoftree()
{
printf("\n the height of the tree is %d \n",height_tree(root));
 
}
int bst::size()
{
int count=0;
scan(root,count);
printf("  size is %d",count); 
 
}
void bst::scan(bnode * root,int &count)
{
if(root==NULL)
return;
count++;
scan(root->left,count);
scan(root->right,count);
 
}
void bst::inorder(bnode * root)
{
if(root==NULL)
return;
inorder(root->left);
printf(" -> %d ",root->key);
inorder(root->right);
}
void bst:: printinorder()
{
printf("\n *********************inorder travasal ****************\n");
inorder(root);
}
 
 
void bst :: preorder(bnode *root)
{
if(root==NULL)
return ;
printf(" -> %d ",root->key);
preorder(root->left);
preorder(root->right);
}
 
 
 
void bst::printpreorder()
{
printf("\n *********************preorder travasal ****************\n");
preorder(root);
}
 
 
void bst::postorder(bnode* root)
{
if(root==NULL)
return ;
postorder(root->left);
postorder(root->right);
printf(" -> %d ",root->key);
}
 
void bst::printpostorder()
{
printf("\n *********************postorder travasal ****************\n");
postorder(root);
}
 
 
 
int bst::height_tree(bnode * root)
{
if(root==NULL) return -1;
return 1+max(height_tree(root->left),height_tree(root->right));
 
}
 
 
 
void bst:: pathfromroottoleaf()
{
root_to_leaf(root);
 
}
 
void bst::print_ancestor(bnode *root,int key)
{
if(root==NULL)
return;
if(root->key==key)
return;
printf(" %d -> ",root->key);
if(key<root->key)
print_ancestor(root->left,key);
else
print_ancestor(root->right,key);
}
void bst::printancestoroftree(int key)
{
print_ancestor(root,key);
}
 
void bst::kth_smallest(bnode *root,int k,int &count)
{
if(root==NULL)
return ;
kth_smallest(root->left,k,count);
if(count+1==k)
{
printf("\n %d smallest  key is %d \n",k,root->key);
count=100000000;
return ;
}
count++;
kth_smallest(root->right,k,count);
 
}
void bst::kthsmallestintree(int k)
{
int count=0;
kth_smallest(root,k,count);
}
int bst::get_level(bnode *root,int key)
{
if(root==NULL)
return -100000;
if(root->key==key)
return 1;
if(root->key>key)
return 1+get_level(root->left,key);
else
return 1+get_level(root->right,key);
 
}
void bst::getlevelofkey(int key)
{
printf(" the key %d is at %d level",key,get_level(root,key));
}
 
 
void bst::leaf_count(bnode *root,int &count)
{
if(root==NULL)
{
count++;
return ;
}
leaf_count(root->left,count);
leaf_count(root->right,count); 
 
}
void bst::totalnoofleaf()
{
 
int count=0;
leaf_count(root,count);
printf("\n Total No Of Leaf in The tree is %d \n",count);
 
 
}
 
void bst::lca(bnode *root,int key1,int key2)
{
if(root==NULL)
return;
if(root->key>=key1&&root->key<=key2)
{printf(" \n The LCA is %d\n",root->key);
return ;
}
else if(root->key<key1)
return lca(root->right,key1,key2);
else
return lca(root->left,key1,key2);
 
 
}
void bst::leastcommonancestorofkey(int key1,int key2)
{
if(key2>key1)
lca(root,key1,key2);
else
lca(root,key2,key1);
}
 
bool bst::isheight_balanced(bnode* root)
{
if(root==NULL)
return true;
if(isheight_balanced(root->left)&&isheight_balanced(root->right)){
if(abs(height_tree(root->left)-height_tree(root->right))<=0)
return true;
else return false;
}
 
}
void bst::isheightbalancedtree()
{
if(isheight_balanced(root))
printf("\n Height Balanced\n");
else
printf("\n Not height Balanced\n");
}
 
void bst::remove(bnode *root)
{
if(root==NULL)
return;
remove(root->left);
remove(root->right);
delete(root);
 
}
 
int bst::find_max(bnode *root)
{
while(root->right!=NULL)
root=root->right;
return root->key;
 
}
void bst::delete_node(bnode* &root,int &key)
{
 
 
if(root==NULL)
return;
 
if(root->key==key)
{
if(root->left!=NULL&&root->right!=NULL)
{
root->key=find_max(root->left);
delete_node(root->left,root->key);
 
}
 
else
{
 
bnode *t=root;
root=(root->left!=NULL)?root->left:root->right;
delete t;
return;
}
 
}
 
if(key<root->key)
delete_node(root->left,key);
else if(root->key<key)
delete_node(root->right,key);
 
 
 
}
 
void bst::deletenodefromtree(int key)
{
delete_node(root,key);
}
 
void bst:: print_stack(snode *t)
{
if(t==NULL)
return;
print_stack(t->next);
printf(" -> %d ",t->input->key);
 
}
void bst::pop()
{
if(top==NULL)
return;
snode *t=top;
top=top->next;
delete t;
return ;
}
 
void bst::push(bnode *root)
{
if(top==NULL)
{
top=new snode;
top->next=NULL;
top->input=root;
return;
}
snode *t;
t=new snode;
t->input=root;
t->next=top;
top=t;
return;
 
}
 
void bst::print_inorder(bnode * root,int key1,int key2)
{
if(root==NULL)
return;
if(root->key>=key1&&root->key<=key2)
push(root);
if(root->key>=key2)
{print_inorder(root->left,key1,key2);return;}
 
if(root->key<=key1)
{print_inorder(root->right,key1,key2);return;}
print_inorder(root->left,key1,key2);
print_inorder(root->right,key1,key2);
 
 
}
void bst::print_key(bnode *root,int key1,int key2)
{
 
 
if(root->key<key1)
print_key(root->right,key1,key2);
else if(root->key>key2)
print_key(root->left,key1,key2);
 
if(key1<=root->key&&key2>=root->key)
{
print_inorder(root,key1,key2);
print_stack(top);
//push(root);
}
 
 
}
 
void bst::printdatabetweentwokey(int key1,int key2)
{
if(key1<=key2)
print_key(root,key1,key2);
else
print_key(root,key2,key1);
}
void bst::root_to_leaf(bnode* root)
{
 
if(root->left==NULL&&root->right==NULL)
{
printf("\n");
push(root);
print_stack(top);
printf("\n");
pop();
return;
 
 
 
}
push(root);
if(root->left!=NULL)
root_to_leaf(root->left);
if(root->right!=NULL)
root_to_leaf(root->right);
pop();
 
/*
 
if(root->left==NULL&&root->right==NULL)
{
push(root);
printf("\n");
print_stack(top);
printf("\n");
pop();
return;
}
push(root);
if(root->left!=NULL)
{
root_to_leaf(root->left);}
 
if(root->right!=NULL)
{root_to_leaf(root->right);}
 
pop();*/
}
void bst::printroottoleafpath()
{
 
root_to_leaf(root);
}
bool bst::isempty()
{
 
if(front==NULL)
return true;
else
return false;
}
 
void bst::inqueue(bnode * root)
{
if(front==NULL)
{
 
 
front=new qnode;
front->input=root;
front->next=NULL;
return;
}
qnode *t=front;
 
 while(t->next!=NULL)
t=t->next;
qnode *p=new qnode;
p->input=root;
p->next=NULL;
t->next=p;
return;
 
}
 
void* bst::dqueue()
{
if(front==NULL)
{
return NULL;
}
qnode *t=front;
front=front->next;
bnode * node=t->input;
delete t;
return node;
 
 
}
void bst::level_order()
{
 
if(root==NULL)
return;
int count=0;
int level=1;
inqueue(root);
while(!isempty())
{
bnode *t=(bnode*)dqueue();
level--;
printf(" - %d",t->key);
if(t->left!=NULL)
{
inqueue(t->left);
count++;
}
if(t->right!=NULL)
{inqueue(t->right);
 
count++;
}
 
if(level==0)
{
level=count;
count=0;
printf("\n");
}
}
 
 
}
void bst::reverse_level_order()
{
 
if(root==NULL)
return;
int count=0;
int level=1;
inqueue(root);
while(!isempty())
{
bnode *t=(bnode*)dqueue();
level--;
printf(" - %d",t->key);
 
if(t->right!=NULL)
{inqueue(t->right);
 
count++;
}
if(t->left!=NULL)
{
inqueue(t->left);
count++;
}
 
if(level==0)
{
level=count;
count=0;
printf("\n");
}
}
 
 
}
void bst::level_order_spiral()
{
 
if(root==NULL)
return;
stack<struct bnode*> s1;
stack<struct bnode*> s2;
s1.push(root);
while(!s1.empty()||!s2.empty())
{
while(!s1.empty())
{
bnode *t=s1.top();
printf(" -> %d",t->key);
s1.pop();
if(t->right!=NULL)
s2.push(t->right);
if(t->left!=NULL)
s2.push(t->left);
 
 
}
while(!s2.empty())
{
bnode *t=s2.top();
printf(" -> %d",t->key);
s2.pop();
if(t->left!=NULL)
s1.push(t->right);
if(t->right!=NULL)
s1.push(t->right);
}
 
}
}
bst::~bst()
{
 
remove(root);
}
int main()
{
 
bst b;
b.insertintotree(4);
b.insertintotree(2);
b.insertintotree(3);
b.insertintotree(10);
b.insertintotree(1);
b.insertintotree(9);
b.insertintotree(5);
b.insertintotree(7);
b.insertintotree(6);
b.insertintotree(8);
 
//b.maketreemirror();
//b.heightoftree();
//b.size();
//b.printinorder();
//b.printpreorder();
//b.printpostorder();
//b.searchintree(11);
/**************************************b.pathfromroottoleaf();*/
//b.printancestoroftree(7);
//b.kthsmallestintree(6);
//b.getlevelofkey(8);
//b.totalnoofleaf();
//b.leastcommonancestorofkey(9,3);
//b.isheightbalancedtree();
//b.deletenodefromtree(4);
//b.printinorder();
//b.printroottoleafpath();
//b.printdatabetweentwokey(2,10);
//b.reverse_level_order();
b.level_order_spiral();
printf("\n");
return 0;
}
Posted by at 2 comments:
Subscribe to: Comments (Atom)