[algogeeks] Re: Google Q : all anagrams next to each other

[Gene]

This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.

You don't need to compute a hash at all.  Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort.  If you are using Latin (8-bit) characters, you don't even need
to complete the counting sort.  Just do the counting into arrays of
256 ints.  You'll end up with character histograms.  It's easy to
compare these rather than sorted strings.  They require O(2 log C) =
O(log C) storage and comparing them needs O(log C) int comparisons,
where C is the number of characters in the alphabet.  Since C is a
constant, this would normally be considered O(1) time and space.

On May 26, 2:52 am, jalaj jaiswal  wrote:
> If you sort every word , then you will lose the original word as Ankita
> pointed out and if you keep a hashmap to track that it will not be inplace
> .,
>
> Is there any problem in the solution I gave Above , please point it out .
>
>
>
>
>
>
>
>
>
> On Fri, May 25, 2012 at 1:14 AM, Anika Jain  wrote:
> > I have a doubt. If u r doing inplace sorting of a word during checks for a
> > word, wouldnt that change that word there itself? then how will the
> > original anagram get restored to arrange in the output in sorted manner?
>
> > On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar 
> > wrote:
>
> >> The complexity will be (N^2)W because the sorting can be done linear time
> >> O(W) for strings.
>
> >> On Thu, May 24, 2012 at 3:44 PM, WgpShashank  >> > wrote:
>
> >>> Yeah , its the in-place approach strikes in mind at first look , just
> >>> slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of
> >>> words in array & W is length of longest word in array , let me know i
> >>> missed something ?
>
> >>>  original                 eat I ate att I the eel eth het
> >>>  after sorting          I I ate att can eat eel eth het the
>
> >>> output should be  I I ate eat att can eel eth het the
>
> >>> Shashank Mani Narayan
> >>> Computer Science & Engineering
> >>> Birla Institute of Technology,Mesra
> >>> Founder Cracking The Code Lab  "http://shashank7s.blogspot.com/";
> >>> FB Pagehttp://www.facebook.com/pages/LestCode
> >>> Google+http://gplus.to/wgpshashank
> >>> Twitter "https://twitter.com/wgpshashank";
> >>> Puzzled Guy @ "http://ashutosh7s.blogspot.com";
> >>> FB Pagehttp://www.facebook.com/Puzzles.For.Puzzled.Minds
>
> >>> On May 22, 8:18 am, Navin Gupta  wrote:
> >>> > It can be done inplace, then Time Complexity will be O( N^2 x W )
> >>> where N
> >>> > is no. of words and  W is word size.
> >>> > Start from the left and sort the current word.
> >>> > Keep a pointer  PTR  to the first index of the element left to process.
> >>> > Initially it will be 0.As we add words this pointer moves forwards.
> >>> > Now iterate the whole list of words to find all those words having same
> >>> > sorted sequence i.e. anagrams
> >>> > Whenver we get a word which is anagram of the current string, swap it
> >>> with
> >>> > the string  pointed by PTR, move PTR forward.
>
> >>> > pseudoCode :-
>
> >>> > func( vector v)
> >>> > {
> >>> >    int n=v.size();
> >>> >    for(int i=0;i >>> >    {
> >>> >       string currentWord = v[i];
> >>> >       sort(currentWord);
> >>> >       for(int j=i+1;j >>> >       {
> >>> >           if ( sort(v[j]) == currentWord )    // anagrams found,
> >>> >           {
> >>> >                swap( v[i] , v[j] );                 //move this string
> >>> to
> >>> > the position next to pos of currentWord
> >>> >                  i++;                                //and move the
> >>> index
> >>> > of currentWord forward
> >>> >           }
> >>> >      }
>
> >>> > }
>
> >>> --
> >>> 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.
>
> >> --
> >> With regards,
>
> >> Jitender Kumar
> >> 3rd year (Computer Engineering)
> >> NIT Kurukshetra
> >> Kurukshetra- 136119
> >>  Mobile  +91-8529035751
>
> >>  --
> >> 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
> > Anika Jain
>
> >  --
> > 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 t

Re: [algogeeks] Re: Algorithm page

[Wladimir Tavares]

More posts:
http://marathoncode.blogspot.com.br/2012/04/list-comprehension-and-generator.html
http://marathoncode.blogspot.com.br/2012/04/floating-point-arithmetic-with.html
http://marathoncode.blogspot.com.br/2012/05/algoritmos-gulosos.html
http://marathoncode.blogspot.com.br/2012/05/algoritmos-de-tentativa-e-erro.html
http://marathoncode.blogspot.com.br/2012/05/introducao-ao-haskell.html
http://marathoncode.blogspot.com.br/2012/04/paralelismo-de-bits.html
http://marathoncode.blogspot.com.br/2012/04/inverso-multiplicativo.html
http://marathoncode.blogspot.com.br/2012/04/usando-pthread.html




Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*




On Mon, Apr 16, 2012 at 7:34 PM, Wladimir Tavares wrote:

> Great Job!!
>
> Wladimir Araujo Tavares
> *Federal University of Ceará 
> Homepage  | 
> Maratona|
> *
>
>
>
>
> On Mon, Apr 16, 2012 at 2:34 PM, Praveen Kumar wrote:
>
>>
>> Here[0] is one of the post(
>> http://marathoncode.blogspot.com.br/2012/03/alguns-truques-da-linguagem-c.html)
>> by Wladimir in english
>>
>> [0]http://codewar.in/c-tricks-vectors-and-algorithm-in-stl/
>>
>>
>> --
>> Cheers
>>
>>
>>  --
>> 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] Re: MS question : string compression

[Navin Gupta]

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.

Re: [algogeeks] Amazon Q: Implement an algorithm to do wild card string matching

[atul anand]

typo error above resolved :-

match(*input , *pattern)
if(*pat == 0)
 return true;

  if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)

  if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)

   if(*input == *pat)
 return match(input+1,pat+1)
  return 0;

On Sat, May 26, 2012 at 2:39 PM, atul anand  wrote:

>
> match(*input , *pattern)
> if(*pat == 0)
>  return true;
>
>   if('?' == *pat)
> return match(input+1,pat+1) || match(input,pat+1)
>
>   if('*' == *pat)
> return match(input+1,pat) || match(input,pat+1)
>
>if(*text == *pat)
>  return match(input+1,pat+1)
>   return 0;
>
> take care of base cases..
> On Sat, May 26, 2012 at 2:16 PM, Ashish Goel  wrote:
>
>> Implement an algorithm to do wild card string matching
>>
>>
>> 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.

Re: [algogeeks] Amazon Q: Implement an algorithm to do wild card string matching

[atul anand]

match(*input , *pattern)
if(*pat == 0)
 return true;

  if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)

  if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)

   if(*text == *pat)
 return match(input+1,pat+1)
  return 0;

