Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
package stringss;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class CompressWord {
String myStr;
Stack myStack;
Queue<Object> myQueue;
CompressWord(String s){
myStr = s;
myStack = new Stack<Object>();
myQueue = new LinkedList<Object>();
}
/**
* Compress the word
*/
public void compressor()
{
int len = myStr.length();
char first = myStr.charAt(0);
int count = 0;
for(int i=0;i<len;i++){
char temp = myStr.charAt(i);
if(first==temp)
count++;
else {
myStack.push(first);
myStack.push(count);
myQueue.add(first);
myQueue.add(count);
first = temp;
count= 0;
}
}//end for
//now print the elements
String output = "";
while(!myStack.empty())
System.out.print(myStack.pop());
System.out.println();
len = myQueue.size();
//______________________________________________________________________________________
// Poll() and just iterate over length
// Object is comapred to object, no other string etc
String dont = "0";
for(int i=0;i<len;i++) {
Object o = myQueue.poll();
if(!o.equals(0))
System.out.print(o);
}
//______________________________________________________________________________________
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CompressWord cWord = new CompressWord("aaabbbabcdddreee");
cWord.compressor();
}
}
Infact there is no need of stack or queue, they are just for storage. The main code is in the compressor function.
Corrected version: We just add a stop letter at the end which is '*' in this case
package stringss;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class CompressWord {
String myStr;
Stack myStack;
Queue<Object> myQueue;
CompressWord(String s){
myStr = s;
myStack = new Stack<Object>();
myQueue = new LinkedList<Object>();
}
/**
* Compress the word
*/
public void compressor()
{
int len = myStr.length();
char first = myStr.charAt(0);
int count = 0;
for(int i=0;i<len;i++){
char temp = myStr.charAt(i);
if(first==temp)
count++;
else {
myStack.push(first);
myStack.push(count);
myQueue.add(first);
myQueue.add(count);
first = temp;
count= 1;
}
}//end for
//now print the elements
/* String output = "";
while(!myStack.empty())
System.out.print(myStack.pop());
System.out.println();*/
len = myQueue.size();
//______________________________________________________________________________________
// Poll() and just iterate over length
// Object is comapred to object, no other string etc
String dont = "0";
for(int i=0;i<len;i++) {
Object o = myQueue.poll();
if(!o.equals(1))
System.out.print(o);
}
//______________________________________________________________________________________
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CompressWord cWord = new CompressWord("AAAAAAAAAAAAAAAAABBBCCDEFFEEEEER"+"*");
cWord.compressor();
}
}
The current top-voted solution takes two passes over the string (because of strlen) and supports only single-digit repetitions, so I thought it'd be worth posting a version that addresses these issues:
void itoa(int n, char **s)
{
char buf[32];
int l = sprintf(buf, "%d", n); // can be done more efficiently by hand
for (int i = 0; i < l; i++)
*s[i] = buf[i];
*s += l;
}
void rle(char *s)
{
char *d = s;
while (*s) {
char c = *s++;
*d++ = c;
int n;
for (n = 1; *s == c; n++) s++;
if (n > 1) itoa(n, &d);
}
*d = 0;
}
Was gonna post my Java version until I saw how compact your code is. Although the terse coding style might make it slightly harder to read, I think it's valuable when one has to write the solution on the whiteboard. Plus the interviewer will be so familiar with the solution that he should get it just by glancing at it.
This one handles multiple digit repetitions also.
void compress(char* str)
{
int i,count,j,top=-1,rev;
for(i=0;str[i];)
{
j=i+1;
count=1;
while(str[j] && str[i]==str[j])
{
j++;count++;
}
str[++top]=str[i];
if(count>1 && count<10)
str[++top]=count+48;
else if(count>=10)
{
rev=0;
while(count)
{
rev=rev*10+count%10;
count/=10;
}
while(rev)
{
str[++top]=rev%10 + 48;
rev/=10;
}
}
i=j;
}
str[++top]='\0';
printf("%s",str);
}
Output: ideone.com/c37hE
public class Compress {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(compress("ABCDEFFGHHHHKLLLLLLLLMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMZ".toCharArray()));
System.out.println(compress("ABCDEFGHHNK".toCharArray()));
}
public static char[] compress(char[] str){
if(str==null || str.length<=1)
return str;
int copyIndex =0;
char prevChar = str[0];
int prevCharCount = 1;
//walk through the array
for(int i=1; i < str.length ; i++){
//check with previous char and current char
if(prevChar != str[i]){
//if prevChar count is only 1
if(prevCharCount==1){
str[copyIndex++] = prevChar;
prevChar = str[i];
}else{
str[copyIndex++] = prevChar;
prevChar = str[i];
char[] countInt = new Integer(prevCharCount).toString().toCharArray();
//copy the occurrence to the array
for(int j=0; j < countInt.length ; j++)
str[copyIndex++] = countInt[j];
}
//copy current one to prev char
prevChar = str[i];
prevCharCount = 1;
}else{
prevCharCount++;
}
}
//Check for the last char in the array
if(prevCharCount==1){
str[copyIndex++] = prevChar;
}else{
str[copyIndex++] = prevChar;
char[] countInt = new Integer(prevCharCount).toString().toCharArray();
//copy the occurrence to the array
for(int j=0; j < countInt.length ; j++)
str[copyIndex++] = countInt[j];
}
//return the compressed char array
return new String(str).substring(0, copyIndex).toCharArray();
}
}
In your code you are creating a new string by
"return new String(str).substring(0, copyIndex).toCharArray(); "
while it is clearly mentioned in question that no new string should be created.
void compress(char a[])
{
char c;
int counter,len1,j;
len=strlen(a);
for(int i=0;i<len;i++)
{
c=a[i];
counter++;
if(c!=a[i+1])
{
j=leftshift(a,len,counter);
a[j++]=c;
a[j]=counter;
i=-1;
len=len-counter;
}
}
int leftshift(char a[],int len,int j)
{
for(int i=j;i<len;i++)
{
a[i-j]=a[i];
}
return i;
}
}
optimized code:
#include<stdio.h>
#include<conio.h>
int main()
{
char a[50]="AAAABBBCXYZEEEEPPPPPKKABC";
int i=0,j=-1;
while(a[i])
{ if(a[i]!=a[i+1])
{ if((i-j)==1)
printf("%c",a[i]);
else
printf("%c%d",a[i],(i-j));
j=i;
}
i++;
}
getchar();
}
i think you have to modify the input array itself.
Correct me if my understanding is wrong.
i think you have to modify the input array itself.
Correct me if my understanding is wrong.
Use a hash table...
The letters will be the keys and their no of occurances will be values. If the value of any key is one, you dont need to display the count. If it is greater than one, display the count in front of the letter...
Time complexity: O(n)
Space complexity: O(n)
Tested C code:
int main()
{
char str[ 250 ] = "AAAABBBCXYZEEEEPPPPPKKABC";
int newIndex = 0, count = 1, prevIndex = -1;
int len = strlen( str );
printf(" Input string is %s \n", str );
for( int curIndex = 0; curIndex <= len; curIndex++ )
{
if( prevIndex == -1 )
{
prevIndex = curIndex;
count = 1;
}
else
{
if( str[ prevIndex ] == str[ curIndex ] )
{
count++;
}
else
{
str[ newIndex ] = str[ prevIndex ];
if( count > 1 )
{
str[ ++newIndex ] = count + 48 ;
count = 1;
}
prevIndex = curIndex;
newIndex++;
}
}
}
str[ newIndex ] = '\0';
printf(" New string is %s \n", str );
return 0;
}
We will use two index variables, one to traverse through the entire original string, the other to write at appropriate place in the string to generate the compressed string.
void compress(char str[]) {
int i = 0, j = 0, count = 0;
do {
if(str[i] == str[j])
count++;
else {
if(count > 1)
str[++j] = count + '0';
str[++j] = str[i];
count = 1;
}
} while(str[i++] != '\0');
str[++j] = '\0';
}
void compress(char *p)
{
char *str = p;
int count = 1;
int index = 0;
int stringlengh = 0;
while(*str != '\0')
{
if(*str == *(++str))
{
count++;
}
else
{
if(1 != count)
{
*(p+index) = *(str-1);
index++;
*(p+index) = (count+48);
index++;
count = 1;
}
else
{
*(p+index) = *(str-1);
index++;
}
}
stringlengh++;
}
memset(p+index, 0,stringlengh - index+1);
}
Fixed:
void compress(char *p)
{
char *str = p;
int count = 1;
int index = 0;
int stringlengh = 0;
while(*str != '\0')
{
if(*str == *(++str))
{
count++;
}
else
{
if(1 != count)
{
int digit = count;
int noOfDig = 0;
while(count > 0)
{
count = count/10;
noOfDig++;
}
*(p+index) = *(str-1);
index++;
sprintf(p+index, "%d", noOfDig );
index= index + noOfDig ;
count = 1;
}
else
{
*(p+index) = *(str-1);
index++;
}
}
stringlengh++;
}
memset(p+index, 0,stringlengh - index+1);
}
void compress(char *p)
{
char *str = p;
int count = 1;
int index = 0;
int stringlengh = 0;
while(*str != '\0')
{
if(*str == *(++str))
{
count++;
}
else
{
if(1 != count)
{
int digit = count;
int noOfDig = 0;
while(count > 0)
{
count = count/10;
noOfDig++;
}
*(p+index) = *(str-1);
index++;
sprintf(p+index, "%d", noOfDig );
index= index + noOfDig ;
count = 1;
}
else
{
*(p+index) = *(str-1);
index++;
}
}
stringlengh++;
}
memset(p+index, 0,stringlengh - index+1);
}
void compress(char* source)
{
int currentPos = 0;
int start = 0;
int next = start + 1 ;
int count = 1;
do
{
if ( source[start] == source[next])
{
++count;
}
else if ( count > 1)
{
// check count is how many digits i.e. 10,100,1000...n
int digitCount = 1;
int tenCount = 10;
while ( ( count / tenCount ) >= 1 )
{
tenCount = tenCount * 10;
++digitCount;
}
// Enter the string count next to the start position.
source[currentPos] = source [next -1];
int newPosition = currentPos + digitCount + 1;
while(digitCount)
{
tenCount = 10;
source[currentPos + digitCount] = 48 + (count%tenCount);
--digitCount;
count = count/tenCount;
}
currentPos = newPosition;
count = 1;
}
else
{
source[currentPos] = source[start];
++currentPos;
}
++next;
++start;
} while (source[next] != '\0');
if ( count > 1)
{
// check count is how many digits i.e. 10,100,1000...n
int digitCount = 1;
int tenCount = 10;
while ( ( count / tenCount ) >= 1 )
{
tenCount = tenCount * 10;
++digitCount;
}
// Enter the string count next to the start position.
source[currentPos] = source [next -1];
int newPosition = currentPos + digitCount + 1;
while(digitCount)
{
tenCount = 10;
int temo = count%tenCount;
source[currentPos + digitCount] = 48 + (count%tenCount);
--digitCount;
count = count/tenCount;
}
currentPos = newPosition;
count = 1;
}
else
{
// write last character as it is.
source[currentPos] = source[start];
++currentPos;
}
source[currentPos] = '\0';
}
#include<stdio.h>
#include<conio.h>
int main()
{
char s[20]={'a','a','a','a','b','b','b','c','a','a','a','b'};
int i,j,count=1,k=0;
for(i=0;i<strlen(s);i++)
printf("%c",s[i]);
printf("\n");
for(j=0;j<strlen(s);j++)
{
if(s[j]==s[j+1]){
count++;
}
else if(count>1){
k=k+count;
printf("%c%d",s[j],count);
j=k-1;
count=1;
} else if(count==1){
k=k+count;
printf("%c%d",s[j],count);
j=k-1;
count=1;
}
}
getch();
}
int compress( char *str )
{
if( NULL == str )
return 0;
if( NULL == str[0] )
return 0;
int k=0, prev=0, Rcount=0;
for(i=1; str[i] != NULL; i++)
{
if( str[i] != str[prev] )
{
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
Rcount = 0;
prev = i;
}
else
Rcount++;
}
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
str[k] = NULL;
return 1;
}
int compress( char *str )
{
if( NULL == str )
return 0;
if( NULL == str[0] )
return 0;
int k=0, prev=0, Rcount=0;
for(i=1; str[i] != NULL; i++)
{
if( str[i] != str[prev] )
{
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
Rcount = 0;
prev = i;
}
else
Rcount++;
}
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
str[k] = NULL;
return 1;
}
int compress( char *str )
{
if( NULL == str )
return 0;
if( NULL == str[0] )
return 0;
int k=0, prev=0, Rcount=0;
for(i=1; str[i] != NULL; i++)
{
if( str[i] != str[prev] )
{
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
Rcount = 0;
prev = i;
}
else
Rcount++;
}
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
str[k] = NULL;
return 1;
}
int compress( char *str )
{
if( NULL == str )
return 0;
if( NULL == str[0] )
return 0;
int k=0, prev=0, Rcount=0;
for(i=1; str[i] != NULL; i++)
{
if( str[i] != str[prev] )
{
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
Rcount = 0;
prev = i;
}
else
Rcount++;
}
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
str[k] = NULL;
return 1;
}
int compress( char *str )
{
if( NULL == str )
return 0;
if( NULL == str[0] )
return 0;
int k=0, prev=0, Rcount=0;
for(i=1; str[i] != NULL; i++)
{
if( str[i] != str[prev] )
{
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
Rcount = 0;
prev = i;
}
else
Rcount++;
}
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
str[k] = NULL;
return 1;
}
int compress( char *str )
{
if( NULL == str )
return 0;
if( NULL == str[0] )
return 0;
int k=0, prev=0, Rcount=0;
for(i=1; str[i] != NULL; i++)
{
if( str[i] != str[prev] )
{
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
Rcount = 0;
prev = i;
}
else
Rcount++;
}
str[k++] = str[prev];
if( Rcount >= 1 ) str[k++] = Rcount + 1;
str[k] = NULL;
return 1;
}
/* Compress String */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
char* compress (char strSource[]){
char* strPtr = strSource;
char* countPtr = strSource;
int strIndex = 0;
int cntIndex = 0;
int count = 0;
char lastChar = strPtr[0];
int tenPowJ;
int cntDigit;
int j;
int firstDigitFound = 0;
while( strPtr[strIndex] != '\0' ){
if(strPtr[strIndex]==lastChar){
count++;
}
else{
countPtr[cntIndex]=lastChar;
cntIndex++;
firstDigitFound = 0;
if(count>1){
for(j=10; j>=0; j--){
tenPowJ = pow(10,j);
if(count/tenPowJ != 0){
firstDigitFound = 1;
}
if(firstDigitFound == 1){
countPtr[cntIndex++] = 48+count/tenPowJ;
count = count%tenPowJ;
}
}
firstDigitFound = 0;
}
count = 1;
}
lastChar = strPtr[strIndex];
strIndex++;
}
strSource[cntIndex+1] = '\0';
return strSource;
}
int main(int argc, char* argv[]){
char strSource[] = "AASARKSESDDDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEDDDDDDDDDDDDDDDDKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEWEEWEKWELEWOEKJWOJNDEKWNMKWMDWOMODWMDWODOWKDOWKDWMDWOMDWODOWKEPASASASBFGRAS";
printf("%s\n", compress(strSource));
}
Recursion
void compressString(char a[], int index, int hcount)
{
char uc = a[index];
int i = index + 1;
int count = 1;
while(a[i] != '\0' && a[i] == uc)
{
i++;
count++;
}
int dc = count;
int digitCount = 1;
while(dc > 9)
{
dc = dc/10;
digitCount++;
}
if(a[i] != '\0')
{
// +1 for the character itself
compressString(a, i, hcount + digitCount + 1);
}
else
{
a[hcount + digitCount + 1] = '\0';
}
a[hcount] = uc;
int k = 0;
for(k = digitCount; k > 0; k-- )
{
a[hcount + k] = count%10 + 48;
count = count/10;
}
}
void compress(char *ptr)
{
char *ptr2 = ptr;
char arr[10];
int ilen = strlen(ptr);
int i = 0 , j = 0 , count = 0;
while(i<ilen)
{
if (ptr[i] != ptr[i+1])
{
ptr2[j] = ptr[i];
j++;
if (count>1)
{
memset(arr,0,10);
itoa(count+1,arr,10);
strcpy(ptr2+j,arr);
j++;
}
count = 0;
}else
{
count ++;
}
i++;
}
ptr[j] = '\0';
}
Do correct me if it is wrong
package stringss;
/**
* Write function compress(char* strSource)
it should do the following .
repeating chars in sequence should be replaced with char & count, in case count is 1 no need to add any integer.
Example - AAAABBBCXYZEEEEPPPPPKKABC
should be A4B3CXYZE4P5K2ABC.
you are supposed to iterate the array only once, and modify the same input parameter,
do not create any new string.
*/
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class CompressWord {
String myStr;
Stack myStack;
Queue<Object> myQueue;
CompressWord(String s){
myStr = s;
myStack = new Stack<Object>();
myQueue = new LinkedList<Object>();
}
/**
* Compress the word
*/
public void compressor()
{
int len = myStr.length();
char first = myStr.charAt(0);
int count = 0;
for(int i=0;i<len;i++){
char temp = myStr.charAt(i);
if(first==temp)
count++;
else {
/* myStack.push(first);
myStack.push(count);*/
myQueue.add(first);
myQueue.add(count);
System.out.print(first);
if(count!=1)
System.out.print(count);
first = temp;
count= 1;
}
}//end for
//add the last character
myQueue.add(first);
myQueue.add(count);
System.out.print(first);
if(count!=1)
System.out.print(count);
//now print the elements
/* String output = "";
while(!myStack.empty())
System.out.print(myStack.pop());
System.out.println();*/
/* len = myQueue.size();
//______________________________________________________________________________________
// Poll() and just iterate over length
// Object is comapred to object, no other string etc
for(int i=0;i<len;i++) {
Object o = myQueue.poll();
if(!o.equals(1))
System.out.print(o);
} */
//______________________________________________________________________________________
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CompressWord cWord = new CompressWord("AAAAAAAAAAAAAAAAABBBCCDEFFEEEEERRRR");
cWord.compressor();
}
}
#include<stdio.h>
#include<stdlib.h>
int main()
{
char a[10],ch;
int i=0,j=0,k=1,count=1;
printf("enter the string\n");
while((ch=getchar())!='\n')
a[i++]=ch;
a[i]='\0';
while(k<i)
{
while(a[k]==a[j])
{
count++;
k++;
}
if(count>1)
{
a[++j]=count+'0';
count=1;
}
a[++j]=a[k];
k++;
}
a[++j]='\0';
printf("%s",a);
return;
}
public static void Compress(String input) {
char[] a = input.toCharArray();
boolean sequence = false;
System.out.println(a);
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int count = 0;
for (int i = 0; i < a.length - 1; i++) {
if (a[i] == a[i + 1]) {
sequence = true;
if (map.containsKey(a[i])) {
map.put(a[i], map.get(a[i]) + 1);
} else {
map.put(a[i], 1);
}
if(i+1==a.length-1){
count = map.get(a[i])+1;
System.out.print(a[i]+""+count);
}
}else
{
count=0;
if(sequence){
count = map.get(a[i])+1;
System.out.print(a[i]+""+count);
}else{
System.out.print(a[i]);
}
if(i+1==a.length-1){
System.out.print(a[i+1]);
}
sequence = false;
}
}
}
public static String charCount(String str) {
int count = 1;
StringBuffer strBuf = new StringBuffer();
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1))
count++;
else {
strBuf.append(str.charAt(i - 1));
if (count != 1)
strBuf.append(count);
count = 1;
}
}
strBuf.append(str.charAt(str.length() - 1));
if (count != 1)
strBuf.append(count);
return strBuf.toString();
}
str1="AAAABBBKKKZZZ"
count=1
i=0
j=1
while(True):
if str1[i]==str1[j]:
count=count+1
else :
if count>1:
str1=str1[:str1.index(str1[i])]+str1[i]+str(count)+str1[i+1:]
i=i-count -1
count=1
i=i+1;
j=i+1;
if (j)==len(str1):
str1=str1[:str1.index(str1[i])]+str1[i]+str(count)+str1[i+1:]
break
print str1
My Java version (even though it feels weird doing this in Java). Nothing fancy, just that I use Math.log10 instead of sprintf to figure out the count, and that rather than checking forward I check backwards for when to print.
void compress(char[] s) {
int i = 0;
int count = 0;
char prev = s[0];
for(char ch : s) {
if(ch == prev) {
count++;
} else {
s[i++] = prev;
if(count > 1) {
int numDigits = 1 + (int)Math.log10(count);
for(int j=numDigits-1; j>=0; j--) {
s[i+j] = (char)('0' + (count % 10));
count /= 10;
}
i+=numDigits;
}
count = 1;
}
prev = ch;
}
s[i] = '\n';
}
void Compress(char* string)
{
int index=0;
int i=0;
while (string[index]!='\0')
{
int count=1;
while (string[index] == string[index+1])
{
count++;
index++;
}
if(count >1)
{
//If not uniuqe => set the previous element.
string[i]=string[index-1];
i++;
char buffer[10];
char* numstring = itoa(count,buffer,10);
int stringlen= strlen(numstring);
for(int j=0;j<stringlen;j++)
{
string[i]=numstring[j];
i++;
}
}
else
{
string[i]=string[index];
i++;
}
//Index has to be incremented before leaving the loop.
index++;
}
string[i]='\0';
}
Injoy !!!!
package Algorithms;
public class CompressString {
public static void main(String[] args) {
String str = "AAABBBCCCDDDEEEFF";
int size = findSize(str);
if(size >= str.length()){
System.out.println(str);
}else{
String compressedStr = compressString(str);
System.out.println(compressedStr);
}
}
public static String compressString(String str){
StringBuffer strBuf = new StringBuffer();
int count = 1;
char last = str.charAt(0);
for(int i = 1 ; i < str.length() ; i++){
if(last == str.charAt(i)){
count++;
}else{
strBuf.append(last);
strBuf.append(count);
count = 1;
last = str.charAt(i);
}
}
strBuf.append(last);
strBuf.append(count);
return strBuf.toString();
}
public static int findSize(String str){
int size = 0;
int count = 1;
char last = str.charAt(0);
for(int i = 1 ; i < str.length() ; i++){
if(last == str.charAt(i)){
count ++;
}else{
size += 1 + String.valueOf(count).length();
last = str.charAt(i);
}
}
size += 1+ String.valueOf(count).length();
return size;
}
}
Implementing such code is kind of tricky. It's very likely to make mistake.
public class StringCompress {
public static void strCompress(char[] a) {
if (a == null) return;
char prev = a[0];
int last = 0;
int diff = 0;
int comp = 0;
int i = 0;
for (i = 0; i < a.length; i++) {
if (prev != a[i]) {
diff = i - last;
last = i;
a[comp++] = prev;
if (diff > 1) {
a[comp++] = (char)(diff + '0');
}
}
prev = a[i];
}
a[comp++] = prev;
diff = i - last;
if (diff > 1) {
a[comp++] = (char)(diff + '0');
}
for (i = comp; i < a.length; i++) {
a[i] = ' ';
}
System.out.println(a);
}
public static void main(String[] args) {
char[] a = {'A','A','A','A','B','B','B','C','X','Y','Z','E','E','E','E','P','P','P','P','P','K','K','A','B','C'};
strCompress(a);
a = new char[] {'A','A'};
strCompress(a);
a = new char[] {'A','B'};
strCompress(a);
a = new char[] {'A'};
strCompress(a);
}
}
import java.util.HashMap;
public class hello {
/**
* @param args
*/
public static void main(String[] args) {
// input : AAAABBBCXYZEEEEPPPPPKKABC
// output : A4B3CXYZE4P5K2ABC
try{
String str="AAAABBBCXYZEEEEPPPPPKKABC ";
int count=1;
char a[]=str.toCharArray();
int i=0;
while(i<str.length())
{
if(a[i]==a[i+1])
count++;
else
{
System.out.print(a[i]);
if(count!=1)
System.out.print(count);
count=1;
}
i++;
}
}
catch(Exception e) {}
}
}
void compress(char* str)
{
char ch = 0;
int count = 0;
int len = 0;
for(int i = 0; str[i] != '\0'; ++i)
{
if(str[i + 1] == '\0' || str[i] != str[i + 1])
{
len += sprintf(str[i - count], "%c", ch);
if(count > 0)
{
len += sprintf(str[i - count + 1], "%d", count + 1);
}
}
else
{
++count;
}
}
str[len + 1] = '\0';
}
package com.xyz.datastructure;
public class CompressString {
public static void main(String[] args) {
String str="AAAABBBCCD";
compress(str);
}
private static void compress(String str) {
int count=0;
char[] chr = str.toCharArray();
int i,j;
for(i=0;i<chr.length;)
{
if(i == 0)
str = "";
j=i+1;
count=1;
if(j != chr.length) {
while(chr[i]==chr[j])
{
j++;
count++;
}
}
str += String.valueOf(chr[i]) + "" + count;
//System.out.println(result);
i = j;
}
System.out.println("Result:"+str);
}
}
public class Compressor {
static StringBuffer compressed = new StringBuffer();
public static void main(String[] args) {
String original = "AAAABBBCXYZEEEEPPPPPKKABC";
charCount(original);
System.out.println(compressed);
}
public static void addString(char c, int cnt){
if(cnt == 1)
compressed.append(Character.toString(c));
else
compressed.append(Character.toString(c) + Integer.toString(cnt));
}
public static void charCount(String str){
str += " ";
Character temp = null;
int cnt = 0;
for(int i=0; i<str.length(); i++) {
if(temp == null) {
temp = str.charAt(i);
cnt = 1;
} else if(!temp.equals(str.charAt(i)) || i==str.length()-1){
addString(str.charAt(i-1), cnt);
temp = str.charAt(i);
cnt = 1;
} else {
cnt++;
}
}
}
}
I did not browse all but most of the solutions are creating a separate string. Please find below in place solution
public class compressString {
private static String compressedString(String string) {
// TODO Auto-generated method stub
if(string == null){
return null;
}
char strCharArr[] = string.toCharArray();
int j=0;
int ptr=0;
int count=0;
for(int i=0;i<string.length();i++){
if(string.charAt(j)==string.charAt(i)) {
count++;
} else {
if(count > 1) {
strCharArr[ptr++] = Integer.toString(count).charAt(0);
}
count =1;
j=i;
}
if(count ==1) {
strCharArr[ptr++] = strCharArr[i];
}
}
while(ptr < strCharArr.length)
strCharArr[ptr++]='\0';
return String.valueOf(strCharArr);
}
}
I did not browse all but most of the solutions are creating a separate string. Please find below in place solution
public class compressString {
private static String compressedString(String string) {
// TODO Auto-generated method stub
if(string == null){
return null;
}
char strCharArr[] = string.toCharArray();
int j=0;
int ptr=0;
int count=0;
for(int i=0;i<string.length();i++){
if(string.charAt(j)==string.charAt(i)) {
count++;
} else {
if(count > 1) {
strCharArr[ptr++] = Integer.toString(count).charAt(0);
}
count =1;
j=i;
}
if(count ==1) {
strCharArr[ptr++] = strCharArr[i];
}
}
while(ptr < strCharArr.length)
strCharArr[ptr++]='\0';
return String.valueOf(strCharArr);
}
}
- Ganesh M January 31, 2012