Amazon Interview Question: Given a string "aaabbbcc", co... | Glassdoor.co.in

Interview Question

Software Development Engineer Interview Hyderabad

Given a string "aaabbbcc", compress it, = "a3b3c2" . Given

  that output string's length is always smaller than input string, you have do it inplace. No extra space
Answer

Interview Answer

30 Answers

25

public static String cstr(String a){
    if(a.length()<2){return a;}
    if(a.length()==2){if(a.charAt(0)==a.charAt(1)){return a.charAt(0)+"2";}else{return a;}}
    for(int i=0;i

Max on 05-Mar-2012
5

#include
#include
#include
#define STR_SIZE 26
int main()
{
   /* Current char sequence tracker */
   char *c = NULL;
   char *b = NULL;
   char *str = (char*)malloc(STR_SIZE * sizeof(char));

   if(NULL == str)
      return -1;
   memcpy(str, "aaaabbbcceeeeefffffff", 26);
   b = c = str;
   printf("Input: %s\n", b);
   while(*str)
   {
      if(*(str+1) != *str) // Repeat sequence ends
      {
         // Add 48 so the count gets printed as a char
         *(c+1) = ((str-c+1)+48);
         // Updated count, copy rest of the string starting after the count position
         memcpy(c+2, str+1, strlen(str));
         // Update c to point to the new char repeat sequence
         c = c+2;
      }
      str++;
   }
  /* b was initialized to point to str up top, proving it was done in place */
   printf("Output:%s\n", b);
   free(b);
   b = NULL;
   return 0;
}

Rohan on 11-Mar-2012
5

String test="aavvvqwqaa";
        int count=0,start=0,end=0;
        int length=test.length();
        for(int i=0;i

Anonymous on 15-Mar-2012
5

Rohan: What if I give you the string "aaaaaaaaaa"? Your solution will print "a:", not "a10".

David on 19-Mar-2012
1

in java, if you give me a String str="aaabbbcc";
you can't modify the str as all, then how can you do it in place?

I assume I can go through the str, and store the new string such as "a3b3c2"

anyone can explain to me?

bsd on 24-Mar-2012
1

java inplace

   public void compress(char[] str) {
      if (str != null && str.length > 1) {
         for (int last = 0, curr = 1, count = 1, tail = 0; curr 1) {
               str[tail++] = str[last];
               str[tail++] = (char) count;
               count = 1;
            }
            last = curr;
            curr++;
         }
      }
   }

Naresh on 29-Mar-2012
1

Need to delimit the array

    public void compress(char[] str) {
        if (str != null && str.length > 1) {
            int tail = 0;
            for (int last = 0, curr = 1, count = 1; curr 1) {
                    str[tail++] = str[last];
                    str[tail++] = (char) count;
                    count = 1;
                }
                last = curr;
                curr++;
            }
            str[tail] = '\0';
        }
    }

Naresh on 29-Mar-2012
0

small correction -
   public void compress(char[] str) {
      if (str != null && str.length > 1) {
          int tail = 0;
          for (int last = 0, curr = 1, count = 1; curr 1) {
                str[tail++] = str[last];
                str[tail++] = (char) (count + '0');
                count = 1;
             }
             last = curr;
             curr++;
          }
          str[tail] = '\0';
      }
   }

N on 29-Mar-2012
0

Try this.. it generates the desired output in Java
/**
 *
 * @author Sourabh Mishra
 * Class which handles compression of a string replacing the occurrences of characters
 * with the character followed by its count in the input string
 *
 */
public class StringCompressor {

