Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread Hassan Monfared 
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 chain?
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel  wrote:
>
>> 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.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread Ashish Goel 
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 chain?

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel  wrote:

> 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.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread Ashish Goel 
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.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] implementation of dijkstra

2012-06-04 Thread Abhishek Sharma 
how to implement dijkstra algorithm using fibonacci heaps ?thanks in
advance

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] importance of heaps

2012-06-04 Thread Abhishek Sharma 
can anyone please tell me how important are heaps as compared to other data
structures (from interview's point of view). i am not talking about simple
min/max heaps, but advanced ones like fibonacci heaps and binomial heaps

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread Ashish Goel 
*tree   substrings*

tree-->|---mississippim .. mississippi
   |
   |---i-->|---ssi-->|---ssippi   i .. ississippi
   |   | |
   |   | |---ppi  issip,issipp,issippi
   |   |
   |   |---ppiip, ipp, ippi
   |
   |---s-->|---si-->|---ssippis .. ssissippi
   |   ||
   |   ||---ppi   ssip, ssipp, ssippi
   |   |
   |   |---i-->|---ssippi si .. sissippi
   |   |
   |   |---ppisip, sipp, sippi
   |
   |---p-->|---pi p, pp, ppi
   |
   |---i  p, pi

*--- Suffix Tree for "mississippi" ---*
in this example, any bifurcation implies that the substring is repeated(eg
i, s, ss, si, p, issi) and looks like this problem can be done while
forming the suffix trie

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Tue, Jun 5, 2012 at 12:28 AM, Abhishek Sharma wrote:

> 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 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 you found out the starting letter then check
>> s.substring(0,i)==s.substring(i,2i).
>>
>> I hope you get the idea.
>>
>>
>> On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma wrote:
>>
>>> @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".
 @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 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=0;len> >  {
>> >int start1=0,start2=len+1;
>> >while(start2> >{
>> >   for(int i=0;i> > s[start1+i]=s[start2+i];i++);
>> >   if(i==len)
>> >return false; //"not valid"
>> >   start1++;
>> >   start2++;
>> > }
>> >  }
>> > return true; // valid
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > }
>> > On Sun, Jun 3, 2012 at 12:52 PM, atul anand <
>> atul.87fri...@gmail.com> wrote:
>> > > can be done with O(n^2) time complexity..
>> >
>> > > can it be done with O(n) complexity ???
>> >
>> > > On 6/3/12, utsav sharma  wrote:
>> > > > given a string tell wether it is valid or not.
>> > > > string is valid if there is no substring which have the same
>> substring
>> > > > following it.
>> >
>> > > > these strings are not valid:- "stringstring","geek123123rt",
>> > > > "abcadabcad","strngstingstrngsting"
>> >
>> > > > --
>> > > > You received this message because you are subscribed to the
>> Google Groups
>> > > > "Algorithm Geeks" group.
>> > > > To post to this group, send email to algogeeks@googlegroups.com
>> .
>> > > > To unsubscribe from this group, send email to
>> > > > algogeeks+unsubscr...@googlegroups.com.
>> > > > For more options, visit this group at
>> > > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > > --
>> > > You received this message because you are subscribed to the
>> Google Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks"

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread atul anand 
well converting single linked list to balanced BST...this would also work

On Mon, Jun 4, 2012 at 4:29 PM, Nishant Pandey  wrote:

> Hi ,
>
> I think the only possiblity is to make it doubly linked list and then
> consider next & prev as left and right child like tree and then perform
> search as we in tree , it would serve the purpose .
> let me know if iam wrong .
>
> On Mon, Jun 4, 2012 at 3:51 PM, SANDEEP CHUGH wrote:
>
>> can be done using skip lists
>>
>>
>> On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh 
>> wrote:
>>
>>> This is possible only if Linked List is sorted then we can apply Merge
>>> Sort for Linked List which would be in place.
>>>
>>> Otherwise the time complexity would be O(n logn).
>>>
>>> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>>>
 Hi we need find a node in linked list in O(logn). You can change the
 list as u like.

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>>
>>> --
>>> *Thanks,
>>> Jeevitesh Shekhar Singh.*
>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Cheers,
>
> Nishant Pandey |Specialist Tools Development  |  
> npan...@google.com |
> +91-9911258345
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] interview HARD problem

2012-06-04 Thread Ashish Goel 
preparing a sample itself is a great problem here, that is why i called it
hard

all words in the rectangle horizontally as well as vertically needs to be
valid dictionary words

Ashish
Hassan

say this rectangle AH,SA,HS,IS,SA,HN should also be valid dictonary words,
indeed they are not..

definitely we will need a multimap to have words of same length forming a
bucket..not able to think beyond this

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Mon, Jun 4, 2012 at 6:38 PM, Hassan Monfared  wrote:

> Give a sample please
>
> On Mon, Jun 4, 2012 at 5:34 PM, Ashish Goel  wrote:
>
>> Given a dictionary of millions of words, give an algorithm to find the
>> largest possible rectangle of letter that every row forms a word(reading
>> left to right) and every column forms a word(reading from top to bottom).
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Digest for algogeeks@googlegroups.com - 25 Messages in 6 Topics