take care of base cases..
On Sat, May 26, 2012 at 2:16 PM, Ashish Goel  wrote:

> Implement an algorithm to do wild card string matching
>
>
> 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] Amazon Q : Design a logWritter for server kind of application

[Ashish Goel]

Design a logWritter for server kind of application


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.

[algogeeks] Amazon Q: Implement an algorithm to do wild card string matching

[Ashish Goel]

Implement an algorithm to do wild card string matching


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] Re: MS question : string compression

[Ashish Goel]

http://michael.dipperstein.com/rle/index.html

and basic one is

http://www.fileformat.info/mirror/egff/ch09_03.htm


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


On Sat, May 26, 2012 at 1:10 PM, Hassan Monfared wrote:

> 1- try "abb"
>
>
> On Sat, May 26, 2012 at 12:07 PM, Anchal Gupta wrote:
>
>> yeah i forgot inplace so to do that we simply add count and ch in str
>> input array instead of op.
>> btw whats wrong with count it give me right answer.
>>
>> On May 26, 12:08 pm, Hassan Monfared  wrote:
>> > u forgot to do "inplace" and you have wrong conversion of count
>> >
>> > On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta > >wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > hey, here is the function that do the compression and store the output
>> > > in an array op.
>> >
>> > > void str_comp(char *str)
>> > > {
>> > >  int count=0,j=0,i;
>> > >  char ch,op[100];
>> >
>> > >  for(i=0;i> > >  {
>> > >ch = str[i];
>> > >while(str[i] == ch)
>> > >  { count++;
>> > >i++;
>> > >  }
>> > > op[j] = count+48;
>> > > op[++j] = ch;
>> > > j++;
>> > > count=0;
>> >
>> > >   }
>> > >   cout<<"input : ";
>> > >   for(i=0;i> > >cout<> >
>> > >   cout<<"\n\noutput : ";
>> > >   for(i=0;i> > >cout<> >
>> > >  }
>> >
>> > > Best Regards
>> > > Anchal Gupta
>> > > USIT(GGSIPU), Delhi
>> > > +91-9015897983
>> >
>> > > --
>> > > 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] Re: MS question : string compression

[Hassan Monfared]

1- try "abb"

On Sat, May 26, 2012 at 12:07 PM, Anchal Gupta wrote:

> yeah i forgot inplace so to do that we simply add count and ch in str
> input array instead of op.
> btw whats wrong with count it give me right answer.
>
> On May 26, 12:08 pm, Hassan Monfared  wrote:
> > u forgot to do "inplace" and you have wrong conversion of count
> >
> > On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta  >wrote:
> >
> >
> >
> >
> >
> >
> >
> > > hey, here is the function that do the compression and store the output
> > > in an array op.
> >
> > > void str_comp(char *str)
> > > {
> > >  int count=0,j=0,i;
> > >  char ch,op[100];
> >
> > >  for(i=0;i > >  {
> > >ch = str[i];
> > >while(str[i] == ch)
> > >  { count++;
> > >i++;
> > >  }
> > > op[j] = count+48;
> > > op[++j] = ch;
> > > j++;
> > > count=0;
> >
> > >   }
> > >   cout<<"input : ";
> > >   for(i=0;i > >cout< >
> > >   cout<<"\n\noutput : ";
> > >   for(i=0;i > >cout< >
> > >  }
> >
> > > Best Regards
> > > Anchal Gupta
> > > USIT(GGSIPU), Delhi
> > > +91-9015897983
> >
> > > --
> > > 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.

[algogeeks] Re: MS question : string compression

[Anchal Gupta]

yeah i forgot inplace so to do that we simply add count and ch in str
input array instead of op.
btw whats wrong with count it give me right answer.

On May 26, 12:08 pm, Hassan Monfared  wrote:
> u forgot to do "inplace" and you have wrong conversion of count
>
> On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta wrote:
>
>
>
>
>
>
>
> > hey, here is the function that do the compression and store the output
> > in an array op.
>
> > void str_comp(char *str)
> > {
> >  int count=0,j=0,i;
> >  char ch,op[100];
>
> >  for(i=0;i >  {
> >    ch = str[i];
> >    while(str[i] == ch)
> >      { count++;
> >        i++;
> >      }
> >     op[j] = count+48;
> >     op[++j] = ch;
> >     j++;
> >     count=0;
>
> >   }
> >   cout<<"input : ";
> >   for(i=0;i >    cout<
> >   cout<<"\n\noutput : ";
> >   for(i=0;i >    cout<
> >  }
>
> > Best Regards
> > Anchal Gupta
> > USIT(GGSIPU), Delhi
> > +91-9015897983
>
> > --
> > 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 question : string compression

[Hassan Monfared]

u forgot to do "inplace" and you have wrong conversion of count

On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta wrote:

> hey, here is the function that do the compression and store the output
> in an array op.
>
>
> void str_comp(char *str)
> {
>  int count=0,j=0,i;
>  char ch,op[100];
>
>  for(i=0;i  {
>ch = str[i];
>while(str[i] == ch)
>  { count++;
>i++;
>  }
> op[j] = count+48;
> op[++j] = ch;
> j++;
> count=0;
>
>   }
>   cout<<"input : ";
>   for(i=0;icout<
>   cout<<"\n\noutput : ";
>   for(i=0;icout<
>  }
>
>
>
> Best Regards
> Anchal Gupta
> USIT(GGSIPU), Delhi
> +91-9015897983
>
>
>
>
> --
> 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] Re: MS question : string compression

[Anchal Gupta]

hey, here is the function that do the compression and store the output
in an array op.


void str_comp(char *str)
{
  int count=0,j=0,i;
  char ch,op[100];

  for(i=0;ihttp://groups.google.com/group/algogeeks?hl=en.