#include "stdafx.h"
#include <iostream>
using namespace std;
const int len = 20;
const int maxCount = 127;
int rle(char* pStr, int length, char* pNew) {
if (!pStr) return -1;
if (length <3) return -1;
int i = 0;
int k = 0;
char p1 = pStr[i++];
char p2 = pStr[i++];
char p3 = pStr[i++];
int pos=0;
int cCount = 0;
bool verbatim = false;
while ((p3) && (i<length)) {
if (p1==p2) {
if (p2==p3) {
if (i == k+3) //no vRun
verbatim = false;//no vRun befor this cRun
if (verbatim)
{
int vEnd = (i-3)-k;;
pNew[pos++] = vEnd;
for (int t=k;t<vEnd;t++) {
pNew[pos++]=pStr[t];
}
}
cCount++;
p1 = p2;
p2 = p3;/*not required*/
p3 = pStr[i++];
continue;
}
else { //run end or no run at all
if (cCount >0) { //a run
pNew[pos++] = -cCount; ///
pNew[pos++] = p2;
p1 = p3;
k = i-1; //p3's position
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
}
else { /*aab */
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
}
else { //no run
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
//possible run or no run here
if (cCount>0) {
pNew[pos++] = -cCount;
pNew[pos++] = p2;
} else {
if (k<length) {
pNew[pos++] = length-k-1;
for (int t=k;t<length;t++) {
pNew[pos++]=pStr[t];
}
}
}
pNew[pos]='\0';
return 1;
}
void rleDecode(char *pEnc, char *pDec, char *pOrig)
{
int i = 0;
int pos =0;
int count ;
char character ;
do {
count = pEnc[i++];
if (count <0) {
count = 2-count;
character = pEnc[i++];
for (int j=0;j<count;j++)
pDec[pos++] = character;
}
else {
//pNew[pos++]=character;
for (int j=0;j<count;j++) {
pDec[pos++]=pEnc[i++];
}
}
}while (pEnc[i]);
pDec[pos]='\0';
for(int i=0;i<len;i++)
if (pOrig[i]!=pDec[i]) cout <<"JERK, do it again!! (:" <<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *pStr = (char *)malloc(sizeof(char)*len);
pStr = "abccdddeeeeeeeeijkk"; //TRY more examples
char *pNew = (char *)malloc(sizeof(char)*len);
char *pDec = (char *)malloc(sizeof(char)*len);
//rleSimple(pStr,pNew);
rle(pStr,len,pNew);
rleDecode(pNew, pDec, pStr);
return 0;
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 9:04 AM, Ashish Goel <ashg...@gmail.com> wrote:
>
>
> 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.
