Saturday, February 26, 2011

WAP to implement Htoi Function (it Used to Convert Hexadecimal into Integer)

#include
#include
#include

void htoi(char *);

int main()
{
char *hex="0xFFFF";
htoi(hex);
return 0;
}

void htoi(char *hexstr)
{
char c;
int val=0,i;

int len=strlen(hexstr);
for(i=0;i{
c=*(hexstr+2); //pointer will points to F in case of 0xFFFF

if(c>='a' && c<='f')
{
val=val*16+(c-'a'+10);
}

else if(c>='A' && c<='F')
{
val=val*16+(c-'A'+10);
}

else
{

if(c>='0' && c<='9')
{
val=val*16+(c-'0');
}

}
printf("Val: %d \t ",val);
hexstr++;

}

printf("\n Val: %d ",val);
}

Friday, February 25, 2011

Given 3 sorted arrays Let x be an element of A, y of B, z of C.the distance b/w x,y,z =max(|x-y|,|y-z|,|z-x|) Find Touple With Minimum Distance

Given 3 sorted arrays (in ascending order). Let the arrays be A(of n1 length), B(of n2 length), C(of n3 length). Let x be an element of A, y of B, z of C. The distance between x, y and z is defined as the max(|x-y|,|y-z|,|z-x|). Find the tuple with the minimum distance?


#include
#include

#define min2(a,b) (a) < (b) ? (a) : (b)
#define min3(a,b,c) (a) < (b) ? min2(a,c) : min2(b,c)
#define max2(a,b) (a) > (b) ? (a) : (b)
#define max3(a,b,c) (a) > (b) ? max2(a,c) : max2(b,c)


typedef struct
{
int x, y, z;
}Tuple;


Tuple mindist(int a[], int b[], int c[], int m, int n, int l)
{
int i = 0;
int j = 0;
int k = 0;

int distance = INT_MAX;
Tuple out = {-1,-1,-1};


while(i < m && j < n && k < l)
{
//Find max (abs(a[i]-b[j]), abs(b[j]-c[k]), abs(a[i]-c[k])
//Advance minimum of a[i], b[j] and c[l]

int x = abs(a[i]-b[j]);
int y = abs(b[j]-c[k]);
int z = abs(a[i]-c[k]);

int d = max3(x,y,z);
if(d < distance)
{
distance = d;
out.x = i; out.y = j, out.z = k;
}

int min = min3(a[i], b[j], c[k]);

if(min == a[i])
i++;
else if(min == b[j])
j++;
else if(min == c[k])
k++;

}
return out;

}


int main()
{
int m=3, n=4, l=5;


int a[]={1,2,3};
int b[]={5,6,7,8};;
int c[]={10,11,12,13,14};

int i;

Tuple r = mindist(a,b,c,m,n,l);

printf("(%d,%d,%d)\n", r.x,r.y,r.z);
}

Given M-by-N matrix all the elements of the j-th row and k-th column to 0 if matrix[k][j] is 1

Suppose you have a (i.e. M rows and N columns), whose entries are all integers. Set all the elements of the j-th row and k-th column to 0 if matrix[k][j] is 1.

For instance, if the matrix is:

1 1 2 15
3 0 1 7
0 3 9 10
2 4 6 8

then, the result should be:

0 0 0 0
0 0 0 0
0 0 0 10
0 0 0 8



class matrix_ones
{


public static void setOnes(int[][] matrix)
{
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix[0].length;j++)
{

if (matrix[i][j] == 1)
{
row[i] = 1;
column[j] = 1;
}

}

}

// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}
}


public static void main(String a[])
{
int ar[][]=new int[][]{
{1, 1 ,2 ,15},
{3 ,0 ,1 ,7},
{0, 3, 9, 10},
{2 ,4 ,6 ,8}

};


setOnes(ar);

for (int i = 0; i <4; i++)
{
for (int j = 0; j < 4;j++)
{

System.out.println(ar[i][j]);

}
System.out.println();


}

}


}