    /**
     * Method takes input as a string and replacing the occurrences of characters
     * with the character followed by its count in the input string
     * @param data String
     * @return
     */
    public String compressString(String data){

        StringBuilder outBuilder = new StringBuilder();
        char prevChar = data.charAt(0);
        int counter = 0;
        char currChar;
        int length = data.length();
        for(int i=0; i< length; i++){
            currChar = data.charAt(i);
            if(currChar == prevChar){
                counter++;
                // For the last unique characters
                if(i == length-1){
                    outBuilder.append(currChar);
                    outBuilder.append(counter);
                }
                continue;
            } else {
                outBuilder.append(prevChar);
                outBuilder.append(counter);
                prevChar = currChar;
                counter=1;
            }
        }

        return outBuilder.toString();
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        StringCompressor sc = new StringCompressor();
        System.out.println(sc.compressString("aaabbbcc"));

    }

}

Sourabh Mishra on 24-Nov-2012
0

An additional check and write inside in the else class is required to print the final unique character for inputs like "aaabbbh"

public class Stringcompress {

    /**
     * Method takes input as a string and replacing the occurrences of
     * characters with the character followed by its count in the input string
     */
    public String compressString(String data) {

        StringBuilder outBuilder = new StringBuilder();
        char prevChar = data.charAt(0);
        int counter = 0;
        char currChar;
        int length = data.length();
        for (int i = 0; i < length; i++) {
            currChar = data.charAt(i);
            System.out.println("Curr character is :" + currChar);
            System.out.println("Prev character is :" + prevChar);
            if (currChar == prevChar) {
                counter++;
                // For the last unique characters
                if (i == length - 1) {
                    outBuilder.append(currChar);
                    outBuilder.append(counter);
                }
                continue;
            } else {
                System.out.println("Prev character in else is :" + prevChar);
                outBuilder.append(prevChar);
                outBuilder.append(counter);
                prevChar = currChar;
                counter = 1;
                if(i==length-1)
                {
                    outBuilder.append(currChar);
                    outBuilder.append(counter);

                }
            }
        }

        return outBuilder.toString();
    }

    public static void main(String[] args) {
        Stringcompress sc = new Stringcompress();
        System.out.println(sc.compressString("aaaaaaadfgdfu"));

    }

}

Sourabh Code correction on 08-Jan-2014
2