2012-06-04 Thread Dhaval Moliya 
@Viharri: You can use skip list.

On Mon, Jun 4, 2012 at 3:30 PM,  wrote:

>   Today's Topic Summary
>
> Group: http://groups.google.com/group/algogeeks/topics
>
>- MS Question: Delete a node in single linked list if it is less than
>any of the successor nodes <#137b6f050d04b422_group_thread_0> [1
>Update]
>- LINKED LIST QUESTION <#137b6f050d04b422_group_thread_1> [2 Updates]
>- amazon interview questions <#137b6f050d04b422_group_thread_2> [6
>Updates]
>- Matrix Minimum Path Sum <#137b6f050d04b422_group_thread_3> [6
>Updates]
>- Simple Question ,Find Error <#137b6f050d04b422_group_thread_4> [2
>Updates]
>- MS: searching problem..help me 
> out...<#137b6f050d04b422_group_thread_5>[8 Updates]
>
>   MS Question: Delete a node in single linked list if it is less than any
> of the successor 
> nodes
>
>Amol Sharma  Jun 04 03:25PM +0530
>
>here is the question ans solution with proper explanation
>
>http://www.geeksforgeeks.org/archives/11604
>
>--
>
>
>Amol Sharma
>Third Year Student
>Computer Science and Engineering
>MNNIT Allahabad
>
><
>http://in.linkedin.com/pub/amol-sharma/21/79b/507><
>http://www.simplyamol.blogspot.com/>
>
>
>
>
>
>
>
>
>
>   LINKED LIST 
> QUESTION
>
>VIHARRI  Jun 04 02:30AM -0700
>
>Hi we need find a node in linked list in O(logn). You can change the
>list
>as u like.
>
>
>
>
>Amol Sharma  Jun 04 03:17PM +0530
>
>not possible i suppose..
>--
>
>
>Amol Sharma
>Third Year Student
>Computer Science and Engineering
>MNNIT Allahabad
>
><
>http://in.linkedin.com/pub/amol-sharma/21/79b/507><
>http://www.simplyamol.blogspot.com/>
>
>
>
>
>
>
>
>
>
>   amazon interview 
> questions
>
>anugrah  Jun 03 06:06AM -0700
>
>So any string with two same characters is not valid??
>
>for example :
>
>GEEK has E followed by E.
>
>So GEEK is also invalid?
>
>
>
>
>
>Hassan Monfared  Jun 03 10:54PM +0430
>
>yes it's not valid
>
>
>
>
>
>utsav sharma  Jun 04 09:11AM +0530
>
>@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).
>
>
>
>
>
>
>utsav sharma  Jun 04 09:14AM +0530
>
>@jeevitesh :- yes i am also thinking of suffix tree,
>but i am facing problem in implementing it. did you implement it ??
>
>
>
>
>
>Hassan Monfared  Jun 04 10:20AM +0430
>
>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{
>int i=0;
>for(;iif(i>=len)
>return false; //"not valid"
>start1++;
>start2++;
>}
>}
>return true; // valid
>}
>It works for both input you provided. :)
>
>
>
>
>
>utsav sharma  Jun 04 02:50PM +0530
>
>@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).
>
>
>--
>Utsav Sharma,
>NIT Allahabad
>
>
>
>   Matrix Minimum Path 
> Sum
>
>Decipher  Jun 03 07:00AM -0700
>
>Q) In the 5 by 5 matrix below, the minimal path sum from the top left
>to
>the bottom right, by moving left, right, up, and down, is indicated in
>bold
>red and is equal to 2297.
>
>
>*131*
>
>673
>
>*234*
>
>*103*
>
>*18*
>
>*201*
>
>*96*
>
>*342*
>
>965
>
>*150*
>
>630
>
>803
>
>746
>
>*422*
>
>*111*
>
>537
>
>699
>
>497
>
>*121*
>
>956
>
>805
>
>732
>
>524
>
>*37*
>
>*331*
>
>
>
>Write an algorithm to find the same. Also, write an algorithm if the
>same
>matrix contains negative numbers (maybe negative cycle) and compare
>the
>space and time complexity of both.
>
>
>
>
>Victor Manuel Grijalva Altamirano  Jun 03
>03:46PM -0500
>
>interesting problem... DP ??? where do you see this problem???
>
>2012/6/3 Decipher 
>
>
>--
>Victor Manuel Grijalva Altamirano
>Universidad Tecnologica de La Mixteca
>
>
>
>
>atul anand  Jun 04 08:55AM +0530
>
>find cumulative sum row[0]
>find cumulative sum of col[0]
>
>after this following recurrence will solve the problem.
>
>start from mat[1][1]
>
>mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] )
>
>
>
>
>
>atul anand  Jun 04 12:20PM +0530
>
>this recurrence wont work..ignore
>
>
>
>
>
>Hassan Monfared  Jun 04 12:39PM +0430
>
>for non-negat

Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread Abhishek Sharma 
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 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 you found out the starting letter then check
> s.substring(0,i)==s.substring(i,2i).
>
> I hope you get the idea.
>
>
> On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma wrote:
>
>> @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".
>>> @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 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=0;len >  {
> >int start1=0,start2=len+1;
> >while(start2 >{
> >   for(int i=0;i > s[start1+i]=s[start2+i];i++);
> >   if(i==len)
> >return false; //"not valid"
> >   start1++;
> >   start2++;
> > }
> >  }
> > return true; // valid
> >
> >
> >
> >
> >
> >
> >
> > }
> > On Sun, Jun 3, 2012 at 12:52 PM, atul anand 
> wrote:
> > > can be done with O(n^2) time complexity..
> >
> > > can it be done with O(n) complexity ???
> >
> > > On 6/3/12, utsav sharma  wrote:
> > > > given a string tell wether it is valid or not.
> > > > string is valid if there is no substring which have the same
> substring
> > > > following it.
> >
> > > > these strings are not valid:- "stringstring","geek123123rt",
> > > > "abcadabcad","strngstingstrngsting"
> >
> > > > --
> > > > You received this message because you are subscribed to the
> Google Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> *Thanks,
> Jeevitesh Shekhar Singh.*
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group

