Re: [algogeeks] Re: Cpp problem
@Bhaskar u r right. I mean wen u are trying to access this function on non
constant object.
On May 28, 2012 2:08 AM, "Bhaskar Kushwaha"
wrote:
> the job of marked const here is to make the member function "operator=" as
> const so it can't modify any member function values unless that member
> function is mutable
>
> @manikanta
> the compiler will throw an error only when we try to modify any members
> inside a const member function but here we are not modifying anything thus
> no error would be there.
>
> On Mon, May 28, 2012 at 12:50 AM, Lucifer wrote:
>
>> @amrit
>> Every non-static member function of a class has an implicit parameter
>> that is passed to the function (when called) This implicit parameter
>> is nothing but the "this" pointer. Now if you want to make the
>> implicit parameter ("this" pointer) a "const", how would u do it? This
>> is done by placing the "const" keyword at the end of the function
>> signature.
>>
>> In case you want to make the "this" pointer "volatile", u can do so by
>> placing the keyword "volatile" at the end of the function signature.
>>
>>
>> On May 28, 12:05 am, Manikanta Babu wrote:
>> > Its a const member function, you cant return reference to the object.
>> >
>> > Const member function never allows you to modify the data until unless
>> its
>> > a mutable. So here we are passing the reference to object which is
>> > modifiable, it conflicts with the const member function property.
>> >
>> > So the compiler throws an error here.
>> >
>> > Thanks
>> > Mani
>> >
>> > On Mon, May 28, 2012 at 12:23 AM, amrit harry > >wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > complex_number const & operator =(complex_number & temp) const
>> > > {
>> > > return *this;
>> > > }
>> >
>> > > what is the job of marked 'const'???
>> >
>> > > --
>> > > 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/-/zjDLCIDr_p8J.
>> > > 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,
>> > Manihttp://www.sanidapa.com- The music Search engine
>>
>> --
>> 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.
>>
>>
>
>
> --
> regards,
> Bhaskar Kushwaha
> Student
> CSE
> Third year
> M.N.N.I.T. 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 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: Cpp problem
the job of marked const here is to make the member function "operator=" as
const so it can't modify any member function values unless that member
function is mutable
@manikanta
the compiler will throw an error only when we try to modify any members
inside a const member function but here we are not modifying anything thus
no error would be there.
On Mon, May 28, 2012 at 12:50 AM, Lucifer wrote:
> @amrit
> Every non-static member function of a class has an implicit parameter
> that is passed to the function (when called) This implicit parameter
> is nothing but the "this" pointer. Now if you want to make the
> implicit parameter ("this" pointer) a "const", how would u do it? This
> is done by placing the "const" keyword at the end of the function
> signature.
>
> In case you want to make the "this" pointer "volatile", u can do so by
> placing the keyword "volatile" at the end of the function signature.
>
>
> On May 28, 12:05 am, Manikanta Babu wrote:
> > Its a const member function, you cant return reference to the object.
> >
> > Const member function never allows you to modify the data until unless
> its
> > a mutable. So here we are passing the reference to object which is
> > modifiable, it conflicts with the const member function property.
> >
> > So the compiler throws an error here.
> >
> > Thanks
> > Mani
> >
> > On Mon, May 28, 2012 at 12:23 AM, amrit harry >wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > complex_number const & operator =(complex_number & temp) const
> > > {
> > > return *this;
> > > }
> >
> > > what is the job of marked 'const'???
> >
> > > --
> > > 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/-/zjDLCIDr_p8J.
> > > 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,
> > Manihttp://www.sanidapa.com- The music Search engine
>
> --
> 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.
>
>
--
regards,
Bhaskar Kushwaha
Student
CSE
Third year
M.N.N.I.T. 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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: # of paths betweek two nodes in a DAG
1) Linearize the DAG using DFS. ( topological sorting)
2) Now take an array of size A[N] ( N - nodes in the DAG ), where A[i]
mimics the 'i'th node in the linearized list.
3) Scan the linearized list from left to right to get to the source
node and initialize all the corresponding values in array A to 0.
i.e. A[1] to A[src].
4) Now use the below equation to calculate the value for no. of paths
to any node after the src node in the linearized list as follows.
i= src + 1;
while( i <=dest )
{
A[i]= sum of all ( A[j] 's);
// where (j < i) and there is a directed edge from j to
i
++i;
}
5) Return A[dest].
On May 24, 11:23 pm, MeHdi KaZemI wrote:
> Hi.
>
> DFS( k ) returns the number of paths from node k to your destination.
> so DFS( k ) is equal to the sum of DFS( p ) such that there is a forward
> edge from k->p.
>
> You have to memoize DFS for each node to prevent "calculating the number of
> paths from that node" more than one time. I do that with array 'ans'.
> Read the code and take a look at the picture and ask your question if there
> is any.
>
>
>
>
>
>
>
>
>
> On Thu, May 24, 2012 at 4:50 PM, Ashish Goel wrote:
> > My bad, i am not able to conceptualize this known problem, can anyone help
>
> > 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.
>
> --
> MeHdi KaZemI
>
> paths in dag.cpp
> < 1KViewDownload
>
> paths in dag.png
> 22KViewDownload
--
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] Re: Cpp problem
@amrit
Every non-static member function of a class has an implicit parameter
that is passed to the function (when called) This implicit parameter
is nothing but the "this" pointer. Now if you want to make the
implicit parameter ("this" pointer) a "const", how would u do it? This
is done by placing the "const" keyword at the end of the function
signature.
In case you want to make the "this" pointer "volatile", u can do so by
placing the keyword "volatile" at the end of the function signature.
On May 28, 12:05 am, Manikanta Babu wrote:
> Its a const member function, you cant return reference to the object.
>
> Const member function never allows you to modify the data until unless its
> a mutable. So here we are passing the reference to object which is
> modifiable, it conflicts with the const member function property.
>
> So the compiler throws an error here.
>
> Thanks
> Mani
>
> On Mon, May 28, 2012 at 12:23 AM, amrit harry wrote:
>
>
>
>
>
>
>
>
>
> > complex_number const & operator =(complex_number & temp) const
> > {
> > return *this;
> > }
>
> > what is the job of marked 'const'???
>
> > --
> > 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/-/zjDLCIDr_p8J.
> > 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,
> Manihttp://www.sanidapa.com- The music Search engine
--
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: Algo for Search in a 2D Matrix
Yes, navin thats a good solution... ... we dont need to work on the whole array but of size k x k (k rows and k columsn only). Rest of the array we can simply ignore.. complexity of youngify is O(k) for every removing every element. we have to remove k-1 elements so complexity of whole operation is o(k*k). Refer this pdf: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf Regards Saurabh On Mon, May 21, 2012 at 10:00 AM, Navin.nitjsr wrote: > We can consider the 2-d matrix as a heap(also called Young Tableau). > We just need to heapify(Youngify) it k-1times,then the element at > 0,0 will be kth smallest element. > This means we need to remove the k-1 smallest elements from matrix and > still maintaining its Row-Col sorted property. > Youngify algo:- > 1:- put a sentinel value (i,e, INF) 0,0 > 2:- Now push it leftwards/downwards to maintain the initial property of > matrix > 3:- If at any point the current element is smaller than both its left and > down element, then STOP. > > This is an in-place operation. > We need to consider the sentinel value as highest value,not present in the > matrix. > It works.Although the matrix is being modified. > > > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > -- > 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/-/GtGv_vms-WQJ. > > 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] Cpp problem
Its a const member function, you cant return reference to the object.
Const member function never allows you to modify the data until unless its
a mutable. So here we are passing the reference to object which is
modifiable, it conflicts with the const member function property.
So the compiler throws an error here.
Thanks
Mani
On Mon, May 28, 2012 at 12:23 AM, amrit harry wrote:
> complex_number const & operator =(complex_number & temp) const
> {
> return *this;
> }
>
>
> what is the job of marked 'const'???
>
> --
> 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/-/zjDLCIDr_p8J.
> 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,
Mani
http://www.sanidapa.com - The music Search engine
--
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] Cpp problem
const allows this function to be called on constant object.
So if someone creates an const obj of this class. Assignments can be done.
On Mon, May 28, 2012 at 12:23 AM, amrit harry wrote:
> complex_number const & operator =(complex_number & temp) const
> {
> return *this;
> }
>
>
> what is the job of marked 'const'???
>
> --
> 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/-/zjDLCIDr_p8J.
> 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] amazon
@atul:
i dont agree that "baa" should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand wrote:
> @saurabh : i kinda assumed that string will not contain
> repeated character. reason being if string has repeated character , say in
> your case "baa" then baa will be repeated
> twice hence it would be difficult to justify the output for this input
> answer could be say 2 or 3 or both are correct.
>
> On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal wrote:
>
>> @atul:
>> if i have understood ..
>> ur solution will break when the string has repeated characters.
>>
>> e.g. for "baa"
>>
>> On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty <
>> partha.mohanty2...@gmail.com> wrote:
>>
>>> sorry it was treeset Here is the code..
>>>
>>> public class asd1 {
>>>
>>>
>>> public static TreeSet t = new TreeSet();
>>> public static int j = 0;
>>> public static void main(String args[]) {
>>>
>>>
>>>
>>>
>>> String s= "edcba";
>>> permute("", s);
>>> System.out.println(t.toString());
>>> int length=t.size();
>>> String[] arr=(String[]) t.toArray(new String[length]);
>>> for(int i =0;i>> {
>>> System.out.println(arr[i]);
>>> if(arr[i].equals(s)){
>>> System.out.println(i+1);
>>> break;
>>> }
>>> }
>>> }
>>>
>>> public static void permute(String st, String chars) {
>>> if (chars.length() <= 1)
>>> t.add(st+chars);
>>> else
>>> for (int i = 0; i < chars.length(); i++) {
>>> try {
>>> String newString = chars.substring(0, i)
>>> + chars.substring(i + 1);
>>> permute(st + chars.charAt(i), newString);
>>> } catch (Exception e) {
>>> e.printStackTrace();
>>> }
>>> }
>>>
>>> }
>>> }
>>>
>>> On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty <
>>> partha.mohanty2...@gmail.com> wrote:
>>>
Java has something call treeMap. it stores strings lexographically.. u
can always do permutations and store them in a treeMap. and get the rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand wrote:
> actually we can think of above approach as follows :-
>
> input : cabd
>
> sort(input) = abcd
>
> find first element of the input i.e 'c' in the sorted form i.e abcd
>
> 'c' is at found_index=3 ( index starting from 1 )
>
> so permutaion stating from 'c' will come after temp_rank=(found_index
> - start_index) * (total_lentgh - 1) !
>
> now after temp_rank we know that permutation starting with 'c' will
> come.
>
> so to find out the exact index sort(input-1) i.e removing 1st
> character ('c') from the input(cadb) we will get abd
>
> now permute string "abd" and compare with input - 1 character i.e
> (abd).
>
> and keep inc the counter , if match is found then you have to add this
> counter to temp_rank.
>
> so for the input = cabd
>
> temp_rank = (3 - 1) * (4-1) !
> = 2 * 3!
> = 12
>
> counter found c = 1;
> rank = 12 + c = 13
>
> but i dont think this would be good solution as be have to permute
> string and then compare at last...yes we did some optimization.
> i was wondering if instead of permuting at the end , we can calculate
> minimum number of swaps required to convert input - 1 to sorted input -1
> (removing 1st character )using edit distance ...will this work?? .
>
>
> On Mon, May 21, 2012 at 11:33 PM, atul anand
> wrote:
>
>> consider string input = cabd
>> now sort this string = abcd
>>
>> now search 1st character from original string(cabd) in sorted string
>> abcd... index found = 3 (index starting from 1 )
>>
>> now you can arrange left elements from found index i.e index-1
>> elements in (index-1) ! and right elements from found index in
>> (lastIndex -
>> index)! before character 'c' occurs at index 0. similarly find for other
>> characters and at the end subtract it from n! (n = length of the string )
>> to find rank
>>
>>
>> On Mon, May 21, 2012 at 11:02 PM, rahul venkat > > wrote:
>>
>>> Given a string. Tell its rank among all its permutations sorted
>>> lexicographically.
>>>
>>> --
>>> 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.
[algogeeks] Cpp problem
complex_number const & operator =(complex_number & temp) const
{
return *this;
}
what is the job of marked 'const'???
--
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/-/zjDLCIDr_p8J.
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] amazon
@saurabh : i kinda assumed that string will not contain repeated character.
reason being if string has repeated character , say in your case "baa" then
baa will be repeated
twice hence it would be difficult to justify the output for this input
answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal wrote:
> @atul:
> if i have understood ..
> ur solution will break when the string has repeated characters.
>
> e.g. for "baa"
>
> On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty <
> partha.mohanty2...@gmail.com> wrote:
>
>> sorry it was treeset Here is the code..
>>
>> public class asd1 {
>>
>>
>> public static TreeSet t = new TreeSet();
>> public static int j = 0;
>> public static void main(String args[]) {
>>
>>
>>
>>
>> String s= "edcba";
>> permute("", s);
>> System.out.println(t.toString());
>> int length=t.size();
>> String[] arr=(String[]) t.toArray(new String[length]);
>> for(int i =0;i> {
>> System.out.println(arr[i]);
>> if(arr[i].equals(s)){
>> System.out.println(i+1);
>> break;
>> }
>> }
>> }
>>
>> public static void permute(String st, String chars) {
>> if (chars.length() <= 1)
>> t.add(st+chars);
>> else
>> for (int i = 0; i < chars.length(); i++) {
>> try {
>> String newString = chars.substring(0, i)
>> + chars.substring(i + 1);
>> permute(st + chars.charAt(i), newString);
>> } catch (Exception e) {
>> e.printStackTrace();
>> }
>> }
>>
>> }
>> }
>>
>> On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty <
>> partha.mohanty2...@gmail.com> wrote:
>>
>>> Java has something call treeMap. it stores strings lexographically.. u
>>> can always do permutations and store them in a treeMap. and get the rank
>>> then... just the idea.. will post the solution once i am done.. what do u
>>> guys think.abt the idea???
>>>
>>>
>>> On Tue, May 22, 2012 at 9:46 AM, atul anand wrote:
>>>
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index -
start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string "abd" and compare with input - 1 character i.e (abd).
and keep inc the counter , if match is found then you have to add this
counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can calculate
minimum number of swaps required to convert input - 1 to sorted input -1
(removing 1st character )using edit distance ...will this work?? .
On Mon, May 21, 2012 at 11:33 PM, atul anand
wrote:
> consider string input = cabd
> now sort this string = abcd
>
> now search 1st character from original string(cabd) in sorted string
> abcd... index found = 3 (index starting from 1 )
>
> now you can arrange left elements from found index i.e index-1
> elements in (index-1) ! and right elements from found index in (lastIndex
> -
> index)! before character 'c' occurs at index 0. similarly find for other
> characters and at the end subtract it from n! (n = length of the string )
> to find rank
>
>
> On Mon, May 21, 2012 at 11:02 PM, rahul venkat
> wrote:
>
>> Given a string. Tell its rank among all its permutations sorted
>> lexicographically.
>>
>> --
>> 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 unsubscrib
Re: [algogeeks] amazon
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for "baa"
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty <
partha.mohanty2...@gmail.com> wrote:
> sorry it was treeset Here is the code..
>
> public class asd1 {
>
>
> public static TreeSet t = new TreeSet();
> public static int j = 0;
> public static void main(String args[]) {
>
>
>
>
> String s= "edcba";
> permute("", s);
> System.out.println(t.toString());
> int length=t.size();
> String[] arr=(String[]) t.toArray(new String[length]);
> for(int i =0;i {
> System.out.println(arr[i]);
> if(arr[i].equals(s)){
> System.out.println(i+1);
> break;
> }
> }
> }
>
> public static void permute(String st, String chars) {
> if (chars.length() <= 1)
> t.add(st+chars);
> else
> for (int i = 0; i < chars.length(); i++) {
> try {
> String newString = chars.substring(0, i)
> + chars.substring(i + 1);
> permute(st + chars.charAt(i), newString);
> } catch (Exception e) {
> e.printStackTrace();
> }
> }
>
> }
> }
>
> On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty <
> partha.mohanty2...@gmail.com> wrote:
>
>> Java has something call treeMap. it stores strings lexographically.. u
>> can always do permutations and store them in a treeMap. and get the rank
>> then... just the idea.. will post the solution once i am done.. what do u
>> guys think.abt the idea???
>>
>>
>> On Tue, May 22, 2012 at 9:46 AM, atul anand wrote:
>>
>>> actually we can think of above approach as follows :-
>>>
>>> input : cabd
>>>
>>> sort(input) = abcd
>>>
>>> find first element of the input i.e 'c' in the sorted form i.e abcd
>>>
>>> 'c' is at found_index=3 ( index starting from 1 )
>>>
>>> so permutaion stating from 'c' will come after temp_rank=(found_index -
>>> start_index) * (total_lentgh - 1) !
>>>
>>> now after temp_rank we know that permutation starting with 'c' will come.
>>>
>>> so to find out the exact index sort(input-1) i.e removing 1st character
>>> ('c') from the input(cadb) we will get abd
>>>
>>> now permute string "abd" and compare with input - 1 character i.e (abd).
>>>
>>> and keep inc the counter , if match is found then you have to add this
>>> counter to temp_rank.
>>>
>>> so for the input = cabd
>>>
>>> temp_rank = (3 - 1) * (4-1) !
>>> = 2 * 3!
>>> = 12
>>>
>>> counter found c = 1;
>>> rank = 12 + c = 13
>>>
>>> but i dont think this would be good solution as be have to permute
>>> string and then compare at last...yes we did some optimization.
>>> i was wondering if instead of permuting at the end , we can calculate
>>> minimum number of swaps required to convert input - 1 to sorted input -1
>>> (removing 1st character )using edit distance ...will this work?? .
>>>
>>>
>>> On Mon, May 21, 2012 at 11:33 PM, atul anand wrote:
>>>
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted string
abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1 elements
in (index-1) ! and right elements from found index in (lastIndex - index)!
before character 'c' occurs at index 0. similarly find for other characters
and at the end subtract it from n! (n = length of the string ) to find rank
On Mon, May 21, 2012 at 11:02 PM, rahul venkat
wrote:
> Given a string. Tell its rank among all its permutations sorted
> lexicographically.
>
> --
> 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/algog
Re: [algogeeks] Re: Google Q : all anagrams next to each other
@jalaj :- we will be sorting a copy of the word and then matching the sorted_sequence with the sorted_sequence of the copy of other words. It will still be in-place, because we are using a space of Word size where the input is a dictionary. This is an amortized in-place. -- Navin Kumar Gupta Computer Science & Engg. National Institute of Technology,Jamshedpur -- 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/-/n2tGzVxSLIYJ. 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: classic problem to tree to circular doubly linked list
@Gene :
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root->left;
root->left = convert(root->right, list);
return *tree(left_subtree, root);*
}
what *tree(left_subtree, root)* function doing here??
On Sun, May 27, 2012 at 7:12 PM, Gene wrote:
> Another approach is to form a singly linked, NULL-terminated list
> (connected e.g. by 'left' pointers). This is a harder problem, and
> it
> might be required if you have a purpose for the other (right)
> pointer. If you need a doubly linked list it's easy to walk down the
> singly linked one, creating 'previous' pointers as you go.
> The converter accepts both a tree and list that's already in the
> correct order, which should be appended at the end of the converted
> tree. The result of the append operation should be returned.
>
> NODE *convert(NODE *root, NODE *list)
> {
> if (root == NULL) return list;
> NODE *left_subtree = root->left;
> root->left = convert(root->right, list);
> return tree(left_subtree, root);
> }
>
> I like this solution because it's so simple. Initiate it with
> convert(tree, NULL);
>
> If you really need the double links:
>
> void adjust(NODE *head)
> {
> NODE *p, *q;
> for (q = NULL, p = head; p; q = p, p = p->next)
>p->right = q;
> head->right = q;
> q->right = head;
> }
>
>
> On May 26, 3:07 am, jalaj jaiswal wrote:
> > Both the explanations above are wrong . It is true that BST can be
> > converted to a Doubly linked list by doing inorder traversal.
> >
> > But the approach mentioned in the stanford link follows a postorder
> > Approach , it is better because it avoids useage of a static/global
> > variable which is required in inorder Approach.
> > "recursively changing the small and large sub-trees into lists, and then
> > append those lists together with the parent node to make larger lists" -
> > quoted from the stanford page. (parent is visited after the subtrees)
> >
> > Explanation of the postorder Approach :-
> >
> > refer to the drawing in the page.
> > FIrst of all it makes the node named 1 as a an independent node after
> that
> > as in postorder it makes node 3 as an independent node . Independent here
> > means
> > root->left=root->right=NULL.
> >
> > After that it comes to node 2 . ( Note that it is happening in postorder
> > fashion) .
> > then it makes node 2 as independent and append it with the list returned
> > from left side(which is independent node 1) and list returned from right
> > side *(which is independent node 3) and make the left side returned node
> as
> > head and follows the process recursively . The order is similar to
> inorder
> > apptoach which is O(n).
> >
> > *IF you want to know the inorder approach as well, Here it is :-*
> >
> > void BSTTODLL( node *root){
> > static int count = 0 ;
> > static node * temp = NULL:
> >if(root != NULL){
> > BSTTODLL(root->left);
> > if(count == 0) {
> > temp = root;
> > count++;
> > }
> > temp->right= root;
> > root->left = temp;
> > temp = root;
> > BSTTODLL(root->right);
> > }
> >
> > }
> >
> > // explanation is trivial , its just keeping a temp pointer to previous
> > node and adjusting pointers in inorder fashion keeping the list sorted.
> >
> > Hope it Helps !
> >
> > On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
> > wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > the main code is dis function only:i will explain dis
> >
> > > static Node treeToList(Node root) {
> > > Node aList, bList;
> >
> > > if (root==NULL) return(NULL);*
> > > /* the below next two lines are just lyk inorder traversal...u mst
> hv done dis*/*
> > > aList = treeToList(root->small);
> > > bList = treeToList(root->large);
> >
> > > */* this is for breaking the links of its left n right child nodes
> n pointing to itself*/*
> > > root->small = root;
> > > root->large = root;
> >
> > >* /* Appending leftchild parent n rightchild together in
> doublylinked list form */*
> > > aList = append(aList, root);
> > > aList = append(aList, bList);
> >
> > > return(aList);
> > > }
> >
> > > --
> > > 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.
> >
> > Regards,
> >
> > Jalaj Jaiswal
> > Software Developer,
> > Adobe Systems
> > +91-9019947895
> > *
> > *
> > FACEBOOK
> > LINKEDIN
>
> --
> 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
[algogeeks] Re: classic problem to tree to circular doubly linked list
Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and
it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating 'previous' pointers as you go.
The converter accepts both a tree and list that's already in the
correct order, which should be appended at the end of the converted
tree. The result of the append operation should be returned.
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root->left;
root->left = convert(root->right, list);
return tree(left_subtree, root);
}
I like this solution because it's so simple. Initiate it with
convert(tree, NULL);
If you really need the double links:
void adjust(NODE *head)
{
NODE *p, *q;
for (q = NULL, p = head; p; q = p, p = p->next)
p->right = q;
head->right = q;
q->right = head;
}
On May 26, 3:07 am, jalaj jaiswal wrote:
> Both the explanations above are wrong . It is true that BST can be
> converted to a Doubly linked list by doing inorder traversal.
>
> But the approach mentioned in the stanford link follows a postorder
> Approach , it is better because it avoids useage of a static/global
> variable which is required in inorder Approach.
> "recursively changing the small and large sub-trees into lists, and then
> append those lists together with the parent node to make larger lists" -
> quoted from the stanford page. (parent is visited after the subtrees)
>
> Explanation of the postorder Approach :-
>
> refer to the drawing in the page.
> FIrst of all it makes the node named 1 as a an independent node after that
> as in postorder it makes node 3 as an independent node . Independent here
> means
> root->left=root->right=NULL.
>
> After that it comes to node 2 . ( Note that it is happening in postorder
> fashion) .
> then it makes node 2 as independent and append it with the list returned
> from left side(which is independent node 1) and list returned from right
> side *(which is independent node 3) and make the left side returned node as
> head and follows the process recursively . The order is similar to inorder
> apptoach which is O(n).
>
> *IF you want to know the inorder approach as well, Here it is :-*
>
> void BSTTODLL( node *root){
> static int count = 0 ;
> static node * temp = NULL:
> if(root != NULL){
> BSTTODLL(root->left);
> if(count == 0) {
> temp = root;
> count++;
> }
> temp->right= root;
> root->left = temp;
> temp = root;
> BSTTODLL(root->right);
> }
>
> }
>
> // explanation is trivial , its just keeping a temp pointer to previous
> node and adjusting pointers in inorder fashion keeping the list sorted.
>
> Hope it Helps !
>
> On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
> wrote:
>
>
>
>
>
>
>
>
>
> > the main code is dis function only:i will explain dis
>
> > static Node treeToList(Node root) {
> > Node aList, bList;
>
> > if (root==NULL) return(NULL);*
> > /* the below next two lines are just lyk inorder traversal...u mst hv
> > done dis*/*
> > aList = treeToList(root->small);
> > bList = treeToList(root->large);
>
> > */* this is for breaking the links of its left n right child nodes n
> > pointing to itself*/*
> > root->small = root;
> > root->large = root;
>
> > * /* Appending leftchild parent n rightchild together in doublylinked
> > list form */*
> > aList = append(aList, root);
> > aList = append(aList, bList);
>
> > return(aList);
> > }
>
> > --
> > 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.
>
> Regards,
>
> Jalaj Jaiswal
> Software Developer,
> Adobe Systems
> +91-9019947895
> *
> *
> FACEBOOK
> LINKEDIN
--
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] Re: classic problem to tree to circular doubly linked list
Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating 'previous' pointers as you go.
The converter accepts both a tree and list that's already in the
correct order, which should be appended at the end of the converted
tree. The result of the append operation should be returned.
NODE *convert(NODE *tree, NODE *list)
{
if (tree == NULL) return list;
On May 26, 3:07 am, jalaj jaiswal wrote:
> Both the explanations above are wrong . It is true that BST can be
> converted to a Doubly linked list by doing inorder traversal.
>
> But the approach mentioned in the stanford link follows a postorder
> Approach , it is better because it avoids useage of a static/global
> variable which is required in inorder Approach.
> "recursively changing the small and large sub-trees into lists, and then
> append those lists together with the parent node to make larger lists" -
> quoted from the stanford page. (parent is visited after the subtrees)
>
> Explanation of the postorder Approach :-
>
> refer to the drawing in the page.
> FIrst of all it makes the node named 1 as a an independent node after that
> as in postorder it makes node 3 as an independent node . Independent here
> means
> root->left=root->right=NULL.
>
> After that it comes to node 2 . ( Note that it is happening in postorder
> fashion) .
> then it makes node 2 as independent and append it with the list returned
> from left side(which is independent node 1) and list returned from right
> side *(which is independent node 3) and make the left side returned node as
> head and follows the process recursively . The order is similar to inorder
> apptoach which is O(n).
>
> *IF you want to know the inorder approach as well, Here it is :-*
>
> void BSTTODLL( node *root){
> static int count = 0 ;
> static node * temp = NULL:
> if(root != NULL){
> BSTTODLL(root->left);
> if(count == 0) {
> temp = root;
> count++;
> }
> temp->right= root;
> root->left = temp;
> temp = root;
> BSTTODLL(root->right);
> }
>
> }
>
> // explanation is trivial , its just keeping a temp pointer to previous
> node and adjusting pointers in inorder fashion keeping the list sorted.
>
> Hope it Helps !
>
> On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
> wrote:
>
>
>
>
>
>
>
>
>
> > the main code is dis function only:i will explain dis
>
> > static Node treeToList(Node root) {
> > Node aList, bList;
>
> > if (root==NULL) return(NULL);*
> > /* the below next two lines are just lyk inorder traversal...u mst hv
> > done dis*/*
> > aList = treeToList(root->small);
> > bList = treeToList(root->large);
>
> > */* this is for breaking the links of its left n right child nodes n
> > pointing to itself*/*
> > root->small = root;
> > root->large = root;
>
> > * /* Appending leftchild parent n rightchild together in doublylinked
> > list form */*
> > aList = append(aList, root);
> > aList = append(aList, bList);
>
> > return(aList);
> > }
>
> > --
> > 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.
>
> Regards,
>
> Jalaj Jaiswal
> Software Developer,
> Adobe Systems
> +91-9019947895
> *
> *
> FACEBOOK
> LINKEDIN
--
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 question : string compression
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta wrote:
> This is called Run-Length-Encoding (RLE) of a string.
> Its purpose is to save space.So in case of abcdef,I think the output
> needed is abcdef (1 is implicit).
> The added benefit is it makes the solution in-place.
>
> Approach:- (In-place and Linear Time)
> Start from the left of string and PREVIOUS_CHAR = str[0]
> move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
> count of PREVIOUS_CHAR
> At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
>put the count of prev_char next to the start position of the previous
> character.
>
> Below is the working code :-
> void torle(char *str)
> { int i=0,j=0,k=0,cnt=1;
> char cur_char=str[0],num[100];
> while(str[j+1])
> {
> cnt=1;
> while(str[j+1]==cur_char && str[j]!='\0'){
> j++;
> cnt++;
> }
> str[i++]=cur_char;
> if( cnt>9 ){
> itoa(cnt,num);
> k=0;
> while(num[k]) str[i++]=num[k++];
> }
> else if( cnt>1 && cnt<10 )
> str[i++]= cnt+'0';
> j++;
> if(str[j]) cur_char=str[j];
> }
> if(i!=0){
> if(cnt==1)
> str[i++]=cur_char;
> str[i]='\0';
>
> }
> }
>
>
> On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
>>
>> Implement a method to perform basic string compression using the counts
>> of repeated characters.(inplace)
>>
>> eg:- input: "aaabcdef"
>> output:"3a5b1c1d1e1f".
>>
>> what should be my approach to this problem
>>
>> if i calculate the size of array required to store the output string
>> and start from the last of the array then i wldn't get the right answer
>> of above input case.
>>
>> and if start from front then i wldn't get the right answer of this input
>> case
>> eg:- input: "abcdef"
>> output: "1a1b1c1d1e1f"
>>
> --
> 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/-/4LxWHEUJuK8J.
>
> 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 qn
http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance On Tue, May 22, 2012 at 7:06 PM, aanchal goyal wrote: > @Lucifer, do we need to add insert and del operations in the > transformation formula u gave? Isn't it just the number of substitutions/2? > > -- > 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.