Thursday, February 24, 2011

WAP to reverse Stack inplace

You are not allowed to use loop constructs like while, for..etc, and you can only use the following ADT functions on Stack S:
isEmpty(S)
push(S)
pop(S)

Solution:
The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

For example, let the input stack be

1 <-- top
2
3
4

First 4 is inserted at the bottom.
4 <-- top

Then 3 is inserted at the bottom
4 <-- top
3

Then 2 is inserted at the bottom
4 <-- top
3
2

Then 1 is inserted at the bottom
4 <-- top
3
2
1

So we need a function that inserts at the bottom of a stack using the above given basic stack function. //Below is a recursive function that inserts an element at the bottom of a stack.
?
void insertAtBottom(struct sNode** top_ref, int item)
{
int temp;
if(isEmpty(*top_ref))
{
push(top_ref, item);
}
else
{

/* Hold all items in Function Call Stack until we reach end of
the stack. When the stack becomes empty, the isEmpty(*top_ref)
becomes true, the above if part is executed and the item is
inserted at the bottom */
temp = pop(top_ref);
insertAtBottom(top_ref, item);

/* Once the item is inserted at the bottom, push all the
items held in Function Call Stack */
push(top_ref, temp);
}
}

//Below is the function that reverses the given stack using insertAtBottom()
?
void reverse(struct sNode** top_ref)
{
int temp;
if(!isEmpty(*top_ref))
{

/* Hold all items in Function Call Stack until we reach end of
the stack */
temp = pop(top_ref);
reverse(top_ref);

/* Insert all the items (held in Function Call Stack) one by one
from the bottom to top. Every item is inserted at the bottom */
insertAtBottom(top_ref, temp);
}
}

//Below is a complete running program for testing above functions.


#include
#include
#define bool int



/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};

/* Function Prototypes */
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);



void insertAtBottom(struct sNode** top_ref, int item)
{
int temp;
if(isEmpty(*top_ref))
{
printf(" yes : ");
push(top_ref, item);
}
else
{

/* Hold all items in Function Call Stack until we reach end of
the stack. When the stack becomes empty, the isEmpty(*top_ref)
becomes true, the above if part is executed and the item is
inserted at the bottom */
temp = pop(top_ref);
insertAtBottom(top_ref, item);

/* Once the item is inserted at the bottom, push all the
items held in Function Call Stack */
push(top_ref, temp);
}
}


void reverse(struct sNode** top_ref)
{
int temp;
if(!isEmpty(*top_ref))
{

/* Hold all items in Function Call Stack until we reach end of
the stack */
temp = pop(top_ref);
printf(" %d ", temp);
reverse(top_ref);

/* Insert all the items (held in Function Call Stack) one by one
from the bottom to top. Every item is inserted at the bottom */
insertAtBottom(top_ref, temp);
}
}

/* Driveer program to test above functions */
int main()
{
struct sNode *s = NULL;
push(&s, 4);
push(&s, 3);
push(&s, 2);
push(&s, 1);

printf("\n Original Stack ");
print(s);
reverse(&s);
printf("\n Reversed Stack ");
print(s);
getchar();
}

/* Function to check if the stack is empty */
bool isEmpty(struct sNode* top)
{
return (top == NULL)? 1 : 0;
}

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_node == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);

