Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652
On Fri, Jun 8, 2012 at 12:54 PM, Ashish Goel <[email protected]> wrote: > #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++; > if (cCount == maxCount) { pNew[pos++] = -cCount; /// pNew[pos++] = p3; p1 = pStr[i++]; if (!p1) break; k = 0; p2 = pStr[i++]; if (!p2) break; p3 = pStr[i++]; cCount = 0; continue; } else { > /*p1 = p2; > p2 = p3; //not required*/ > p3 = pStr[i++]; > } > } > 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 <[email protected]> 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 <[email protected]>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 <[email protected]> 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 >>>>> <[email protected]>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 [email protected]. >>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@* >>>>>> *googlegroups.com <algogeeks%[email protected]>. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>>>> googlegroups.com <algogeeks%[email protected]>. >>>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