Re: [algogeeks] Simple Question ,Find Error

2012-06-04 Thread sengar.mahi 
Answer:
Compiler error: Lvalue required in function main

This was the answer given along with the question..pls explain !!
On Mon, Jun 4, 2012 at 10:04 PM, abhishek  wrote:

> This code have issue.
>
> names[3]=names[4];
> names[4]=t;
>
> -Original Message-
> From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On
> Behalf Of mahendra sengar
> Sent: Monday, June 04, 2012 4:13 AM
> To: Algorithm Geeks
> Cc: sengar.m...@gmail.com
> Subject: [algogeeks] Simple Question ,Find Error
>
>  main()
> {
> static char names[5][20]={"pascal","ada","cobol","fortran","perl"};
> int i;
> char *t;
> t=names[3];
> names[3]=names[4];
> names[4]=t;
> for (i=0;i<=4;i++)
> printf("%s",names[i]);
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

RE: [algogeeks] Simple Question ,Find Error

2012-06-04 Thread abhishek 
This code have issue.

names[3]=names[4];
names[4]=t;

-Original Message-
From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On
Behalf Of mahendra sengar
Sent: Monday, June 04, 2012 4:13 AM
To: Algorithm Geeks
Cc: sengar.m...@gmail.com
Subject: [algogeeks] Simple Question ,Find Error

 main()
{
static char names[5][20]={"pascal","ada","cobol","fortran","perl"};
int i;
char *t;
t=names[3];
names[3]=names[4];
names[4]=t;
for (i=0;i<=4;i++)
printf("%s",names[i]);
}

-- 
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread Nishant Pandey 
Hi ,

I think the only possiblity is to make it doubly linked list and then
consider next & prev as left and right child like tree and then perform
search as we in tree , it would serve the purpose .
let me know if iam wrong .

On Mon, Jun 4, 2012 at 3:51 PM, SANDEEP CHUGH wrote:

> can be done using skip lists
>
>
> On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh wrote:
>
>> This is possible only if Linked List is sorted then we can apply Merge
>> Sort for Linked List which would be in place.
>>
>> Otherwise the time complexity would be O(n logn).
>>
>> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>>
>>> Hi we need find a node in linked list in O(logn). You can change the
>>> list as u like.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> *Thanks,
>> Jeevitesh Shekhar Singh.*
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Cheers,

Nishant Pandey |Specialist Tools Development  |
npan...@google.com |
+91-9911258345

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Matrix Minimum Path Sum

2012-06-04 Thread Decipher 
@Victor - Someone had asked this question from me !! He told me its from 
Project Euler Q-83.
@Hassan -  I think you are right. This question can be solved by 
Dijikstra's algo, if we consider the matrix elements as weights.  

On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote:
>
> moving must be done in A* style
>
> On Mon, Jun 4, 2012 at 1:17 PM, atul anand wrote:
>
>> i dont think so dijistra will worh here..bcozz we cannot move diagonally 
>> ...but according to matrix this path can be considered. 
>>
>> On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared wrote:
>>
>>> for non-negative values Dijkstra will solve the problem in ( O(N^2) )
>>> and Floyd-Warshal is the solution for negative cells. ( O(N^3) )
>>>
>>>  
>>>
>>> On Mon, Jun 4, 2012 at 11:20 AM, atul anand wrote:
>>>
 this recurrence wont work..ignore 

 On Mon, Jun 4, 2012 at 8:55 AM, atul anand wrote:

> find cumulative sum row[0]
> find cumulative sum of col[0]
>
> after this following recurrence will solve the problem.
>
> start from mat[1][1]
>
> mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] )
>
>
> On Sun, Jun 3, 2012 at 7:30 PM, Decipher wrote:
>
>> Q) In the 5 by 5 matrix below, the minimal path sum from the top left 
>> to the bottom right, by moving left, right, up, and down, is indicated 
>> in 
>> bold red and is equal to 2297.
>>
>> 
>>  *131*
>>  
>> 673
>>  
>> *234*
>>  
>> *103*
>>  
>> *18*
>>   
>> *201*
>>  
>> *96*
>>  
>> *342*
>>  
>> 965
>>  
>> *150*
>>   
>> 630
>>  
>> 803
>>  
>> 746
>>  
>> *422*
>>  
>> *111*
>>   
>> 537
>>  
>> 699
>>  
>> 497
>>  
>> *121*
>>  
>> 956
>>   
>> 805
>>  
>> 732
>>  
>> 524
>>  
>> *37*
>>  
>> *331*
>>   
>>
>>   
>> Write an algorithm to find the same. Also, write an algorithm if the 
>> same matrix contains negative numbers (maybe negative cycle) and compare 
>> the space and time complexity of both.
>>  
>>  -- 
>> You received this message because you are subscribed to the Google 
>> Groups "Algorithm Geeks" group.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to 
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
  -- 
 You received this message because you are subscribed to the Google 
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>  -- 
>>> You received this message because you are subscribed to the Google 
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to 
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at 
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to 
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] interview HARD problem