/* move the head to point to the new node */
(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;

/*If stack is empty then error */
if(*top_ref == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

/* Functrion to pront a linked list */
void print(struct sNode* top)
{
printf("\n");
while(top != NULL)
{
printf(" %d ", top->data);
top = top->next;
}
}


/*

void reverse(stack s){
if(empty(s)){
return ;
}
func(s);
k=s.pop();
reverse(s);
push(&s,k);
}

void func(stack s){
if(empty(s)){
return ;
}
k=s.pop();
if(!empty(s)){
temp=s.pop();
push(&s,k);
push(&s,temp);
}
else{
push(&s,k);
}
}

*/

Run Here https://ideone.com/pCoDm
Source Geesk4Geeks

Given an array and an integer k, find the maximum for each and every contiguous sub array of size k.

Sample Input :
1 2 3 1 4 5 2 3 6
3 [ value of k ]

Sample Output :
3
3
4
5
5
5
6



#include

using namespace std;

int max(int a[],int r,int pos)
{
int m=a[pos];
int i=0;
for(i=pos+1;i {
if(a[i]>m)
{
m=a[i];
}

}

return m;
}
void maxi(int a[],int r,int pos)
{
int m;

if(pos > 10-r ) return ;
m=max(a,3,pos);
cout< maxi(a,r,pos+1);
}
int main()
{
int a[]={1, 2, 3 ,1 ,4 ,5 ,2 ,3 ,6};

int pos=0;

maxi(a,3,pos);


return 1;
}

Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the

#include
#include
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*
Given a tree and a sum, return true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum.

Strategy: subtract the node value from the sum when recurring down,
and check to see if the sum is 0 when you run out of tree.
*/
bool hasPathSum(struct node* node, int sum)
{
/* return true if we run out of tree and sum==0 */
if (node == NULL)
{
return(sum == 0);
}
else
{
/* otherwise check both subtrees */
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}

/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newnode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{

int sum = 21;

/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
*/
struct node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(2);
root->left->left = newnode(3);
root->left->right = newnode(5);
root->right->left = newnode(2);

if(hasPathSum(root, sum))
printf("There is a root-to-leaf path with sum %d", sum);
else
printf("There is no root-to-leaf path with sum %d", sum);

getchar();
return 0;
}

WAP to Convert Zig Zag level order Traversal of Tree to Doubly Linked List

Method 1 using 2-Stack--Need Modification RunTime Error But Logic is 100% Correct

#include
#include

/* Structure for Tree */
struct node
{
struct node* left;
struct node* right;
int data;
};

/* structure of a stack node */
struct sNode
{
struct node *t;
struct sNode *next;
};

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct node* newtNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct node *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref);

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}

/* Function to pop an item from stack*/
struct node *pop(struct sNode** top_ref)
{
struct node *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}

void Insert(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->left= NULL;

/* link the old list off the new node */
new_node->right= (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->left= new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}

void Spiral(struct node* root)
{
struct node *head;//for DLL
struct sNode *node1;
struct sNode *node2;
struct node *temp;


if(root == NULL)
return;

push(&node1,root);


while(!isEmpty(node1) && !isEmpty(node2))
{

while(!isEmpty(node1))
{
temp = pop(&node1);
Insert(&head,temp->data);
push(&node2,temp->right);
push(&node2,temp->left);
}
//temp=NULL;

while(!isEmpty(node2))
{
temp = pop(&node2);
Insert(&head,temp->data);
push(&node1,temp -> left);
push(&node1,temp -> right);
}

}

}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Utility function to print a linked list */
void printList(struct node* head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->right;
}
printf("\n");
}

/* Driver function to test above functions */
int main()
{
struct node *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
root->right->left = newtNode(6);
root->right->right = newtNode(7);

Spiral(root);
printList(root);

getchar();
}

TC O(n)
Sc (2n) if Stack Space is considered else O(1)
Run Here https://ideone.com/cyPM5

Method 2 Using Recursion(Bottom Up Tree Traversal)


#include
#include

struct node
{
struct node *left;
struct node *right;
int data;

};

struct node *rslt;//Global structure pointer..it point to head of doubly linked list


int height(struct node* head)
{

if(head==NULL)
return 0;

if(head->left==NULL && head->right==NULL)
return 0;

int lh=height(head->left);
int rh=height(head->right);

return lh>rh?(lh+1):(rh+1);

}

struct node* appnd(struct node *a,struct node *b)
{
if(a==NULL)return b;
if(b==NULL)return a;

struct node* result=a;
while(a->left!=NULL)
a=a->left;

a->left=b;
b->right=a;

b->left=NULL;

return result;

}

void printGivenLevel(struct node* head,int level,int ltr)
{
if(head==NULL)
return;

if(level==0)
{
appnd(rslt, head);
rslt = head;
}

if(level>0)
{

if(ltr)
{
printGivenLevel(head->left,level-1,ltr);
printGivenLevel(head->right,level-1,ltr);
}
else
{
printGivenLevel(head->right,level-1,ltr);
printGivenLevel(head->left,level-1,ltr);

}
}

}

void printGivenOrder(struct node* head)
{

int i=0;
int ltr=0;

for(i=height(head); i >= 0; i--)
{

printGivenLevel(head,i,ltr);
ltr=~ltr;
}

}

struct node* NewNode(int data)
{
struct node* tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=data;
tmp->left=NULL;
tmp->right=NULL;
return tmp;

}

void printList(struct node* node)
{
struct node* current=node;
while(current)
{
printf("%d ----> ",current->data);
current=current->right;
}


}

int main()
{
struct node* start=NULL;

start=NewNode(1);
start->left=NewNode(2);
start->right=NewNode(3);
start->left->left=NewNode(4);
start->left->right=NewNode(5);
start->right->left=NewNode(6);
start->right->right=NewNode(7);

printGivenOrder(start);

printList(rslt);

return 0;

}
TC O(n^2)....need Modification..??
Sc O(1)
Run Here https://ideone.com/y9Ssb

WAP for Sorting Doubly Linked List

/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}


struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;

/* Base cases */
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 = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}