public class Example1
{
    static String S1="aaabbbccc";
    static String comstring="";
public static void main(String[] args)
{
    System.out.println(" Actual string is "+S1);
    S1=S1+"#";
    String oldString=S1;
     int count=1;
    for(int i=0;i

I think this one also work for it with simple char comparision on 12-May-2015
1

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
class amzone
{
public static void main(String [] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line=br.readLine();
int n=line.length();
int count=1;
for(int i=0;i

vikas singh on 15-Jul-2015
0

Using Ruby methods,

ans = ""
s.split("").group_by{|x| x}.each{|k,v| ans += "#{k}#{v.count}"}
puts ans

But this code snippet will produce "a4b3c2" for the input string "aaabbbcca"

Selvag on 10-Sep-2015
0

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class StringCharCount {
    public static void main(String args[])
    {
        String inputString="aaabbbccdddddddddddd";

        List charUniqueList=new ArrayList();
        Map charCountMap=new HashMap();
        for(int i=0;i

Here you go.. on 23-Jul-2016
0

What about the input "abc"? I assume that should compress to "a1b1c1" which is NOT shorter than the input, so you cannot compress in place.

anonymous on 06-Nov-2016
1

string CombineWithNoExtraSpace(string S)
{
    int n=S.size(),count=1,i=0;
    if(i==n) return "\0";
    while(i+1<=n && S[i]==S[i+1] )
    {
        count++;
        i++;
    }
    S = S[i] + to_string(count) + combine(S.substr(i+1,n-count));
    return S;
}

Dev on 04-Dec-2016
0

def compress(in_string):
    final_string = ""
    init_char = ""
    ch_val = 1
    for (i,ch) in enumerate(in_string):
        if ch is not init_char:
            init_char = ch
            if ch_val > 1:
                final_string += str(ch_val)
            ch_val = 1
            final_string += ch
            continue
        ch_val += 1
        try:
            out = in_string[i+1]
        except IndexError:
            final_string += str(ch_val)
    return final_string

print compress("aaaaab")

Priyal on 02-Jan-2017
0

public String compress(String in)
    {
        if (in.length() 1 ? right-left : "");
            right++; left = right-1;
        }
        return out.toString();
    }

Java method to compress string on 17-Jul-2017
0

public String compress(String in)
    {
        if (in.length() 1 ? right-left : "");
            right++; left = right-1;
        }
        return out.toString();
    }

Anonymous on 17-Jul-2017
0

Answer:

public class StringCompression {

    public static void main(String[] args) {
        String inputString = "abcabcaaaaaaaaaaaaabc";//"aabcccccaaa";
        System.out.println(getCompressedString(inputString));
    }

    private static String getCompressedString(String originalString) {
        StringBuilder compressedStr = new StringBuilder();
        if(originalString != null && originalString.length() = originalString.length()){
            return originalString;
        }
        else{
            return compressedStr.toString();
        }
    }

}

Janhavi2989 on 04-Sep-2017
0

public static String returnCount (String values) {
        HashMap getHash = new HashMap();
        StringBuilder sb = new StringBuilder();
// char[] charsInString = values.toCharArray();
        for(char characters : values.toCharArray()){
            if(!(getHash.containsKey(characters))){
                getHash.put(characters,1);
            }
            else
                getHash.put(characters,getHash.get(characters) + 1);
        }
// for()
        for(char keys : getHash.keySet()){
            sb.append(keys);
            sb.append(getHash.get(keys));
        }

        System.out.println(getHash);

return sb.toString();
    }

In Java on 12-Jan-2018
2

#include
#include
int main(void)
{
    char ch;
    char accept[100];
    char output_string[100];
    int count=0,i,j,pos=0;
    scanf("%s",&accept);
    printf("%s",accept);
    for(i=0;i

CoDeKiller on 04-Sep-2018
0

dfdsf

Anonymous on 10-Sep-2018
0

#include
int main()
{
  char c[30];
  int i,count=0;
  printf("Enter a String : ");
  scanf("%s",c);
  for(i=0;s[i]!='\0';i++)
  {
    count=1;
    while(s[i]==s[i+1])
    {
       i++;
       count++;

   }
   printf("%s,%d",s[i],count);
 }
 return 0;
}

sai on 01-Feb-2019
2

x="aaabbbcc"
for i in range(len(x)):
    if i==x.index(x[i])+x.count(x[i])-1:
        print(x[i],end="")
        print(x.count(x[i]),end="")

vamsi on 21-Jul-2019
0

public class CompressUtil {

    public static void main(String[] args) {

        char[] str = "aaabbbccs".toCharArray();

        StringBuilder strcompress = compressString(str);
        System.out.println(strcompress.toString());
    }

    private static StringBuilder compressString(char[] str)
    {
        StringBuilder strcompress = new StringBuilder();
        int counter = 1;
        if (str.length == 1)
            strcompress.append(str[0]);

        for (int i = 0; i < str.length - 1; i++) {

            if (str[i] == str[i + 1]) {
                counter++;

                //check if it's the last position
                if (i + 1 == str.length - 1) {
                    strcompress.append(str[i] + "" + counter);
                }
            } else {
                if (counter == 1) {
                    strcompress.append(str[i]);
                } else {
                    strcompress.append(str[i] + "" + counter);
                }
                counter = 1;
                //check if it's the last position
                if (i + 1 == str.length - 1) {
                    strcompress.append(str[i + 1]);
                }
            }
        }
        return strcompress;
    }

}

Garnicajr on 20-Oct-2019
0

public class Test {
// Initialize the count to default
    static int count=1;

    static void strCompress(String str)
    {
        for(int i=0;i

Sri Janya on 11-Feb-2020
0

public class Test {
// Initialize the count to default
    static int count=1;
    static void strCompress(String str)
    {
        for(int i=0;i

Sri Janya on 11-Feb-2020

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.