2012-06-04 Thread Hassan Monfared 
Give a sample please

On Mon, Jun 4, 2012 at 5:34 PM, Ashish Goel  wrote:

> Given a dictionary of millions of words, give an algorithm to find the
> largest possible rectangle of letter that every row forms a word(reading
> left to right) and every column forms a word(reading from top to bottom).
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] interview HARD problem

2012-06-04 Thread Ashish Goel 
Given a dictionary of millions of words, give an algorithm to find the
largest possible rectangle of letter that every row forms a word(reading
left to right) and every column forms a word(reading from top to bottom).

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...

2012-06-04 Thread Abhishek Sharma 
mailing you the link for same

On Mon, Jun 4, 2012 at 1:31 AM, Dhaval Moliya wrote:

> If any one have algorithms for interviews by adnan aziz ebook... Please
> mail ...
> Thanks
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MS Question: Delete a node in single linked list if it is less than any of the successor nodes

2012-06-04 Thread atul anand 
whats problem with the approch provided by navin

http://k2code.blogspot.in/2011/09/deleting-node-in-singly-linked-list-if.html

it seems much simpler ...is there any test case for which it wont work ??

On Mon, Jun 4, 2012 at 3:25 PM, Amol Sharma  wrote:

> here is the question ans solution with proper explanation
>
> http://www.geeksforgeeks.org/archives/11604
>
> --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>  
> 
>
>
>
>
>
>
> On Sat, Jun 2, 2012 at 1:21 AM, Hassan Monfared wrote:
>
>> 1- read all elements of list into stack
>> 2- max = stak.pop()
>> 3- if stack.empty() goto 7
>> 4- next=stack.pop()
>> 5- if next > max then max=next
>>  else delete next from list
>> 6- repeat from 3
>> 7- end!
>>
>> Regards,
>>
>> On Thu, May 31, 2012 at 9:45 PM, atul anand wrote:
>>
>>> @navin : +1
>>>
>>> On 5/31/12, Navin Kumar  wrote:
>>> > I think the easiest method to do this problem is this:
>>> >
>>> >
>>> http://k2code.blogspot.in/2011/09/deleting-node-in-singly-linked-list-if.html
>>> >
>>> > On Thu, May 31, 2012 at 5:58 PM, Ashish Goel 
>>> wrote:
>>> >
>>> >> that is what i have done by using recursion<=>stack.
>>> >>
>>> >> my code has problem, after  free(pCurr);, i should have return pRest;
>>> >>
>>> >> Best Regards
>>> >> Ashish Goel
>>> >> "Think positive and find fuel in failure"
>>> >> +919985813081
>>> >> +919966006652
>>> >>
>>> >>
>>> >> On Thu, May 31, 2012 at 4:37 PM, atul anand
>>> >> wrote:
>>> >>
>>> >>> then i guess ...it can be done using stack..with O(n) complexity..
>>> >>> it is similar to finding next greater element 
>>> >>>
>>> >>> http://www.geeksforgeeks.org/archives/8405
>>> >>>
>>> >>> element in the stack at the end of the algo...are the element which
>>> will
>>> >>> remain in the linked list . if stack is not empty then keep poping
>>> >>> elements
>>> >>> and create a SLL.
>>> >>>
>>> >>>
>>> >>> On Thu, May 31, 2012 at 4:29 PM, Ashish Goel 
>>> wrote:
>>> >>>
>>>  yes
>>> 
>>>  Best Regards
>>>  Ashish Goel
>>>  "Think positive and find fuel in failure"
>>>  +919985813081
>>>  +919966006652
>>> 
>>> 
>>>  On Thu, May 31, 2012 at 2:34 PM, atul anand
>>>  wrote:
>>> 
>>> > @Ashish :  please clarify this ques...
>>> >
>>> > delete a node in SLL if it is less than *any* of the succesor node
>>> ..
>>> >
>>> > 1 2 8 10 3 4 7 12
>>> >
>>> > delete 1,2,8,10,3,4,7
>>> >
>>> > ouput will be single node i.e 12
>>> >
>>> > dats what question asks?
>>> >
>>> > On Thu, May 31, 2012 at 2:16 PM, Ashish Goel 
>>> > wrote:
>>> >
>>> >> the LL is unsorted, is there any better solution that this?
>>> >>
>>> >> struct node* deleteNodes(struct node *pHead, struct node *pPrev)
>>> >> {
>>> >>   struct  node *pLL = *pHead;
>>> >>   if (!pLL) return NULL;
>>> >>   struct node *pCurr = pLL;
>>> >>
>>> >>   struct node *pRest = deleteNodes(pCurr->next, pCurr);
>>> >>   if (!pRest) return pCurr;
>>> >>   if (pCurr->data data)
>>> >>   {
>>> >> if (pPrev) { pPrev->next = pRest; };
>>> >> free(pCurr);
>>> >>   }
>>> >>  else
>>> >>  {
>>> >>pCurr->next = pRest;
>>> >>  }
>>> >>return pCurr;
>>> >> }
>>> >>
>>> >>
>>> >> Best Regards
>>> >> Ashish Goel
>>> >> "Think positive and find fuel in failure"
>>> >> +919985813081
>>> >> +919966006652
>>> >>
>>> >> --
>>> >> You received this message because you are subscribed to the Google
>>> >> Groups "Algorithm Geeks" group.
>>> >> To post to this group, send email to algogeeks@googlegroups.com.
>>> >> To unsubscribe from this group, send email to
>>> >> algogeeks+unsubscr...@googlegroups.com.
>>> >> For more options, visit this group at
>>> >> http://groups.google.com/group/algogeeks?hl=en.
>>> >>
>>> >
>>> >  --
>>> > You received this message because you are subscribed to the Google
>>> > Groups "Algorithm Geeks" group.
>>> > To post to this group, send email to algogeeks@googlegroups.com.
>>> > To unsubscribe from this group, send email to
>>> > algogeeks+unsubscr...@googlegroups.com.
>>> > For more options, visit this group at
>>> > http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> 
>>>   --
>>>  You received this message because you are subscribed to the Google
>>>  Groups "Algorithm Geeks" group.
>>>  To post to this group, send email to algogeeks@googlegroups.com.
>>>  To unsubscribe from this group, send email to
>>>  algogeeks+unsubscr...@googlegroups.com.
>>>  For more options, visit this group at
>>>  http://groups.google.com/group/algogeeks?hl=en.
>>> 
>>> >>>
>>> >>>  --
>>> >>> You r

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread atul anand 
as question says you can change the list as u like...i guess skip list is
the answer.

