Tushar
BAN USERi don't know what sonesh is saying.
I have another doubt.
Take the case:
While searching, data = 5
5 has not been inserted in the hashmap
Garbage values are as follows:
from[5] = 3234
to[3234] = 5
Then this will return that 5 exists but if we have the check from[data]<top, then it will function correctly
So I think the check
from[data]<top
should also be there.
There are always trade offs involved
In the example in third comment on this answer, your method would be faster and extra space taken would not be much, whereas if there are missing numbers which are distributed into many different ranges, it might lead to too much extra space.
An answer similar to yours has been posted by notbad on Jan 6.
It is quite difficult to have one best anwer.
Thanks for your approach.
I think there are a few bugs.
In DisplayNode(), you take node at distance one to be head itself. head should be printed when dis comes in the function as zero. If dis is zero, it is converted to 1, and then recursive calls are made. This recursion will end only when you encounter head to be NULL.
In FindNodes, you call DisplayNode() for nodes in path from root to required node. This will print nodes at distance dis(which has been decremented correctly) in both directions. You have to print nodes in the subtree other than the one in which required node is present.
Your while loop condition checks that return value of function is non negative and then inside the loop, you check that the value is negative. I think the condition inside the loop is redundant.
I agree with Hugo that this will be stuck indefinitely till you are able to generate a number not in the list. It might be in 1 step or it might even take a long time to get that value. It is not deterministic. Though we need a random value, we need an algo that will come to an end within a limited time.
Thank you for pointing this out
I forgot to write the basic point that we will go through a loop till the num is less than the smallest element in the subarray being considered at a particular point.
So in the example you have given, we will not stop at 4. We will again traverse with k=2 and go on like that. After reaching 50, k=1. Then we will move ahead and reach 60.
In my example there were 2 traversals as it required that only.
Also I have not covered the case where all numbers in the range are in the list. I have also assumed that numbers are distinct in the list.
When we are implementing this, we will need to take care of such edge cases. There are some other cases like min<=max and others which will be taken care of while implementing.
just modified a bit of the code for trie.
So there are 2 more things I'd like to mention:
1. is_last is redundant here
2. insert() function can insert strings of all lengths, but I have put checks according to length 3 only as checking for repeated string of length will suffice.
for the second part,
we can move back to only oe 1 in the array.
1. Take first number as n. then repeat the second number n times.
2. Now, take third number as n, Repeat fourth number n times.