int Length(struct node* head)
{
int count = 0;
struct node* current = head;
while (current != NULL)
{
count++;
current=current->next;
}
return(count);
}
// to split list in to two equal part using lenth function
void FrontBackSplit(struct node* source,struct node** frontRef, struct node** backRef)
{
int len = Length(source);
int i;
struct node* current = source;

if (len < 2) {
*frontRef = source;
*backRef = NULL;
}
else {
int hopCount = (len-1)/2; //(figured these with a few drawings)
for (i = 0; icurrent = current->next;
}
// Now cut at current
*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}


/* sorts the linked list by changing next pointers (not data) */
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 */
FrontBackSplit(head, &a, &b);

/* Recursively sort the sublists */
MergeSort(&a);
MergeSort(&b);

/* answer = merge the two sorted lists together */
*headRef = SortedMerge(a, b);
}




/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 2);
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 2);

printf("\n Original Linked list ");
printList(head);

MergeSort(&head);


printf("\nsorted Doubly Linked list ");
printList(head);


getchar();
}


Run Here https://ideone.com/dESuB

Wednesday, February 23, 2011

WAP tp print Combination of given string

#include
#include
#include

void mycombination(char const * const s, int l, int *arr, int index, int start, int d)
{
int i,j;
if (index >= d)
return ;
for (j = start ; j < l ; j++)
{
arr[index] = j;
if (index == d-1)
{
for (i=0;i putchar('\n');
}
else
mycomb_ultrabad(s,l,arr,index+1,j+1,d);
}
return ;
}

int main()
{
int i,d;
char s[4]={'a','v','i'};
d = strlen(s);
int arr[d+1];
for (i=0;i {
mycomb_ultrabad(s, d, arr,0,0,d-i);
}
return 0;
}

WAP to Swap Two NIbble in Byte

struct nibbles
{
int lnibble:4;
int unibble:4;
};
union swap
{
char byte;
struct nibbles nb;
};
int main()
{
union swap sw;
int temp;
sw.byte=0x12;
printf("Before swap:%x\n",sw.byte);
temp=sw.nb.lnibble;
sw.nb.lnibble=sw.nb.unibble;
sw.nb.unibble=temp;
printf("After swap:%x",sw.byte);
}