On Mon, Jun 4, 2012 at 3:51 PM, SANDEEP CHUGH wrote:

> can be done using skip lists
>
>
> On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh wrote:
>
>> This is possible only if Linked List is sorted then we can apply Merge
>> Sort for Linked List which would be in place.
>>
>> Otherwise the time complexity would be O(n logn).
>>
>> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>>
>>> Hi we need find a node in linked list in O(logn). You can change the
>>> list as u like.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> *Thanks,
>> Jeevitesh Shekhar Singh.*
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Matrix Minimum Path Sum

2012-06-04 Thread Hassan Monfared 
moving must be done in A* style

On Mon, Jun 4, 2012 at 1:17 PM, atul anand  wrote:

> i dont think so dijistra will worh here..bcozz we cannot move diagonally
> ...but according to matrix this path can be considered.
>
> On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared wrote:
>
>> for non-negative values Dijkstra will solve the problem in ( O(N^2) )
>> and Floyd-Warshal is the solution for negative cells. ( O(N^3) )
>>
>>
>>
>> On Mon, Jun 4, 2012 at 11:20 AM, atul anand wrote:
>>
>>> this recurrence wont work..ignore
>>>
>>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand wrote:
>>>
 find cumulative sum row[0]
 find cumulative sum of col[0]

 after this following recurrence will solve the problem.

 start from mat[1][1]

 mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] )


 On Sun, Jun 3, 2012 at 7:30 PM, Decipher wrote:

> Q) In the 5 by 5 matrix below, the minimal path sum from the top left
> to the bottom right, by moving left, right, up, and down, is indicated in
> bold red and is equal to 2297.
>
>
>  *131*
>
> 673
>
> *234*
>
> *103*
>
> *18*
>
> *201*
>
> *96*
>
> *342*
>
> 965
>
> *150*
>
> 630
>
> 803
>
> 746
>
> *422*
>
> *111*
>
> 537
>
> 699
>
> 497
>
> *121*
>
> 956
>
> 805
>
> 732
>
> 524
>
> *37*
>
> *331*
>
>
>
> Write an algorithm to find the same. Also, write an algorithm if the
> same matrix contains negative numbers (maybe negative cycle) and compare
> the space and time complexity of both.
>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>


>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread SANDEEP CHUGH 
can be done using skip lists


On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh wrote:

> This is possible only if Linked List is sorted then we can apply Merge
> Sort for Linked List which would be in place.
>
> Otherwise the time complexity would be O(n logn).
>
> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>
>> Hi we need find a node in linked list in O(logn). You can change the list
>> as u like.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> *Thanks,
> Jeevitesh Shekhar Singh.*
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: MS: searching problem......help me out...

2012-06-04 Thread Rahul Kumar Patle 
i think gene is correct in normal RAM it is impossible @abhishek you
are talking about parallel algorithms but till this extent is not possible
to implement in general computers..
@abhinav you was correct.. firsst we will have to make heap tree which is
impossible in log(n) time...

