Solution - #104 Project Euler
Posted on April 4, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
//p104
// Find the Fibonacci sequence for which the first nine digits and the last nine digits are 1-9 pandigital
#include
#include
char number_string[100000];
char isPandigital( unsigned long int num )
{
if ( num < 123456789 )
{
return 0;
}
char num_of_unique_digits = 0;
char number_array[9];
unsigned long int temp = num;
int i;
int j;
for ( i = 0; i < 9; i++ )
[Read More]Simplified IP Addressing
Posted on March 27, 2010
(Last modified on August 7, 2020)
| 13 minutes
| Kinshuk Chandra
Basics
The first question concerns what constitutes a Class A, or a Class B, etc. network. Novices have trouble remembering where each class begins and ends. Table 3 shows a schema to help with this. First, let’s discuss some basics of binary numbers.
A byte is a grouping of eight binary bits. Since a binary bit is either a 0 or a 1, a byte consists of eight 0s and/or 1s.
[Read More]Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store values from 1.....N.
Posted on March 6, 2010
(Last modified on August 7, 2020)
| 13 minutes
| Kinshuk Chandra
Basics
The first question concerns what constitutes a Class A, or a Class B, etc. network. Novices have trouble remembering where each class begins and ends. Table 3 shows a schema to help with this. First, let’s discuss some basics of binary numbers.
A byte is a grouping of eight binary bits. Since a binary bit is either a 0 or a 1, a byte consists of eight 0s and/or 1s.
[Read More]Some cardinals
Posted on March 4, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A binary tree with n nodes has exactly n+1 null nodes
If there are n nodes, there exist 2^n-n different trees.
No. of nodes in a full binary tree is of the form 2^k - 1
Bucket size is 1, when the overlapping and collision occur at same time
Because If there is only one entry possible in the bucket, when the collision occurs,
[Read More]Tree
Posted on January 29, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Tree are of various types:
- BST
BST - Index
Posted on January 29, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Common Operations on BST Understanding functions of BST – insert, size and traversal Deleting a node from BST Implementing a BST in C Traversals are covered seperately below.
Traversal in BST: Inorder, pre order and post order traversal(recursive approach)
Inorder, pre order and post order traversal(iterative approach)
Level order traversal
Threaded binary tree
DFS and BFS on tree
Given the expression tree, calculate the expression
Construct a tree, given its inorder and pre-order
[Read More]Threaded binary tree
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.
[Read More]Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
For Inorder And Preorder traversals
inorder = g d h b e i a f j c preorder = a b d g h e i c f j
Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, “a” is the root of the tree; “gdhbei” are in the left subtree; “fjc” are in the right subtree. “b” is the next root; “gdh” are in the left subtree; “ei” are in the right subtree.
[Read More]Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The code below prints the paranthesized form of a tree.
**print_infix_exp(node * root)** { if(root) { printf("("); infix_exp(root->left); printf(root->data); infix_exp(root->right); printf(")"); } }
Creating a binary tree for a postfix expression
`
*node create_tree(char postfix[])
{
node *temp, *st[100];
int i,k;
char symbol;
for(i=k=0; (symbol = postfix[i])!=’\0’; i++)
{
temp = (node *) malloc(sizeof(struct node));//temp = getnode();
temp->value = symbol;
temp->left = temp->right = NULL;
if(isalnum(symbol))
st[k++] = temp;
[Read More]First / Lowest common ancestor (LCA) of 2 node in binary tree
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem
Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Case 2- What will you do if it is Binary search tree
Example
So for example look into below figure:
So for node 4 and 14, LCA is 8.
[Read More]