Keep doing this.
At any step, if you an odd length array or have same number to be repeated continuously, then the array is invalid.
It is obvius that odd length is invalid.
For second point, consider 1, 1, 1, 1
It will create
1, 1
1
But it is not valid as its sequence should have been 2, 1 and not 1, 1, 1, 1
Algo:
1. You have last 2 characters of the stream saved in a buffer.
2. Append the current char to form string of length 3
3. Insert this into the trie.
If this string already exists in the trie, then return a signal of repeated string.
It does not use any concept of suffixes. It is simply comparing given string with earlier strings but using a tree for it. This is what we do in tries.
But I am taking space of 3 chars to store last 2 chars and current char. I am not using space for just one char.
The question says "Given a String"
Stream is not mentioned in the question.
Even if it is a stream, you can save last two characters and after the current character arrives, just check for the 3 character string in the trie. We just need to save all distinct 3 character strings that have already come through the stream.
As soon as there is a repetition, we can return the answer.
@Kusum, cypher's comment on lovecoding's answer answers the question of minimum 3 and not exactly 3 characters
Some people have suggested making an array of the numbers we do not have in the given list. This array can be too big.
We can have this algoirthm:
1. Sort the given list. It takes time O(nlogn)
2. Instead of creating an array we can just get the size of the array, i.e., number of elements which are not present in the given list. It will be
size = (maxmin+1)  (number of distinct numbers in the list)
3. Now we can get a random number k in the range [1,size]
4. Now we just need to find the kth number among the numbers which are not present in the given list. We have not created the array of missing numbers. So we will find the kth number among the missing numbers using the given list as follows:
a) take curr = min
b) take num = curr + k  1 (taking k to bestarting from 1)
c) do binary search to find element in the list which is the rightmost element less than or equal to num. Label it as lower_element
If no such element exists, then num is less than first element in the list, so num is the answer.
Otherwise,
(i) count the number of elements from lower_element in this traversal to the lower_element in previous traversal (if first traversal, count number of elements from starting)
(ii) k = (count in step (i))
(iii) num = num + k
Example:
List is {10, 20, 40, 60, 80} //taking sorted list for convenience.
Range is 1100
Step 2.
size = (1001+1)  5
= 95
Step 3.
Random number generated = 50
Step 4.
a) curr = 1
b) num = 1+501 = 50
c)
First traversal:
search for 50 in the given array.
lower_element = 40
i) count = 3
ii) k = 3
iii) num = 50+3 = 53
Second traversal:
search for 53 in the given array after 40.
There is no lower_element now.
So the answer is 53.
Basic Assumption: We have a function that generates a pure random number from 1 to n.
I think this might work.
#include<iostream>
using namespace std;
class node;
class node
{
public:
int data;
node *left;
node *middle;
node *right;
node(int val)
{
data = val;
left = middle = right = NULL;
}
};
node * create_list(node *tnode, node *tnode2)
{
if(!tnode) return NULL;
tnode2 = tnode;
tnode2>left = create_list(tnode>left, tnode2);
while(tnode2>left)
tnode2 = tnode2>left;
tnode2>left = create_list(tnode>middle, tnode2);
while(tnode2>left)
tnode2 = tnode2>left;
tnode2>left = create_list(tnode>right, tnode2);
return tnode;
}
int main()
{
node *root = NULL;
root = new node(10);
root>left = new node(6);
root>middle = new node(9);
root>right = new node(13);
root>left>left = new node(7);
root>left>middle = new node(8);
root>left>right = new node(5);
root = create_list(root, root);
while(root)
{
cout<<root>data<<'\n';
root = root>left;
}
return 0;
}

Tushar
January 06, 2013 good solution bhavesh
@TechLead
We can assign a number to each word in the correct sentence
e.g.:
we must go to newyork now
we  1
must  2
go  3
to  4
newyork  5
now  6
do this using a map
now for the senetence spoken by yoda
"Newyork must go we to now"
create an int array storing numbers for the corresponding words
array would be {5,2,3,1,4,6}
count the number of inversions as done here: www[dot]geeksforgeeks[dot]org/archives/3968
I think this should work.
struct TN{
int data;
struct TN* left;
struct TN* right;
};
///////////////////////////////////////////////////////////////
//returns length of longest path from root to a leaf
int getHeight(TN *root)
{
if(root == NULL)
return 0;
return(1 + max(getHeight(root>left), getHeight(root>right)));
}
/////////////////////////////////////////////////////////////
//returns length of minimum path from root to a leaf
int getMinHeight(TN *root)
{
if(root == NULL)
return 0;
int lMinHeight = getMinHeight(root>left);
int rMinHeight = getMinHeight(root>right);
if(lMinHeight == 0  rMinHeight == 0)
{return 1+max(lMinHeight,rMinHeight);
}
else
{return 1 + min(lMinHeight, rMinHeight);}
}
////////////////////////////////////////////////////////
//function to check balance of tree
bool checkBalance(TN *root)
{
int maxHeight = getHeight(root);
int minHeight = getMinHeight(root);
if(maxHeight  minHeight > 1)
return false;
else
return true;
}

Tushar
June 15, 2012 A
BC
 DEFG
HIJKM
L
If we have this tree, then it is balanced. But, MinDepth of A will be calculated as 3 whereas MaxDepth as 5. So it will give it as an unbalanced tree.
Please correct me if I am taking this incorrectly.
RepHi, I am Alisa from Southfield, USA, I am working as a Toolmaker in an AudioVisions company. I am also ...
Repsallieroliphant, Project Leader at Wissen Technology
With years of experience I can guarantee you that our licensed company specializes in furnace maintenance scarborough, air conditioners and ...
Open Chat in New Window
@Hill Billy, in case of longest common substring suffix tree is a better choice, though I would implement it using suffix array as it is easier to code.
 Tushar January 28, 2013