On Sun, Jun 3, 2012 at 11:23 PM, Gene  wrote:

> Finding a given element in an unsorted list in less than O(n) time
> (with a normal RAM model of computation) is easy to prove impossible.
>
> On Jun 3, 11:01 am, abhinav gupta  wrote:
> >   We have given a list 14 6 7 15 8 9 we have to find 15 in
> (log
> > n ) times.
> > --
> >
> > *Thanks and Regards,*
> >
> > Abhinav Kumar Gupta
> > **abhinav@gmail.com
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Thanks and Regards:
Rahul Kumar Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302, India
Mobile No: +91-8798049298, +91-9424738542
patlerahulku...@gmail.com
rahulkumarpa...@yahoo.com

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Simple Question ,Find Error

2012-06-04 Thread Nishant Pandey 
actually the address of name is constant and that get modifed , so
thats not possible once name is converted to pointer then this assignment
is posible .

On Mon, Jun 4, 2012 at 10:51 AM, Hassan Monfared wrote:

> you can't assign  value into names[i]!
>
>
> On Mon, Jun 4, 2012 at 3:12 AM, mahendra sengar wrote:
>
>>  main()
>> {
>> static char names[5][20]={"pascal","ada","cobol","fortran","perl"};
>> int i;
>> char *t;
>> t=names[3];
>> names[3]=names[4];
>> names[4]=t;
>> for (i=0;i<=4;i++)
>> printf("%s",names[i]);
>> }
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Cheers,

Nishant Pandey |Specialist Tools Development  |
npan...@google.com |
+91-9911258345

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Simple Question ,Find Error

2012-06-04 Thread Raghavendhra Chowdary MV 
names[3] = names[4]; //Cant be done like these as they are char arrays

On Mon, Jun 4, 2012 at 4:12 AM, mahendra sengar wrote:

>  main()
> {
> static char names[5][20]={"pascal","ada","cobol","fortran","perl"};
> int i;
> char *t;
> t=names[3];
> names[3]=names[4];
> names[4]=t;
> for (i=0;i<=4;i++)
> printf("%s",names[i]);
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Thanks & Regards,
M.V.Raghavendhra Chowdary.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread Jeevitesh 
This is possible only if Linked List is sorted then we can apply Merge Sort
for Linked List which would be in place.

Otherwise the time complexity would be O(n logn).

On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:

> Hi we need find a node in linked list in O(logn). You can change the list
> as u like.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
*Thanks,
Jeevitesh Shekhar Singh.*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Google Developer Group, New Delhi - HACK 2012 - Code for a Cause !

2012-06-04 Thread Shrey Malhotra 
Dear all,

On behalf, of *Google Developer Group New Delhi *(formerly known as* GTUG
New Delhi*) , I would like to inform you that we are going to host *H-A-C-K
- "Code for a Cause", *a hackathon, on *16-17th June* at the *Indian
Habitat Center, New Delhi*.

 *HACK- "Code for a Cause"* is being organized with the goal of bringing
> together developers, designers, startups & NGOs to apply their talents to
> the social sector and build product ideas for social innovation. It is agreat 
> chance for the developers to code  good apps that do good.


The selected themes for the event are Education, Health, Information
Access, Women Security, Disaster Management and other related to social
sector.

Can your app help India achieve the threshold literacy level? Can you
> educate the 290 million illiterates? Can it make education fun?
> Can your app help a woman in danger? Make her feel safe?
> Can your app help people know more about their health? Can it help them
> prevent diseases?



To participate, Register yourself at www.gdg-hack.com

Stop complaining, take a step and make a difference!!

You can watch the teaser video for the event here -
http://youtu.be/PR68eEWB4bk
Regards,
Shrey Malhotra
GDG New Delhi , Organizer
+91-9711455462

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread Jeevitesh 
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 you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).

I hope you get the idea.

On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma wrote:

> @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".
>> @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 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=0;len>>> >  {
 >int start1=0,start2=len+1;
 >while(start2>>> >{
 >   for(int i=0;i>>> > s[start1+i]=s[start2+i];i++);
 >   if(i==len)
 >return false; //"not valid"
 >   start1++;
 >   start2++;
 > }
 >  }
 > return true; // valid
 >
 >
 >
 >
 >
 >
 >
 > }
 > On Sun, Jun 3, 2012 at 12:52 PM, atul anand 
 wrote:
 > > can be done with O(n^2) time complexity..
 >
 > > can it be done with O(n) complexity ???
 >
 > > On 6/3/12, utsav sharma  wrote:
 > > > given a string tell wether it is valid or not.
 > > > string is valid if there is no substring which have the same
 substring
 > > > following it.
 >
 > > > these strings are not valid:- "stringstring","geek123123rt",
 > > > "abcadabcad","strngstingstrngsting"
 >
 > > > --
 > > > You received this message because you are subscribed to the
 Google Groups
 > > > "Algorithm Geeks" group.
 > > > To post to this group, send email to algogeeks@googlegroups.com.
 > > > To unsubscribe from this group, send email to
 > > > algogeeks+unsubscr...@googlegroups.com.
 > > > For more options, visit this group at
 > > >http://groups.google.com/group/algogeeks?hl=en.
 >
 > > --
 > > You received this message because you are subscribed to the Google
 Groups
 > > "Algorithm Geeks" group.
 > > To post to this group, send email to algogeeks@googlegroups.com.
 > > To unsubscribe from this group, send email to
 > > algogeeks+unsubscr...@googlegroups.com.
 > > For more options, visit this group at
 > >http://groups.google.com/group/algogeeks?hl=en.

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
*Thanks,
Jeevitesh Shekhar Singh.*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MS Question: Delete a node in single linked list if it is less than any of the successor nodes

