[algogeeks] Re: linked lists
@asquare basically i just added a flag to enable the "window slide". good catch btw! On Oct 20, 7:55 am, Asquare wrote: > @ligerdave - > your algo will fail in the case the two arrays are: > > hellostl > eeelexander > > ans : hellostlexander > but according to ur method the answer would end up being > hellostleeelexander -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: linked lists
@Asquare
you were right. what about this?
public static char[] concat(char[] str1, char[] str2) {
boolean repeat = false;// indicates whether two neighbor chars
repeat in
// str1 array
int pointer = -1; // pointer for str2 array
for (int i = 0; i < str1.length; i++) {
if (pointer + 1 >= str2.length) {
pointer = -1;
break;
}
if (str1[i] == str2[pointer + 1]) {
pointer++;
repeat = (i > 0 && (str1[i] == str1[i - 1]));
} else {
if (!repeat)
pointer = -1;
}
}
char[] result = null;
if (pointer != -1) {
result = new char[str1.length + str2.length - (pointer
+ 1)];
System.arraycopy(str1, 0, result, 0, str1.length);
System.arraycopy(str2, pointer + 1, result, str1.length,
str2.length
- pointer - 1);
}
return result;
}
On Oct 20, 7:55 am, Asquare wrote:
> @ligerdave -
> your algo will fail in the case the two arrays are:
>
> hellostl
> eeelexander
>
> ans : hellostlexander
> but according to ur method the answer would end up being
> hellostleeelexander
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: linked lists
@ligerdave - your algo will fail in the case the two arrays are: hellostl eeelexander ans : hellostlexander but according to ur method the answer would end up being hellostleeelexander -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: linked lists
Is there any additional condition saying if last 'n' characters of first list should match with first 'n' characters of 2nd list ? On Oct 7, 12:52 pm, snehal jain wrote: > There are two linked list, both containing a character in each node. > > If one linked list contain characters o x e n c and second contain > characters e n c a r t a then the final linked list should contain o x > e n c a r t a i.e. if the end of one list is same as the start of > second then those characters should come only once. > > can we do it in O(n+m) where n and m are the length of list. both are > singly link list. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: linked lists
@Snehal...wat ligerdave says is have ptr1 for list1 and ptr2 for list2. if(ptr1->data==ptr2->data)increment both ptr1 and ptr2 else reset ptr2 to the head of list2 , increment ptr1 ptr2 position gives from where we need to concatenate. On Sat, Oct 9, 2010 at 12:21 AM, ashita dadlani wrote: > I think we can use KMP string matching algorithm. > > > On Fri, Oct 8, 2010 at 6:40 PM, shashank jain wrote: > >> there are 2 unsorted array we have to want a third array in sorted >> form in mininmum time complexicity >> >> answer can like be this merge the two array in 3rd array then sort the >> array >> >> or >> sort the individual array and then merge >> >> if feel first one is better >> >> can any one can help >> >> >> On 10/8/10, snehal jain wrote: >> > @ligerdave >> > m nt getting ur algo..can u explain with an example >> > >> > >> > On 10/8/10, snehal jain wrote: >> >> >> >> @neeraj >> >> ur worst case complexity will be O(mn) >> >> >> >> >> >> On 10/8/10, snehal jain wrote: >> >>> >> >>> @tech >> >>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with >> >>> prefix of 2nd >> >>> >> >>> >> >>> On 10/7/10, ligerdave wrote: >> >> use pointer. shift to left if one more leading char has been found. >> any unmatched char resets the pointer to first char >> >> once you went through the entire list(first one), the pointer on the >> second list tells you where to concatenate >> >> that gives you O(n) where n is the length of first list >> >> On Oct 7, 3:52 am, snehal jain wrote: >> > There are two linked list, both containing a character in each >> node. >> > >> > If one linked list contain characters o x e n c and second contain >> > characters e n c a r t a then the final linked list should contain >> o x >> > e n c a r t ai.e. if the end of one list is same as the start >> of >> > second then those characters should come only once. >> > >> > can we do it in O(n+m) where n and m are the length of list. both >> are >> > singly link list. >> >> -- >> You received this message because you are subscribed to the Google >> Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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. > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: linked lists
I think we can use KMP string matching algorithm. On Fri, Oct 8, 2010 at 6:40 PM, shashank jain wrote: > there are 2 unsorted array we have to want a third array in sorted > form in mininmum time complexicity > > answer can like be this merge the two array in 3rd array then sort the > array > > or > sort the individual array and then merge > > if feel first one is better > > can any one can help > > > On 10/8/10, snehal jain wrote: > > @ligerdave > > m nt getting ur algo..can u explain with an example > > > > > > On 10/8/10, snehal jain wrote: > >> > >> @neeraj > >> ur worst case complexity will be O(mn) > >> > >> > >> On 10/8/10, snehal jain wrote: > >>> > >>> @tech > >>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with > >>> prefix of 2nd > >>> > >>> > >>> On 10/7/10, ligerdave wrote: > > use pointer. shift to left if one more leading char has been found. > any unmatched char resets the pointer to first char > > once you went through the entire list(first one), the pointer on the > second list tells you where to concatenate > > that gives you O(n) where n is the length of first list > > On Oct 7, 3:52 am, snehal jain wrote: > > There are two linked list, both containing a character in each node. > > > > If one linked list contain characters o x e n c and second contain > > characters e n c a r t a then the final linked list should contain o > x > > e n c a r t ai.e. if the end of one list is same as the start of > > second then those characters should come only once. > > > > can we do it in O(n+m) where n and m are the length of list. both > are > > singly link list. > > -- > You received this message because you are subscribed to the Google > Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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: linked lists
there are 2 unsorted array we have to want a third array in sorted form in mininmum time complexicity answer can like be this merge the two array in 3rd array then sort the array or sort the individual array and then merge if feel first one is better can any one can help On 10/8/10, snehal jain wrote: > @ligerdave > m nt getting ur algo..can u explain with an example > > > On 10/8/10, snehal jain wrote: >> >> @neeraj >> ur worst case complexity will be O(mn) >> >> >> On 10/8/10, snehal jain wrote: >>> >>> @tech >>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with >>> prefix of 2nd >>> >>> >>> On 10/7/10, ligerdave wrote: use pointer. shift to left if one more leading char has been found. any unmatched char resets the pointer to first char once you went through the entire list(first one), the pointer on the second list tells you where to concatenate that gives you O(n) where n is the length of first list On Oct 7, 3:52 am, snehal jain wrote: > There are two linked list, both containing a character in each node. > > If one linked list contain characters o x e n c and second contain > characters e n c a r t a then the final linked list should contain o x > e n c a r t ai.e. if the end of one list is same as the start of > second then those characters should come only once. > > can we do it in O(n+m) where n and m are the length of list. both are > singly link list. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: linked lists
@ligerdave m nt getting ur algo..can u explain with an example On 10/8/10, snehal jain wrote: > > @neeraj > ur worst case complexity will be O(mn) > > > On 10/8/10, snehal jain wrote: >> >> @tech >> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with >> prefix of 2nd >> >> >> On 10/7/10, ligerdave wrote: >>> >>> use pointer. shift to left if one more leading char has been found. >>> any unmatched char resets the pointer to first char >>> >>> once you went through the entire list(first one), the pointer on the >>> second list tells you where to concatenate >>> >>> that gives you O(n) where n is the length of first list >>> >>> On Oct 7, 3:52 am, snehal jain wrote: >>> > There are two linked list, both containing a character in each node. >>> > >>> > If one linked list contain characters o x e n c and second contain >>> > characters e n c a r t a then the final linked list should contain o x >>> > e n c a r t ai.e. if the end of one list is same as the start of >>> > second then those characters should come only once. >>> > >>> > can we do it in O(n+m) where n and m are the length of list. both are >>> > singly link list. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@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 algoge...@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: linked lists
@neeraj ur worst case complexity will be O(mn) On 10/8/10, snehal jain wrote: > > @tech > the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with > prefix of 2nd > > > On 10/7/10, ligerdave wrote: >> >> use pointer. shift to left if one more leading char has been found. >> any unmatched char resets the pointer to first char >> >> once you went through the entire list(first one), the pointer on the >> second list tells you where to concatenate >> >> that gives you O(n) where n is the length of first list >> >> On Oct 7, 3:52 am, snehal jain wrote: >> > There are two linked list, both containing a character in each node. >> > >> > If one linked list contain characters o x e n c and second contain >> > characters e n c a r t a then the final linked list should contain o x >> > e n c a r t ai.e. if the end of one list is same as the start of >> > second then those characters should come only once. >> > >> > can we do it in O(n+m) where n and m are the length of list. both are >> > singly link list. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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 algoge...@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: linked lists
@tech the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with prefix of 2nd On 10/7/10, ligerdave wrote: > > use pointer. shift to left if one more leading char has been found. > any unmatched char resets the pointer to first char > > once you went through the entire list(first one), the pointer on the > second list tells you where to concatenate > > that gives you O(n) where n is the length of first list > > On Oct 7, 3:52 am, snehal jain wrote: > > There are two linked list, both containing a character in each node. > > > > If one linked list contain characters o x e n c and second contain > > characters e n c a r t a then the final linked list should contain o x > > e n c a r t ai.e. if the end of one list is same as the start of > > second then those characters should come only once. > > > > can we do it in O(n+m) where n and m are the length of list. both are > > singly link list. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: linked lists
use pointer. shift to left if one more leading char has been found. any unmatched char resets the pointer to first char once you went through the entire list(first one), the pointer on the second list tells you where to concatenate that gives you O(n) where n is the length of first list On Oct 7, 3:52 am, snehal jain wrote: > There are two linked list, both containing a character in each node. > > If one linked list contain characters o x e n c and second contain > characters e n c a r t a then the final linked list should contain o x > e n c a r t a i.e. if the end of one list is same as the start of > second then those characters should come only once. > > can we do it in O(n+m) where n and m are the length of list. both are > singly link list. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
