shashank7android
BAN USERmy thought , its just like searching the element in sorted array of infinite length , bin search in 2^i where i=0 to n .
Assume location of car is x and o to infinite (length of road its unknown )
Question need to be understand clearly .We Have to Transfer the Whole BST/BT across the network this is where he asked to implement the serialization on Tree & the transfer to another host on recipient side we use deserialization . to implement serialization on tree we need to save it in file & restoring the exact tree on receiving side .important question arises that which traversal we have to use here pre,in or post ?? only one is best are u able to think of it ???
let me explain lets we have tree is
_30_
/ \
20 40
/ / \
10 35 50
In-order traversal
If we do an in-order traversal, we will output 10 20 30 35 40 50. There is no way of telling how the original BST structure looks like, as the following unbalanced BST is one of the possible BST sets from the output 10 20 30 35 40 50.
_50
/
40
/
35
/
30
/
20
/
10
Post-order traversal:
If we do a post-order traversal, we will output the leaf nodes before its parent node. Specifically, we will output 10 20 35 50 40 30 using post-order traversal. Imagine we’re reading the nodes to construct the tree back. See the problem that we are reading the leaf nodes before its parent? There’s too much trouble to create the child nodes before its parent. Remember that the BST insertion algorithm works by traversing the tree from the root to the correct leaf to insert.
Pre-order traversal:
Pre-order traversal is the perfect algorithm for making a copy of a BST. The output of a pre-order traversal of the BST above is 30 20 10 40 35 50. Please note the following important observation:
A node’s parent is always output before itself.
Therefore, when we read the BST back from the file, we are always able to create the parent node before creating its child nodes. The code for writing a BST to a file is exactly the same as pre-order traversal.
Ps: we can solve this problem with any traversal if we need to given an array to store in array instead of file isn't it think ?? why
on receiving side Reading a BST from a file:
The question now is, how would you reconstruct a BST back from the file? Assume that we have the following pre-order traversal output of the BST earlier: 30 20 10 40 35 50.
so answer is
When we encounter a new node to insert, we should always place it into the first empty space which it will fit using a pre-order traversal. How do we determine the first empty space which a node will fit in? We can use the ordinary BST insertion algorithm, but the run-time complexity will be O(n lg n), since inserting a node takes O(lg n) time. Not efficient enough! so we need some more efficient algorithm
yes we can do it using what we used to solve "Determine if a Binary Tree is a Binary Search Tree (BST)?"
so what will be the efficent algo then here it is
We use the same idea here. We pass the valid range of the values from the parent node to its child nodes. When we are about to insert a node, we will check if the insert value is in the valid range. If it is, this is the right space to insert. If it is not, we will try the next empty space. Reconstructing the whole BST from a file will take only O(n) time.
void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) {
int val = insertVal;
p = new BinaryTree(val);
if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}
void readBST(BinaryTree *&root, ifstream &fin) {
int val;
fin >> val;
readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}
Cheers!!!! Do Notify me if anything wrong or other solutions
Shashank "shashank7s.blogspot.com"
obvious hash set is better it wont allow to add duplicate..so duplicate automatically removed ..from array
- shashank7android March 21, 2011Keep in Mind Whenever we wants to find the kth or nth largest or top k elements or use Min Heap because logic is simple behind this. when we build the min heap in each iteration we remove the min from the min-heap so call to heapify operation its overall complexity is O(n*logn) but gives us desired result suppose k=3 means u wants to find out 3rd largest inn unsorted array of 100 elements
1st solution is to sort the array which is also a solution but not sounds good to interviewer in this scenario he wanst to hear from us about Heap DS
2nd solution is to build min heap in (nlogn) keep removing min element which is nothing but minimum element in heap until k=0 when when k=0 we have 3rd largest element at top & that's what we are looking for ..soon i will post solution here using min heap.
Keep in Mind Whenever we wants to find the kth or nth largest or top k elements or use Min Heap because logic is simple behind this. when we build the min heap in each iteration we remove the min from the min-heap so call to heapify operation its overall complexity is O(n*logn) but gives us desired result suppose k=3 means u wants to find out 3rd largest inn unsorted array of 100 elements
1st solution is to sort the array which is also a solution but not sounds good to interviewer in this scenario he wanst to hear from us about Heap DS
2nd solution is to build min heap in (nlogn) keep removing min element which is nothing but minimum element in heap until k=0 when when k=0 we have 3rd largest element at top & that's what we are looking for ..soon i will post solution here using min heap.
Keep in Mind Whenever we wants to find the kth or nth largest or top k elements or use Min Heap because logic is simple behind this. when we build the min heap in each iteration we remove the min from the min-heap so call to heapify operation its overall complexity is O(n*logn) but gives us desired result suppose k=3 means u wants to find out 3rd largest inn unsorted array of 100 elements
1st solution is to sort the array which is also a solution but not sounds good to interviewer in this scenario he wanst to hear from us about Heap DS
2nd solution is to build min heap in (nlogn) keep removing min element which is nothing but minimum element in heap until k=0 when when k=0 we have 3rd largest element at top & that's what we are looking for ..soon i will post solution here using min heap.
its recursion using catalan number
Cn+1= sum(Ci*Cn-i)
i=0 to k]
void fully-bst(int n) //n= N-1/2
{
if(n==0||n==1)
return n;
else return (fact(2*n)/fact(n+1)*fact(n));
}
unsigned int fact(unsigned int n)
{
if (n <= 1)
return 1;
else
return n * fact(n-1);
}
All Credit Goes to Tulley Who Explained it Exceptionally Well
put all the phone numbers into hastable & count with every single entry .time & space complexity for insertion depends on which technique u r using e.g. (closed addressing)separate chaining ot linear probing(open addressing) now its done given a phone number as key your have to search a phone number which has count more then 1 dats nothing but duplicate ..we hav saved our space also here by not storing duplicates as a saperate instead we have just incremented the count for every simpler entry so searching will took O(1) time
Please Correct me If I am wrong of is dare any flaw in my approach
#define MAX_POINT 3
#define ARR_SIZE 100
#include<stdio.h>
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);
/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n, int i)
{
/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];
if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(n-k, i+1);
}
}
}
/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
printCompositions(n, 0);
getchar();
return 0;
}
only if sorting allowed problems becomes to finding the subset of length K in given sert of length L where K<=L
- shashank7android February 13, 2011
Check for kadane algorithm :)
- shashank7android September 01, 2012