2012-06-04 Thread Amol Sharma 
here is the question ans solution with proper explanation

http://www.geeksforgeeks.org/archives/11604

--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad








On Sat, Jun 2, 2012 at 1:21 AM, Hassan Monfared  wrote:

> 1- read all elements of list into stack
> 2- max = stak.pop()
> 3- if stack.empty() goto 7
> 4- next=stack.pop()
> 5- if next > max then max=next
>  else delete next from list
> 6- repeat from 3
> 7- end!
>
> Regards,
>
> On Thu, May 31, 2012 at 9:45 PM, atul anand wrote:
>
>> @navin : +1
>>
>> On 5/31/12, Navin Kumar  wrote:
>> > I think the easiest method to do this problem is this:
>> >
>> >
>> http://k2code.blogspot.in/2011/09/deleting-node-in-singly-linked-list-if.html
>> >
>> > On Thu, May 31, 2012 at 5:58 PM, Ashish Goel  wrote:
>> >
>> >> that is what i have done by using recursion<=>stack.
>> >>
>> >> my code has problem, after  free(pCurr);, i should have return pRest;
>> >>
>> >> Best Regards
>> >> Ashish Goel
>> >> "Think positive and find fuel in failure"
>> >> +919985813081
>> >> +919966006652
>> >>
>> >>
>> >> On Thu, May 31, 2012 at 4:37 PM, atul anand
>> >> wrote:
>> >>
>> >>> then i guess ...it can be done using stack..with O(n) complexity..
>> >>> it is similar to finding next greater element 
>> >>>
>> >>> http://www.geeksforgeeks.org/archives/8405
>> >>>
>> >>> element in the stack at the end of the algo...are the element which
>> will
>> >>> remain in the linked list . if stack is not empty then keep poping
>> >>> elements
>> >>> and create a SLL.
>> >>>
>> >>>
>> >>> On Thu, May 31, 2012 at 4:29 PM, Ashish Goel 
>> wrote:
>> >>>
>>  yes
>> 
>>  Best Regards
>>  Ashish Goel
>>  "Think positive and find fuel in failure"
>>  +919985813081
>>  +919966006652
>> 
>> 
>>  On Thu, May 31, 2012 at 2:34 PM, atul anand
>>  wrote:
>> 
>> > @Ashish :  please clarify this ques...
>> >
>> > delete a node in SLL if it is less than *any* of the succesor node
>> ..
>> >
>> > 1 2 8 10 3 4 7 12
>> >
>> > delete 1,2,8,10,3,4,7
>> >
>> > ouput will be single node i.e 12
>> >
>> > dats what question asks?
>> >
>> > On Thu, May 31, 2012 at 2:16 PM, Ashish Goel 
>> > wrote:
>> >
>> >> the LL is unsorted, is there any better solution that this?
>> >>
>> >> struct node* deleteNodes(struct node *pHead, struct node *pPrev)
>> >> {
>> >>   struct  node *pLL = *pHead;
>> >>   if (!pLL) return NULL;
>> >>   struct node *pCurr = pLL;
>> >>
>> >>   struct node *pRest = deleteNodes(pCurr->next, pCurr);
>> >>   if (!pRest) return pCurr;
>> >>   if (pCurr->data data)
>> >>   {
>> >> if (pPrev) { pPrev->next = pRest; };
>> >> free(pCurr);
>> >>   }
>> >>  else
>> >>  {
>> >>pCurr->next = pRest;
>> >>  }
>> >>return pCurr;
>> >> }
>> >>
>> >>
>> >> Best Regards
>> >> Ashish Goel
>> >> "Think positive and find fuel in failure"
>> >> +919985813081
>> >> +919966006652
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> >> Groups "Algorithm Geeks" group.
>> >> To post to this group, send email to algogeeks@googlegroups.com.
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+unsubscr...@googlegroups.com.
>> >> For more options, visit this group at
>> >> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >
>> >  --
>> > You received this message because you are subscribed to the Google
>> > Groups "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> 
>>   --
>>  You received this message because you are subscribed to the Google
>>  Groups "Algorithm Geeks" group.
>>  To post to this group, send email to algogeeks@googlegroups.com.
>>  To unsubscribe from this group, send email to
>>  algogeeks+unsubscr...@googlegroups.com.
>>  For more options, visit this group at
>>  http://groups.google.com/group/algogeeks?hl=en.
>> 
>> >>>
>> >>>  --
>> >>> You received this message because you are subscribed to the Google
>> >>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>> >>> To unsubscribe from this group, send email to
>> >>> algogeeks+unsubscr...@googlegroups.com.
>> >>> For more options, visit this group at
>> >>> http://groups.google.com/group/algogeeks?hl=en.
>> >>>
>> >>
>> >>  --
>> >> You received this messag

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread Amol Sharma 
not possible i suppose..
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad








