Thursday, September 1, 2011
Find common elements in an Array
Suppose two arrays are given , we need to find the common elements. case 1 : two arrays are sorted . case 2 : two arrays are unsorted . Answer : case 1 : Do a search as we just move through them as we would merge them. As they are sorted , while searching the element in the 2nd array with the element in the 1st array , we can store the index where it the 1st array element exceeds the 2nd array element. Such that the next search can begin at this stored index. case 2 : Hash both the arrays , wherever collision occurs its a common element.
Tree Traversals without using Recursion
/* Inorder traversal with out using recursion */
int top = -1;
struct node *arr[100];
struct node
{
char data;
struct node *left;
struct node *right;
int visited;
};
static int postIndex = 6;
int search(char in[],int inStrt, int inEnd, char data);
struct node *buildTree(char in[], char pre[], int inStrt, int inEnd);
struct node* newNode(char data);
int search(char arr[], int inStrt, int inEnd, char data)
{
int i;
for(i = inStrt; i <= inEnd; i++)
{
if(arr[i] == data)
{
return i;
}
}
}
struct node *buildTree(char post[], char in[], int inStrt, int inEnd)
{
if(inStrt > inEnd)
return NULL;
// pick the last node from post-order traversal
// which happens to be the root
struct node *tNode = newNode(post[postIndex--]);
// if this node has no childern then return
if(inStrt == inEnd)
return tNode;
// find the index of this node in in-order traversal
int inIndex = search(in, inStrt, inEnd, tNode->data);
tNode->right = buildTree(post, in, inIndex+1, inEnd);
tNode->left = buildTree(post, in, inStrt, inIndex -1);
return tNode;
}
struct node* newNode(char data)
{
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->visited = 0;
return node;
}
void push (struct node *root)
{
arr[++top] = root;
}
struct node *pop(void)
{
return arr[top--];
}
/* Inorder traversal without using recursion */
void printInorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return;
// Push all node onto the stack
while(root != NULL)
{
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
printf("%c \t", temp->data);
temp = temp->right;
while(temp != NULL)
{
push(temp);
temp = temp->left;
}
}
printf("top inorder : %d\n", top);
}
/* Pre-order traversal without using recursion */
void printPreorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return 0;
while(root != NULL)
{
printf("%c \t", root->data);
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
temp = temp->right;
while(temp != NULL)
{
printf("%c\t", temp->data);
push(temp);
temp= temp->left;
}
}
}
/* Post-order traversal without using recursion */
void printPostorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return 0;
while(root != NULL)
{
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
push(temp);
//printf("%c %d\n", temp->data, temp->visited);
temp = temp->right;
while(temp != NULL && temp->visited == 0)
{
temp->visited = 1;
push(temp);
temp= temp->left;
}
temp = pop();
printf("%c\t", temp->data);
}
}
main()
{
char post[] = {'C', 'F', 'G', 'D', 'B', 'E', 'A'};
char in[] = {'C', 'B', 'F', 'D', 'G', 'A', 'E'};
int len = sizeof(post)/sizeof(post[0]);
int i;
struct node *root = buildTree(post, in, 0, len-1);
printf("Print the in order traversal\n");
printInorder(root);
printf("Print the pre-order traversal\n");
printPreorder(root);
printf("\nPrint the post-order traversal\n");
printPostorder(root);
}
Find the 8 digit number
Find a 8-digit number, where the first figure defines the count of zeros in this number, the second figure the count of numeral 1 in this number and so on.... Start with 8 digit number, starting from left to right, first digit indicate number of 0's in 8 digit number, second digit indicate number of 1's in 8 digit number. Similary 7th digit indicate number of 7's in 8 digit number. 70000000 //8 digit number 7 indicate number of 0's in the number. 70000001 //As number of 7's = 1 so 7th place is 1 60000001 //As due to 1 on 7th place number of zeros = 6 60000010 //As 6 is present so 7th place, number of 6's = 1; number of 7's = 0 61000010 //As 1 is present on 7th place ; number of 1's = 1 so 2nd place there should be 1 51000010 //As number of 0's = 5 51000100 //As 5 is present so 6th place is 1 number of 6's = 0; number of 7's = 0 52000100 //As number of 1's = 2 52100100 //As 2 is present on 1st place so 3rd place is 1 42100100 // As number of 0's = 4 so 1st place is 4 42101000 // As 4 is present so 5th place is 1; number of 5's, 6's and 7's = 0; We got the answer as 4210 1000.
Reverse the order of words in a string
For example: Input string is " This is my first post"
Output string will be "post first my is This";
first reverse each word.(complexity o(n))
finally reverse the whole string.(complexity O(n))
total O(n)+O(n) = O(n)
How about pushing tokens using stack and then popping all.
Number of Trailing zeros in n!
We use the fact that zeros occurs only when multiple of 5 gets multiplied to an even number. So it boils down to a problem of finding power of 5 in prime factorization of n!.
int countOfPrimeFactors(int n,int k) // This method gives count of prime factors of k for a given n in n! .
{
int count=0;
while(n>=k)
{
count+=n/k;
k= k*k;
}
return count;
}
main()
{
int n = 20;
printf("Number of zeros : %d\n", countOfPrimeFactors(n,5)); // Find prime factors of 5 in n! .
}
Construct Tree from given Inorder and Preorder traversals
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.
A
/ \
/ \
D B E F C
We recursively follow above steps and get the following tree.
A
/ \
/ \
B C
/ \ /
/ \ /
D E F
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
/* program to construct tree using inorder and preorder traversals */
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
char data;
struct node* left;
struct node* right;
};
/* Prototypes for utility functions */
int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);
/* Recursive function to construct binary of size len from
Inorder traversal in[] and Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1. The function doesn't
do any error checking for cases where inorder and preorder
do not form a tree */
struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;
if(inStrt > inEnd)
return NULL;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if(inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode->data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = buildTree(in, pre, inStrt, inIndex-1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd);
return tNode;
}
/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(char arr[], int strt, int end, char value)
{
int i;
for(i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(char data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* This funtcion is here just to test buildTree() */
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%c ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Driver program to test above functions */
int main()
{
char in[] = {'D', 'B', 'E', 'A', 'F', 'C'};
char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};
int len = sizeof(in)/sizeof(in[0]);
struct node *root = buildTree(in, pre, 0, len - 1);
/* Let us test the built tree by printing Insorder traversal */
printf("\n Inorder traversal of the constructed tree is \n");
printInorder(root);
getchar();
}
Time Complexity: O(n^2). Worst case occurs when tree is left skewed. Example Preorder and Inorder traversals for worst case are {A, B, C, D} and {D, C, B, A}.
Subscribe to:
Comments (Atom)