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

26 Answers

21

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
4

#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
2

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

Anonymous on 15-Mar-2012
4

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

This solution covers all cases..

http://justprogrammng.blogspot.in/2012/06/amazon-interview-string-compression-c.html

rohan on 05-Jun-2012
0

Here is a recursive code which considers all cases...

http://justprogrammng.blogspot.com/2012/06/amazon-interview-string-compression-c.html

rohan on 09-Jun-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
1

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
1

#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

Add Answers or Comments

To comment on this, Sign In or Sign Up.