On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:

> Hi we need find a node in linked list in O(logn). You can change the list
> as u like.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] LINKED LIST QUESTION

2012-06-04 Thread VIHARRI 
Hi we need find a node in linked list in O(logn). You can change the list 
as u like.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: amazon interview questions

2012-06-04 Thread utsav sharma 
@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.size()/2;len++)
>  {
>int start1=0,start2=len;
>while(start2{
>int i=0;
>   for(;i   if(i>=len)
>return false; //"not valid"
>   start1++;
>   start2++;
> }
>  }
> return true; // valid
> }
> It works for both input you provided. :)
>
> On Mon, Jun 4, 2012 at 8:14 AM, utsav sharma wrote:
>
>> @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".
>>> @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 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=0;len >  {
> >int start1=0,start2=len+1;
> >while(start2 >{
> >   for(int i=0;i > s[start1+i]=s[start2+i];i++);
> >   if(i==len)
> >return false; //"not valid"
> >   start1++;
> >   start2++;
> > }
> >  }
> > return true; // valid
> >
> >
> >
> >
> >
> >
> >
> > }
> > On Sun, Jun 3, 2012 at 12:52 PM, atul anand 
> wrote:
> > > can be done with O(n^2) time complexity..
> >
> > > can it be done with O(n) complexity ???
> >
> > > On 6/3/12, utsav sharma  wrote:
> > > > given a string tell wether it is valid or not.
> > > > string is valid if there is no substring which have the same
> substring
> > > > following it.
> >
> > > > these strings are not valid:- "stringstring","geek123123rt",
> > > > "abcadabcad","strngstingstrngsting"
> >
> > > > --
> > > > You received this message because you are subscribed to the
> Google Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Utsav Sharma,
NIT Allahabad

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send e

Re: [algogeeks] Matrix Minimum Path Sum

2012-06-04 Thread atul anand 
i dont think so dijistra will worh here..bcozz we cannot move diagonally
...but according to matrix this path can be considered.

On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared  wrote:

> for non-negative values Dijkstra will solve the problem in ( O(N^2) )
> and Floyd-Warshal is the solution for negative cells. ( O(N^3) )
>
>
>
> On Mon, Jun 4, 2012 at 11:20 AM, atul anand wrote:
>
>> this recurrence wont work..ignore
>>
>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand wrote:
>>
>>> find cumulative sum row[0]
>>> find cumulative sum of col[0]
>>>
>>> after this following recurrence will solve the problem.
>>>
>>> start from mat[1][1]
>>>
>>> mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] )
>>>
>>>
>>> On Sun, Jun 3, 2012 at 7:30 PM, Decipher  wrote:
>>>
 Q) In the 5 by 5 matrix below, the minimal path sum from the top left
 to the bottom right, by moving left, right, up, and down, is indicated in
 bold red and is equal to 2297.


  *131*

 673

 *234*

 *103*

 *18*

 *201*

 *96*

 *342*

 965

 *150*

 630

 803

 746

 *422*

 *111*

 537

 699

 497

 *121*

 956

 805

 732

 524

 *37*

 *331*



 Write an algorithm to find the same. Also, write an algorithm if the
 same matrix contains negative numbers (maybe negative cycle) and compare
 the space and time complexity of both.

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Matrix Minimum Path Sum

2012-06-04 Thread Hassan Monfared 
for non-negative values Dijkstra will solve the problem in ( O(N^2) )
and Floyd-Warshal is the solution for negative cells. ( O(N^3) )



On Mon, Jun 4, 2012 at 11:20 AM, atul anand  wrote:

> this recurrence wont work..ignore
>
> On Mon, Jun 4, 2012 at 8:55 AM, atul anand wrote:
>
>> find cumulative sum row[0]
>> find cumulative sum of col[0]
>>
>> after this following recurrence will solve the problem.
>>
>> start from mat[1][1]
>>
>> mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] )
>>
>>
>> On Sun, Jun 3, 2012 at 7:30 PM, Decipher  wrote:
>>
>>> Q) In the 5 by 5 matrix below, the minimal path sum from the top left to
>>> the bottom right, by moving left, right, up, and down, is indicated in bold
>>> red and is equal to 2297.
>>>
>>>
>>>  *131*
>>>
>>> 673
>>>
>>> *234*
>>>
>>> *103*
>>>
>>> *18*
>>>
>>> *201*
>>>
>>> *96*
>>>
>>> *342*
>>>
>>> 965
>>>
>>> *150*
>>>
>>> 630
>>>
>>> 803
>>>
>>> 746
>>>
>>> *422*
>>>
>>> *111*
>>>
>>> 537
>>>
>>> 699
>>>
>>> 497
>>>
>>> *121*
>>>
>>> 956
>>>
>>> 805
>>>
>>> 732
>>>
>>> 524
>>>
>>> *37*
>>>
>>> *331*
>>>
>>>
>>>
>>> Write an algorithm to find the same. Also, write an algorithm if the
>>> same matrix contains negative numbers (maybe negative cycle) and compare
>>> the space and time complexity of both.
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.