Month: November 2013
Pointer to array of pointer to string in c programming
Example of Pointer to array of pointer to string:
What will be output if you will execute following code?
#include<stdio.h>
0;
Multilevel pointers in c programming
Multilevel pointers: A pointer is pointer to another pointer which can be pointer to others pointers and so on is know as multilevel pointers. We can have any level of pointers.
Examples of multilevel pointers in c:
#include<stdio.h>
0;
#include<stdio.h>
0;
#include<stdio.h>
0;
Explanations:
Pointer to union in c programming
Pointer to structure: A pointer which is pointing to a structure is know as pointer to structure.
Examples of pointers to structure:
#include<stdio.h>
0;
Pointer to structure in c programming
Pointer to structure: A pointer which is pointing to a structure is know as pointer to structure.
Examples of pointers to structure:
#include<stdio.h>
}cus={“A.Kumar”,”H-2″,456003},*p=&cus;
return 0;
Pointer to array of string in c programming
A pointer which pointing to an array which content is string, is known as pointer to array of strings.
Pointer to array of function in c
In other word we can say pointer to array of functions is a pointer which is pointing to an array which contents are pointers to a function.
Examples of pointer to array of function:
#include<stdio.h>
return 0;
Pointer to function in c programming
Function pointer definition: A pointer which keeps address of a function is known as function pointer.
Examples of function pointers in c:
#include<stdio.h>
how google search engine works
Quote Posted on Updated on
Google runs on a distributed network of thousands of low-cost computers and can therefore carry out fast parallel processing. Parallel processing is a method of computation in which many calculations can be performed simultaneously, significantly speeding up data processing. Google has three distinct parts:
-
Googlebot, a web crawler that finds and fetches web pages.
-
The indexer that sorts every word on every page
-
and stores the resulting index of words in a huge database.
-
The query processor, which compares your search query to the
-
index and recommends the documents that it considers most relevant.
Let’s take a closer look at each part.
1. Googlebot, Google’s Web Crawler
Googlebot is Google’s web crawling robot, which finds and retrieves pages on the web and hands them off to the
Google indexer. It’s easy to imagine Googlebot as a little spider scurrying across the strands of cyberspace, but
in reality Googlebot doesn’t traverse the web at all. It functions much like your web browser, by sending a
request to a web server for a web page, downloading the entire page, then handing it off to Google’s indexer.
Googlebot consists of many computers requesting and fetching pages much more quickly
than you can with your web browser. In fact, Googlebot can request thousands of different pages simultaneously.
To avoid overwhelming web servers, or crowding out requests from human users,
Googlebot deliberately makes
requests of each individual web server more slowly than it’s capable of doing.
Googlebot finds pages in two ways: through an add URL form, www.google.com/addurl.html, and through
finding links by crawling the web
The combination of the two types of crawls allows Google to both make efficient use of its resources
and keep its index reasonably current.
1.deep crawling
2.fresh crawls
When Googlebot fetches a page, it culls all the links appearing on the page and adds them to a
queue for subsequent crawling. Googlebot tends to encounter little spam because most web
authors link only to what they believe are high-quality pages. By harvesting links from every page it
encounters, Googlebot can quickly build a list of links that can cover broad reaches of the web.
This technique, known as deep crawling, also allows Googlebot to probe deep within individual
sites. Because of their massive scale, deep crawls can reach almost every page in the web. Because
the web is vast, this can take some time, so some pages may be crawled only once a month.
Although its function is simple, Googlebot must be programmed to handle several challenges. First, since
Googlebot sends out simultaneous requests for thousands of pages, the queue of “visit soon” URLs must be
constantly examined and compared with URLs already in Google’s index. Duplicates in the queue must be
eliminated to prevent Googlebot from fetching the same page again. Googlebot must determine how often to
revisit a page.
To keep the index current, Google continuously recrawls popular frequently changing web pages
at a rate roughly proportional to how often the pages change. Such crawls keep an index current
and are known as fresh crawls. Newspaper pages are downloaded daily, pages with stock quotes
are downloaded much more frequently. Of course, fresh crawls return fewer pages than the deep
crawl.
2. Google’s Indexer
Googlebot gives the indexer the full text of the pages it finds. These pages are stored in Google’s
index database.
This index is sorted alphabetically by search term, with each index entry storing a
list of documents in which the term appears and the location within the text where it occurs. This
data structure allows rapid access to documents that contain user query terms.
To improve search performance, Google ignores (doesn’t index) common words called stop
words (such as the, is, on, or, of, how, why, as well as certain single digits and single letters). Stop
words are so common that they do little to narrow a search, and therefore they can safely be
discarded. The indexer also ignores some punctuation and multiple spaces, as well as converting
all letters to lowercase, to improve Google’s performance.
3. Google’s Query Processor
The query processor has several parts, including the user interface (search box), the “engine” that
evaluates queries and matches them to relevant documents, and the results formatter.
PageRank is Google’s system for ranking web pages. A page with a higher PageRank is deemed more
important and is more likely to be listed above a page with a lower PageRank.
Google considers over a hundred factors in computing a PageRank and determining which
documents are most relevant to a query.
including the popularity of the page.
the position and size of the search terms within the page.
the proximity of the search terms to one another on the page.
Google also applies machine-learning techniques to improve its performance automatically by learning
relationships and associations within the stored data. For example, the spelling-correcting system uses such
techniques to figure out likely alternative spellings. Google closely guards the formulas it uses to calculate
relevance; they’re tweaked to improve quality and performance, and to outwit the latest devious techniques
used by spammers.
Indexing the full text of the web allows Google to go beyond simply matching single search terms.
Google gives more priority to pages that have search terms near each other and in the same order
as the query. Google can also match multi-word phrases and sentences. Since Google indexes
HTML code in addition to the text on the page, users can restrict searches on the basis of where
query words appear, e.g., in the title, in the URL, in the body,
C programms asked in most interviews
Programs
1. Write a program to find factorial of the given number…
2. Write a program to check whether the given number is even or odd.
3. Write a program to swap two numbers using a temporary variable.
4. Write a program to swap two numbers without using a temporary variable.
5. Write a program to swap two numbers using bitwise operators. Read the rest of this entry »
System programming in c language..
Programming in C
UNIX System Calls and Subroutines using C
Go to the link.
https://csekapil.wordpress.com/system-programming-in-c-language/
Implement filter in c
code :
#include<unistd.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int n,a,b,temp;
char str[20];
while(fgets(str,20,stdin))
{
//str[n]=”;
if(sscanf(str,”%d%d%d”,&a,&b,&temp)==2)
{
sprintf(str,”%d\n”,a+b);
n=strlen(str);
if(write(STDOUT_FILENO,str,n)!=n)
{
fprintf(stderr,”Write error!\n”);
exit(0);
}
}
else
{
if(write(STDOUT_FILENO,”INVALID ARGS\n”,13)!=13)
{
fprintf(stderr,”Write error!\n”);
exit(0);
}
}
}
return 0;
}
Read the rest of this entry »
Review tree code for interviews quickly
Given a binary tree, print out all of its root-to-leaf paths one per line
————————————————————————-
void printPathsRecur(struct node* node, int path[], int pathLen)
{
if (node==NULL) return;
/* append this node to the path array */
path[pathLen] = node->data;
pathLen++;
/* it’s a leaf, so print the path that led to here */
if (node->left==NULL && node->right==NULL)
{
printArray(path, pathLen);
}
else
{
/* otherwise try both subtrees */
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
Write an Efficient C Function to Convert a Binary Tree into its Mirror Tree-
—————————————————————————
void mirror(struct node* node)
{
if (node==NULL)
return;
else
{
struct node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
Find the Maximum Depth or Height of a Tree-
——————————————
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
Determine if Two Trees are Identical-
————————————
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
return 0;
}
Calculate Size of a tree-
————————
int size(struct node* node)
{
if (node==NULL)
return 0;
else
return(size(node->left) + 1 + size(node->right));
}
Lowest Common Ancestor in a Binary Search Tree-
———————————————-
* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2)
{
if (root == NULL) return NULL;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (root->data > n1 && root->data > n2)
return lca(root->left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (root->data < n1 && root->data < n2)
return lca(root->right, n1, n2);
return root;
}
find minimum in BST-
——————-
int minValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return(current->data);
}
Level Order Traversal-
———————
Recursive Solution-
——————
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return;
if(level == 1)
printf(“%d “, root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
void printLevelOrder_recursive(struct node* root)
{
int h = height(root);
int i;
for(i=1; i<=h; i++)
printGivenLevel(root, i);
}
Non Recursive Solution-
———————-
void level_trav(struct node *root)
{
struct node *ptr = root;
if( ptr==NULL )
{
printf(“Tree is empty\n”);
return;
}
insert_queue(ptr);
while( !queue_empty() ) /*Loop until queue is not empty*/
{
ptr=del_queue();
printf(“%d “,ptr->info);
if(ptr->lchild!=NULL)
insert_queue(ptr->lchild);
if(ptr->rchild!=NULL)
insert_queue(ptr->rchild);
}
printf(“\n”);
}
Get Leaf Count-
————–
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
check if the tree is BST or not-
——————————-
Using Inorder Traversal-
———————–
Do In-Order Traversal of the given tree and store the result in a temp array.
Check if the temp array is sorted in ascending order, if it is, then the tree is BST.
We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node.
If the value of the currently visited node is less than the previous value, then tree is not BST.
bool isBST(struct node* root)
{
static struct node *prev = NULL;
// traverse the tree in inorder fashion and keep track of prev node
if (root)
{
if (!isBST(root->left))
return false;
// Allows only distinct valued nodes
if (prev != NULL && root->data <= prev->data)
return false;
prev = root;
return isBST(root->right);
}
return true;
}
Check for Children Sum Property in a Binary Tree- if the sum of children’s data is equal to the current node data
————————————————
int isSumProperty(struct node* node)
{
if(node == NULL ||
(node->left == NULL && node->right == NULL))
return 1;
else
{
if(node->left!=NULL && node->right==NULL ||node->left==NULL && node->right!=NULL )
return false;
else if((node->data == node->left->data + node->right->data))
return ((isSumProperty(node->left) && (isSumProperty(node->right));
else
return 0;
}
}
Diameter of Tree-
—————-
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lheigth = height(node->left);
int rheigth = height(node->right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
int diameter(struct node * tree)
{
/* base case where tree is empty */
if (tree == 0)
return 0;
/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);
/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
How to determine if a binary tree is height-balanced?-
—————————————————–
bool isBalanced(struct node *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if(root == NULL)
return 1;
/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);
if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
InOrder Non Recursive Traversal-
——————————-
void nrec_in(struct node *root)
{
struct node *ptr=root;
if( ptr==NULL )
{
printf(“Tree is empty\n”);
return;
}
while(1)
{
while(ptr->lchild!=NULL )
{
push_stack(ptr);
ptr = ptr->lchild;
}
while( ptr->rchild==NULL )
{
printf(“%d “,ptr->info);
if(stack_empty())
return;
ptr = pop_stack();
}
printf(“%d “,ptr->info);
ptr = ptr->rchild;
}
printf(“\n”);
}
Root to leaf path sum equal to a given number-
———————————————
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
{
bool ans = 0;
/* otherwise check both subtrees */
int subSum = sum – node->data;
/* If we reach a leaf node and sum becomes 0 then return true*/
if ( subSum == 0 && node->left == NULL && node->right == NULL )
return 1;
if(node->left)
ans = ans || hasPathSum(node->left, subSum);
if(node->right)
ans = ans || hasPathSum(node->right, subSum);
return ans;
}
}
Double Tree- To create Double tree of the given tree, create a new duplicate for each node, and insert the duplicate as the left child of the original node.
———–
void doubleTree(struct node* node)
{
struct node* oldLeft;
if (node==NULL) return;
/* do the subtrees */
doubleTree(node->left);
doubleTree(node->right);
/* duplicate this node to its left */
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;
}
Maximum width of the tree-
————————-
int getWidth(struct node* root, int level)
{
if(root == NULL)
return 0;
if(level == 1)
return 1;
else if (level > 1)
return getWidth(root->left, level-1) +
getWidth(root->right, level-1);
}
int getMaxWidth(struct node* root)
{
int maxWidth = 0;
int width;
int h = height(root);
int i;
/* Get width of each level and compare
the width with maximum width so far */
for(i=1; i<=h; i++)
{
width = getWidth(root, i);
if(width > maxWidth)
maxWidth = width;
}
return maxWidth;
}
Total number of possible Binary Search Trees with n keys-
========================================================
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!
Sorted order printing of a given array that represents a BST-
===========================================================
level order traversal
void printSorted(int arr[], int start, int end)
{
if(start > end)
return;
// print left subtree
printSorted(arr, start*2 + 1, end);
// print root
printf(“%d “, arr[start]);
// print right subtree
printSorted(arr, start*2 + 2, end);
}
int main()
{
int arr[] = {4, 2, 5, 1, 3};
int arr_size = sizeof(arr)/sizeof(int);
printSorted(arr, 0, arr_size-1);
getchar();
return 0;
}
Complexity = O(n);
Uses of Tree-
============
following are the common uses of tree.
1. Manipulate hierarchical data.
2. Make information easy to search (see tree traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for visual effects.
5. Router algorithms
Get Level of a node in a Binary Tree-
====================================
/* Helper function for getLevel(). It returns level of the data if data is
present in tree, otherwise returns 0.*/
int getLevelUtil(struct node *node, int data, int level)
{
if (node == NULL)
return 0;
if (node->data == data)
return level;
int downlevel = getLevelUtil(node->left, data, level+1);
if (downlevel != 0)
return downlevel;
downlevel = getLevelUtil(node->right, data, level+1);
return downlevel;
}
/* Returns level of given data value */
int getLevel(struct node *node, int data)
{
return getLevelUtil(node,data,1);
}
Print Ancestors of a given node in Binary Tree-
==============================================
/* If target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
bool printAncestors(struct node *root, int target)
{
/* base cases */
if (root == NULL)
return false;
if (root->data == target)
return true;
/* If target is present in either left or right subtree of this node,
then print this node */
if ( printAncestors(root->left, target) ||
printAncestors(root->right, target) )
{
cout << root->data << ” “;
return true;
}
/* Else return false */
return false;
}
Print BST keys in the given range-
=================================
void Print(struct node *root, int k1, int k2)
{
/* base case */
if ( NULL == root )
return;
/* Since the desired o/p is sorted, recurse for left subtree first
If root->data is greater than k1, then only we can get o/p keys
in left subtree */
if ( k1 < root->data )
Print(root->left, k1, k2);
/* if root’s data lies in range, then prints root’s data */
if ( k1 <= root->data && k2 >= root->data )
printf(“%d “, root->data );
/* If root->data is smaller than k2, then only we can get o/p keys
in right subtree */
if ( k2 > root->data )
Print(root->right, k1, k2);
}
Check if a given Binary Tree is SumTree-
=======================================
A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree
/* returns 1 if sum property holds for the given
node and both of its children */
int isSumTree(struct node* node)
{
int ls, rs;
/* If node is NULL or it’s a leaf node then
return true */
if(node == NULL ||
(node->left == NULL && node->right == NULL))
return 1;
/* Get sum of nodes in left and right subtrees */
ls = sum(node->left);
rs = sum(node->right);
/* if the node and both of its children satisfy the
property return 1 else 0*/
if((node->data == ls + rs)&&
isSumTree(node->left) &&
isSumTree(node->right))
return 1;
return 0;
}
http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
Check if a binary tree is subtree of another binary tree-
========================================================
bool areIdentical(struct node * root1, struct node *root2)
{
/* base cases */
if(root1 == NULL && root2 == NULL)
return true;
if(root1 == NULL || root2 == NULL)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right) );
}
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{
/* base cases */
if (S == NULL)
return true;
if (T == NULL)
return false;
/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;
/* If the tree with root as current node doesn’t match then
try left and right subtrees one by one */
return isSubtree(T->left, S) ||
isSubtree(T->right, S);
}
Sorted Array to Balanced BST-
============================
/* A function that constructs Balanced Binary Search Tree from a sorted array */
struct TNode* sortedArrayToBST(int arr[], int start, int end)
{
/* Base Case */
if (start > end)
return NULL;
/* Get the middle element and make it root */
int mid = (start + end)/2;
struct TNode *root = newNode(arr[mid]);
/* Recursively construct the left subtree and make it
left child of root */
root->left = sortedArrayToBST(arr, start, mid-1);
/* Recursively construct the right subtree and make it
right child of root */
root->right = sortedArrayToBST(arr, mid+1, end);
return root;
}
Convert a given tree to its Sum Tree-
====================================
10
/ \
-2 6
/ \ / \
8 -4 7 5
should be changed to
20(4-2+12+6)
/ \
4(8-4) 12(7+5)
/ \ / \
0 0 0 0
// Convert a given tree to a tree where every node contains sum of values of
// nodes in left and right subtrees in the original tree
int toSumTree(struct node *node)
{
// Base case
if(node == NULL)
return 0;
// Store the old value
int old_val = node->data;
// Recursively call for left and right subtrees and store the sum as
// new value of this node
node->data = toSumTree(node->left) + toSumTree(node->right);
// Return the sum of values of nodes in left and right subtrees and
// old_value of this node
return node->data + old_val;
}
root to leaf maximum sum-
========================
sum=0;
int findmaxsum(treenode *root,int sum)
{
if(!root) return sum;
else
return max(findmaxsum(root->left,root->data),findmaxsum(root->right,root->data));
}
LISS-
=====
Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set
if there is no edge between any two nodes of the subset. For example, consider the following binary tree. The largest independent
set(LIS) is {10, 40, 60, 70, 80} and size of the LIS is 5.
10
/ \
20 30
/ \ \
40 50 60
/ \
70 80
LISS(X) = MAX { (1 + sum of LISS for all grandchildren of X),
(sum of LISS for all children of X) }
int LISS(struct node *root)
{
if (root == NULL)
return 0;
// Caculate size excluding the current node
int size_excl = LISS(root->left) + LISS(root->right);
// Calculate size including the current node
int size_incl = 1;
if (root->left)
size_incl += LISS(root->left->left) + LISS(root->left->right);
if (root->right)
size_incl += LISS(root->right->left) + LISS(root->right->right);
// Return the maximum of two sizes
return max(size_incl, size_excl);
}
Segment Tree-
============
This is used when number of queries and updates are equal and in large number.
and we can perform all the operations multiple times in log2(n) time once the tree is constructed O(n) time.
(36)[0,5]
/ \
(9)[0,2] (27)[3,5]
/ \ / \
(4)[0,1] (5)[2,2] (16)[3,4] (11) [5,5]
/ \ / \
(1) (3) (7) (9)
[0,0] [1,1] [3,3] [4,4]
arr[]={1,3,5,7,9,11};
all array elements are represented by the leaf nodes of segment tree. and rest of nodes are
formed by adding children nodes up the tree.
Construction of segment tree-
—————————-
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) +
constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for segment tree
int x = (int)(ceil(log2(n))); //Height of segment tree
int max_size = 2*(int)pow(2, x) – 1; //Maximum size of segment tree
int *st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
sum between l and r index-
————————-
/* A recursive function to get the sum of values in given range of the array.
The following are parameters for this function.
st –> Pointer to segment tree
index –> Index of current node in the segment tree. Initially 0 is
passed as root is always at index 0
ss & se –> Starting and ending indexes of the segment represented by
current node, i.e., st[index]
l & r –> Starting and ending indexes of query range */
int getSumUtil(int *st, int ss, int se, int l, int r int index)
{
// If segment of this node is a part of given range, then return the
// sum of the segment
if (l <=ss && r >= se)
return st[index];
// If segment of this node is outside the given range
if (se < l || ss > r)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(st, ss, mid, l, r, 2*index+1) +
getSumUtil(st, mid+1, se, l, r, 2*index+2);
}
int getSum(int *st, int n, int l, int r) // n is the length of the array
{
// Check for erroneous input values
if (l < 0 || r > n-1 || l > r)
{
printf(“Invalid Input”);
return -1;
}
return getSumUtil(st, 0, n-1, l, r, 0);
}
Remove all nodes which don’t lie in any path with sum>= k-
=========================================================
/* Main function which truncates the binary tree. */
struct Node *pruneUtil(struct Node *root, int k, int *sum)
{
// Base Case
if (root == NULL) return NULL;
// Initialize left and right sums as sum from root to
// this node (including this node)
int lsum = *sum + (root->data);
int rsum = lsum;
// Recursively prune left and right subtrees
root->left = pruneUtil(root->left, k, &lsum);
root->right = pruneUtil(root->right, k, &rsum);
// Get the maximum of left and right sums
*sum = max(lsum, rsum);
// If maximum is smaller than k, then this node
// must be deleted
if (*sum < k)
{
free(root);
root = NULL;
}
return root;
}
// A wrapper over pruneUtil()
struct Node *prune(struct Node *root, int k)
{
int sum = 0;
return pruneUtil(root, k, &sum);
}
Add all greater values to every node in a given BST-
===================================================
We do reverse Inorder traversal and keep track of the sum of all nodes visited so far, we add this sum to every node.
// Recursive function to add all greater values in every node
void modifyBSTUtil(struct node *root, int *sum)
{
// Base Case
if (root == NULL) return;
// Recur for right subtree
modifyBSTUtil(root->right, sum);
// Now *sum has sum of nodes in right subtree, add
// root->data to sum and update root->data
*sum = *sum + root->data;
root->data = *sum;
// Recur for left subtree
modifyBSTUtil(root->left, sum);
}
// A wrapper over modifyBSTUtil()
void modifyBST(struct node *root)
{
int sum = 0;
modifyBSTUtil(root, &sum);
}
Print Left View of a Binary Tree-
================================
We can keep track of level of a node by passing a parameter to all recursive calls. The idea is to keep track of maximum level also.
Whenever we see a node whose level is more than maximum level so far, we print the node because this is the first node in its level
(Note that we traverse the left subtree before right subtree)
12
/ \
10 30
/ \
25 40
answer should be 12 10 25
]
// Recursive function to print left view of a binary tree.
void leftViewUtil(struct node *root, int level, int *max_level)
{
// Base Case
if (root==NULL) return;
// If this is the first node of its level
if (*max_level < level)
{
printf(“%d\t”, root->data);
*max_level = level;
}
// Recur for left and right subtrees
leftViewUtil(root->left, level+1, max_level);
leftViewUtil(root->right, level+1, max_level);
}
// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
int max_level = 0;
leftViewUtil(root, 1, &max_level);
}
Check if all leaves are at same level-
=====================================
/* Recursive function which checks whether all leaves are at same level */
bool checkUtil(struct Node *root, int level, int *leafLevel)
{
// Base case
if (root == NULL) return true;
// If a leaf node is encountered
if (root->left == NULL && root->right == NULL)
{
// When a leaf node is found first time
if (*leafLevel == 0)
{
*leafLevel = level; // Set first found leaf’s level
return true;
}
// If this is not first leaf node, compare its level with
// first leaf’s level
return (level == *leafLevel);
}
// If this node is not leaf, recursively check left and right subtrees
return checkUtil(root->left, level+1, leafLevel) &&
checkUtil(root->right, level+1, leafLevel);
}
/* The main function to check if all leafs are at same level.
It mainly uses checkUtil() */
bool check(struct Node *root)
{
int level = 0, leafLevel = 0;
return checkUtil(root, level, &leafLevel);
}
Height of the tree by iterative method-
======================================
// Iterative method to find height of Bianry Tree
int treeHeight(node *root)
{
// Base Case
if (root == NULL)
return 0;
// Create an empty queue for level order tarversal
queue<node *> q;
// Enqueue Root and initialize height
q.push(root);
int height = 0;
while (1)
{
// nodeCount (queue size) indicates number of nodes
// at current lelvel.
int nodeCount = q.size();
if (nodeCount == 0)
return height;
height++;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
node *node = q.front();
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
nodeCount–;
}
}
}
use of various data structure
REAL life interview questions asked on
Datastructure
Q.1. Assume that you are given a fixed set of floating point numbers. Now given a new floating point number ‘x’, the goal is to efficiently find the number that is closest to ‘x’ from the fixed set. Question is: what data structure will you actually use for storing the fixed set of floating point numbers to achieve this?
Edit:
I missed to add. The interviewer further mentioned that I can not sort and that I can use any amount of time for creating the data structure (meaning this need not be efficient).
Ans : Using a Binary Search tree can solve this problem. While traversing the BST we can continue to track the “Minumum difference” found till the current Node and return the “Global minumum” found at the end.
Time O(lg n) and constant space.
public float findClosest(float element) throws IllegalArgumentException{
if (head == null){
throw new IllegalArgumentException();
}
Node traversePointer = head;
float min = Math.abs(head.value – element);
float minElement = traversePointer.value;
//Traverse through all the nodes and find out
while (traversePointer != null ) {
if (min > Math.abs(traversePointer.value – element)) {
min = Math.abs(traversePointer.value – element);
minElement = traversePointer.value;
if (min == 0) {
return minElement;
}
}
if (traversePointer.value > element) {
traversePointer = traversePointer.left;
}else {
traversePointer = traversePointer.right;
}
}
return minElement;
}
Q.2 How would you assign numbers if you were AT&T(largest fixed telephone number provider) describe a data structur??
Ans : Trie(prefix tree). The length of a phone number is a fixed number and phone numbers in close area may share the same area code(prefix). So It will be pretty efficient for searching(O(m), m is the length of the phone number) and storing all those phone numbers inside a Trie.
Q 3 .
A call to hasNext() will return whether the stream contains any more characters to process.
A call to getNext() will return the next character to be processed in the stream.
It is not possible to restart the stream.
If there is no unique character, then return the character ‘#’. # won’t be any character in the character stream.
You just have to complete the function getUniqueCharacter() using the functions hasNext() and getNext() which are already defined.
Example:
Input:
aAbBABac
Output:
b
Input:
aBBa
Output:
#
Algorithm:
1)get count of each and every char in string array.
2)use “Java – String indexOf() Method” to find which element comes first in string array whose count is 1.
##CODE -SAMPLE:##
String str = new String(“aAbBABac “);
for(i=0;i<str[i].length();i++)
{
if(str[i]==str[i+1])
{
count++;//count of all char
}
ex:
aAbBABac
count of ‘a’=2,’A’=2,’B’=2,’b’=1,’c’=1;
return the char whose count is 1;
b,c;
##now finding the first unique char :##
System.out.println(Str.indexOf( ‘b’ ));
System.out.println(Str.indexOf( ‘c’ ));
should return index of both ‘b’,’c’:
index of ‘b’=2;
index of ‘c’=7;(chk both)
Here ‘b’ comes first befre ‘c’ ;so
OUTPUT:
‘b’
Q 4. Design a web crawler to dump all the pages of a given website (URL) onto disk. So basically it saves pages which is related to the website (for instance dump all pages of aws.amazon.com) and do not crawl the links outside the website
Ans :
Awesome
Q. 4 Find the first non-repeating character from a stream of characters
October 8, 2013
Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.
If we follow the first approach discussed here, then we need to store the stream so that we can traverse it one more time to find the first non-repeating character at any moment. If we use extended approach discussed in the same post, we need to go through the count array every time first non-repeating element is queried. We can find the first non-repeating character from stream at any moment without traversing any array.
We strongly recommend you to minimize the browser and try it yourself first.
The idea is to use a DLL (Doubly Linked List) to efficiently get the first non-repeating character from a stream. The DLL contains all non-repeating characters in order, i.e., the head of DLL contains first non-repeating character, the second node contains the second non-repeating and so on.
We also maintain two arrays: one array is to maintain characters that are already visited two or more times, we call it repeated[], the other array is array of pointers to linked list nodes, we call it inDLL[]. The size of both arrays is equal to alphabet size which is typically 256.
1) Create an empty DLL. Also create two arrays inDLL[] and repeated[] of size 256.
inDLL is an array of pointers to DLL nodes. repeated[] is a boolean array,
repeated[x] is true if x is repeated two or more times, otherwise false.
inDLL[x] contains pointer to a DLL node if character x is present in DLL,
otherwise NULL.
2) Initialize all entries of inDLL[] as NULL and repeated[] as false.
3) To get the first non-repeating character, return character at head of DLL.
4) Following are steps to process a new character ‘x’ in stream.
a) If repeated[x] is true, ignore this character (x is already repeated two
or more times in the stream)
b) If repeated[x] is false and inDLL[x] is NULL (x is seen first time)
Append x to DLL and store address of new DLL node in inDLL[x].
c) If repeated[x] is false and inDLL[x] is not NULL (x is seen second time)
Get DLL node of x using inDLL[x] and remove the node. Also, mark inDLL[x]
as NULL and repeated[x] as true.
Note that appending a new node to DLL is O(1) operation if we maintain tail pointer. Removing a node from DLL is also O(1). So both operations, addition of new character and finding first non-repeating character take O(1) time.
|
// A C++ program to find first non-repeating character from a stream of characters #include <iostream> #define MAX_CHAR 256 using namespace std; // A linked list node struct node { char a; struct node *next, *prev; }; // A utility function to append a character x at the end of DLL. // Note that the function may change head and tail pointers, that // is why pointers to these pointers are passed. void appendNode(struct node **head_ref, struct node **tail_ref, char x) { struct node *temp = new node; temp->a = x; temp->prev = temp->next = NULL; if (*head_ref == NULL) { *head_ref = *tail_ref = temp; return; } (*tail_ref)->next = temp; temp->prev = *tail_ref; *tail_ref = temp; } // A utility function to remove a node ‘temp’ fromt DLL. Note that the // function may change head and tail pointers, that is why pointers to // these pointers are passed. void removeNode(struct node **head_ref, struct node **tail_ref, struct node *temp) { if (*head_ref == NULL) return; if (*head_ref == temp) *head_ref = (*head_ref)->next; if (*tail_ref == temp) *tail_ref = (*tail_ref)->prev; if (temp->next != NULL) temp->next->prev = temp->prev; if (temp->prev != NULL) temp->prev->next = temp->next; delete(temp); } void findFirstNonRepeating() { // inDLL[x] contains pointer to a DLL node if x is present in DLL. // If x is not present, then inDLL[x] is NULL struct node *inDLL[MAX_CHAR]; // repeated[x] is true if x is repeated two or more times. If x is // not seen so far or x is seen only once. then repeated[x] is false bool repeated[MAX_CHAR]; // Initialize the above two arrays struct node *head = NULL, *tail = NULL; for (int i = 0; i < MAX_CHAR; i++) { inDLL[i] = NULL; repeated[i] = false; } // Let us consider following stream and see the process char stream[] = “geeksforgeeksandgeeksquizfor”; for (int i = 0; stream[i]; i++) { char x = stream[i]; cout << “Reading ” << x << ” from stream \n”; // We process this character only if it has not occurred or occurred // only once. repeated[x] is true if x is repeated twice or more.s if (!repeated[x]) { // If the character is not in DLL, then add this at the end of DLL. if (inDLL[x] == NULL) { appendNode(&head, &tail, stream[i]); inDLL[x] = tail; } else // Otherwise remove this caharacter from DLL { removeNode(&head, &tail, inDLL[x]); inDLL[x] = NULL; repeated[x] = true; // Also mark it as repeated } } // Print the current first non-repeating character from stream if (head != NULL) cout << “First non-repeating character so far is ” << head->a << endl; } } /* Driver program to test above function */ int main() { findFirstNonRepeating(); return 0; } |
Output:
Reading g from stream
First non-repeating character so far is g
Reading e from stream
First non-repeating character so far is g
Reading e from stream
First non-repeating character so far is g
Reading k from stream
First non-repeating character so far is g
Reading s from stream
First non-repeating character so far is g
Reading f from stream
First non-repeating character so far is g
Reading o from stream
First non-repeating character so far is g
Reading r from stream
First non-repeating character so far is g
Reading g from stream
First non-repeating character so far is k
Reading e from stream
First non-repeating character so far is k
Reading e from stream
First non-repeating character so far is k
Reading k from stream
First non-repeating character so far is s
Reading s from stream
First non-repeating character so far is f
Reading a from stream
First non-repeating character so far is f
Reading n from stream
First non-repeating character so far is f
Reading d from stream
First non-repeating character so far is f
Reading g from stream
First non-repeating character so far is f
Reading e from stream
First non-repeating character so far is f
Reading e from stream
First non-repeating character so far is f
Reading k from stream
First non-repeating character so far is f
Reading s from stream
First non-repeating character so far is f
Reading q from stream
First non-repeating character so far is f
Reading u from stream
First non-repeating character so far is f
Reading i from stream
First non-repeating character so far is f
Reading z from stream
First non-repeating character so far is f
Reading f from stream
First non-repeating character so far is o
Reading o from stream
First non-repeating character so far is r
Reading r from stream
First non-repeating character so far is a
Brush up your concepts 