Ans to *Boundary traversal of a tree. Write the code.
*1) you need to for preoder oder for left most tree with flag and post
order traversal for right most tree with flag.
2) the role of flag would be to decide wther to print or not like in case
of left subtree ,flag would be tree as u knw that
i have few questions regarding ur problems pratik :
1) A tree with only parent pointer, how to find LCA?
Doubt : do u mean only root of the tree is given , i am assuming root along
with two nodes address whose lca need to
find too is given , i am right ?
2) Find top k searched elements
these questions were asked for software dev. in amazon ? which round .
looks like straight easy questions...
On Sun, Mar 10, 2013 at 5:58 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
Ans to *Boundary traversal of a tree. Write the code.
*1) you need to for preoder oder for left
It looks as if you have just pasted some Amazon interview questions on this
forum.
These are pretty common questions.
Try to come up with your own answers.
Do some research on google and previous posts on this forum. You'll get
answers to all of them.
If you have some idea and want to discuss
Hassan geke should not be a valid string. The question states which have
the same substring following it so here e follows e. There is no
precondition that it has to follow immediate.
Utsav: can you clarify?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
nope geke is valid string..
here is the link from where question was taken
http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker
On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote:
Hassan geke should not be a valid string. The question states which
geke is valid. BTW if you changeif(i=len) toif(i0) my code
outputs geke is invalid.( what you desired)
if geke is invalid regarding to the question, then you can achieve the
answer in nLogn by sorting strings :s[0..n-1], s[1..n-1],s[n-1..n-1]
and comparing adjacent members.
Regards
@ashish:- geke is valid as repeated substrings should be immediate.
On Wed, Jun 6, 2012 at 1:44 PM, Hassan Monfared hmonfa...@gmail.com wrote:
geke is valid. BTW if you changeif(i=len) toif(i0) my code
outputs geke is invalid.( what you desired)
if geke is invalid regarding to the
Thanks, my approach
prepare a multimap of charcters and their positions by walking over the
string.
ashishis if is give string
the multimap will have
a-0
s-1,4,7
h-2,5
i-3,6
now for every character while walkingover the given string again, check
from its multimap, if it is repeated, if not
*tree substrings*
tree--|---mississippim .. mississippi
|
|---i--|---ssi--|---ssippi i .. ississippi
| | |
| | |---ppi issip,issipp,issippi
| |
| |---ppi
Hassan, can you explain your algo?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote:
for
--
You received this message because you are subscribed to the Google Groups
The problem suggests that a character can't be more than once present and
thereby it can be done by just having s bitmap and if a char repeats, any
longer repeating substring will have those char repeated atleast twice,
hence O(n) solution.
Also, Hasaan: how is your algo O(n2) for for-while-for
Ashish:
the algorithm passes over string and check if there is any substring with
len=1 is repeated or not. if not, tries for substring with len 2,... and so
on.
max length of substring which can be repeated can be at most N/2.
Regards,
On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel
is geke is a invalid strng?
On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Ashish:
the algorithm passes over string and check if there is any substring with
len=1 is repeated or not. if not, tries for substring with len 2,... and so
on.
max length of substring
yes It's valid, cuz it doesn't have any repeated substring next together
On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.com wrote:
is geke is a invalid strng?
On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote:
Ashish:
the algorithm passes over
@hasan :-ohhh sorry, i didn't see the outer loop
yeah, it works but it is O(n^2), required solution is of O(n).
On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote:
utsav: It works fine, I did little bug fixing on boundaries as here goes :
bool IsValid(string s)
{
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array as
it is easier) traverse the each suffix till you encounter the first letter
of the suffix you are traversing and check to see this suppose i is the
index
I think it can be done by modifying the h-array and by making some changes
in KMP-algorithm
On Mon, Jun 4, 2012 at 9:35 AM, Jeevitesh jeeviteshshekha...@gmail.comwrote:
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.com wrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try
utsav: It works fine, I did little bug fixing on boundaries as here goes :
bool IsValid(string s)
{
for(int len=1;len=s.size()/2;len++)
{
int start1=0,start2=len;
while(start2s.size())
{
int i=0;
for(;ilen start2+is.size() s[start1+i]==s[start2+i];i++);
if(i=len)
23 matches
Mail list logo
