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 lef
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 f
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
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
@ashish:- geke is valid as repeated substrings should be immediate.
On Wed, Jun 6, 2012 at 1:44 PM, Hassan Monfared wrote:
> geke is valid. BTW if you change " if(i>=len) " to " if(i>0)" my code
> outputs geke is invalid.( what you desired)
> if geke is invalid regarding to the question, the
geke is valid. BTW if you change " if(i>=len) " to " if(i>0)" 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.
Regar
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 wrote:
> Hassan geke should not be a valid string. The question states " which
> have the same
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
+91
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 wrote:
> is geke is a invalid strng?
>
>
> On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared wrote:
>
>> Ashish:
>>
>> the algorithm passes over string and check if there is any
is geke is a invalid strng?
On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared wrote:
> 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 re
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 wrote:
>
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
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 wrote:
> for
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
*tree substrings*
tree-->|---mississippim .. mississippi
|
|---i-->|---ssi-->|---ssippi i .. ississippi
| | |
| | |---ppi issip,issipp,issippi
| |
| |---ppi
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 wrote:
> 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
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 yo
@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 wrote:
> utsav: It works fine, I did little bug fixing on boundaries as here goes :
> bool IsValid(string s)
> {
> for(int len=1;len<=s
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(start2=len)
return false; //"not valid"
start1++;
start2++;
}
}
return true; // valid
}
It works
@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 wrote:
> @hassan :- it will not work for many strings as you are checking from the
> mid of strings. try out "ababcdef","aabc".
>
@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 wrote:
> yes it's not valid
>
>
> On Sun, Jun 3, 2012 at 5:36 PM, anugrah wrote:
>
>> So any
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah 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 wrote:
> > bool IsValid(string s)
> > {
> > for(int len=
21 matches
Mail list logo
