The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position in
the string i am processing now and do the compress(either verbatim or real
compress) when 3 same chars are found
eg
abcfdgffffffg: pos is 0 and at index 8 we get to know that there is a run,
so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and update
pos to index 6, and count to 1. Since now run flag is on, we continue till
we find a triplet mismatch(f==f but f!=g) which happens at g (index
12)implying an end to a run, therefore now count is 4, we would write 4f
implying 2+4 times of next char should be expanded. now again pos will be
set to 12, count to 0 and three same char check should re-begin. This will
for sure have 2 while loops and a bit comex, and i donot think this is what
the interviewer should expect one to code. Kindly note that if run is more
than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta <navin.nit...@gmail.com> wrote:
> If abcdef is changed to a1b1c1d1e1f1,
> then we need to allocate memory dynamically.
> Because length is increased,I think this has no practical
> implementation.As "abcdef " serves the same purpose.
>
>
> On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
>>
>> @ashish:-algo given in link wiil fail for "abcdef"
>>
>> @navin:- output of "abcdef" should be "1a1b1c1d1e1f"
>>
>> On Sun, May 27, 2012 at 3:24 PM, Ashish Goel <ashg...@gmail.com> wrote:
>>
>>> 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 <navin.nit...@gmail.com>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: "aaabbbbbcdef"
>>>>> 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<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+unsubscribe@**
>>>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>.
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <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+unsubscribe@**
>>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>.
>>> For more options, visit this group at http://groups.google.com/**
>>> group/algogeeks?hl=en <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/-/gM8fEXZNskkJ.
>
> 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.
