Amazon Interview Question
SDE1sCountry: United States
When I wrote the same thing in Python, it won't append the last characters because of the end case on your if statement.
At the end of the iteration, I added the last character to the final string
def encodeString(s):
char = s[0]
count = 1
final = ""
for c in s:
if char == c:
count += 1
else:
final += char
final += str(count)
count = 1
char = c
final += char
final += str(count)
return final
print encodeString("aaabbcccdd")
Is it for contiguous characters only? For eg : What should happen for strings like aabbaaccaa? Should it be a2b2a2c2a2 OR a6b2c2?
Did the interviewer allow to use extra space to store the result?
If input string array should be used for output,
abc would expand to a1b1c1 so that the input string array would be not enough.
string getStringFromNumber(int i)
{
ostringstream ss;
ss << i;
return ss.str();
}
void printFormattedString1(string iStr)
{
string finalStr = "";
//int counter = 0;
int characters[256] = {0};
int totalChars = iStr.length();
for(int i = 0; i < totalChars; ++i)
{
counter++;
characters[int(iStr[i])]++;
}
for(int j = 0; j < 256; ++j)
{
counter++;
if(characters[j])
{
finalStr += char(j);
finalStr += getStringFromNumber(characters[j]);
}
}
//cout<<endl<<counter;
cout<< endl << finalStr;
}
Solution to the former one :
void printFormattedString(string iStr)
{
string finalStr = "";
char currChar = iStr[0];
int ctr = 0;
//int counter = 0;
int totalChars = iStr.length();
for(int i = 0; i <= totalChars; ++i)
{
char newChar = ' ';
//counter++;
if( i < totalChars )
{
newChar = iStr[i];
}
if(newChar == currChar)
{
ctr++;
}
else
{
finalStr += currChar;
finalStr += getStringFromNumber(ctr);
ctr = 1;
currChar = newChar;
}
}
//cout<<endl<<counter;
cout<< endl << finalStr;
}
Java Code:
public class StringCompApp {
public static String StringComp(String str) {
int tail=0;
int count=1;
String compStr = "";
for (int j=1; j<str.length(); j++) {
if(str.charAt(j) == str.charAt(tail)) {
tail++;
count++;
}
else {
compStr = compStr + str.charAt(tail) + count;
System.out.println("compStr: " + compStr);
tail++;
count = 1;
}
}
//for the last character count
compStr = compStr + str.charAt(tail) + count;
return compStr;
}
public static void main(String[] args) {
String str1 = "aaaabbcccdefgg";
String compstr1;
compstr1 = StringComp(str1);
System.out.println("Compressed Str: " + compstr1);
}
}
Do a single scan of the string and collect and print the data as below. Space complexity is constant, time is linear:
#include <stdio.h>
void enc(const char* buf, int size)
{
if (NULL == buf)
return;
int cnt = 0;
char pc = 0;
for (int i = 0; i < size; i++)
{
if (pc == buf[i])
{
cnt++;
}
else
{
// process the previous char
if(pc)
printf("%c%d", pc, cnt);
pc = buf[i];
cnt = 1;
}
}
// process the final char(s)
if (cnt)
printf("%c%d", pc, cnt);
}
int main(int argc, char* argv[])
{
char buf[] = "aaaabbccdd";
int size = strlen(buf);
enc(buf, size);
return 0;
}
public static void encodeString(String input)
{
char[] inputArray = input.toCharArray();
int charCounter = 1;
int arrayIndex = 0;
char tmpChar = inputArray[0];
String encodeString="";
System.out.println("Method 1:");
for (int i = 1; i < inputArray.length; i++) {
if(tmpChar == inputArray[i])
charCounter++;
else
{
// 1. You can just go on printing new string as and when you find it. In this case in the end you wont have it stored anywhere.
// 2. We copy encoded string to new string. So space increases
// 3. You can modify your current char array with encoded string. When encoding is over you can insert special char to mark the end.
// The catch here is there should be no such char which occurs only once since then you will exceed char array limit. Ex abc -> a1b1c1 which goes beyond limit of char array.
System.out.print(tmpChar+Integer.toString(charCounter));
encodeString=encodeString+tmpChar+ Integer.toString(charCounter);
inputArray[arrayIndex]=tmpChar;
arrayIndex++;
if(((String)Integer.toString(charCounter)).toCharArray().length>1)
{
char[] charCounterArray = ((String)Integer.toString(charCounter)).toCharArray();
for (int j = 0; j < charCounterArray.length; j++) {
inputArray[arrayIndex]=charCounterArray[j];
arrayIndex++;
}
}
else
{
inputArray[arrayIndex]=((String)Integer.toString(charCounter)).charAt(0);
arrayIndex++;
}
tmpChar = inputArray[i];
charCounter =1;
}
}
// collecting final char
System.out.print(tmpChar+Integer.toString(charCounter));
System.out.println();
encodeString = encodeString+tmpChar+charCounter;
System.out.println("Method 2: "+encodeString);
inputArray[arrayIndex]=tmpChar;
arrayIndex++;
if(((String)Integer.toString(charCounter)).toCharArray().length>1)
{
char[] charCounterArray = ((String)Integer.toString(charCounter)).toCharArray();
for (int j = 0; j < charCounterArray.length; j++) {
inputArray[arrayIndex]=charCounterArray[j];
arrayIndex++;
}
}
else
{
inputArray[arrayIndex]=((String)Integer.toString(charCounter)).charAt(0);
arrayIndex++;
}
// Marking end of collection in original array
inputArray[arrayIndex]='*';
System.out.println("Method 3: ");
for (int i = 0; i < inputArray.length; i++) {
if(inputArray[i]=='*')
break;
System.out.print(inputArray[i]);
}
System.out.println();
}
import java.util.StringBuilder;
public class Encoding {
protected static StringBuilder encodedStr = new StringBuilder();
private static void encodeStr(char[] c, int start) {
int count = 1;
if (start > c.size -1) {
return;
}
encodedStr.add(c[start]);
while (c[count + start - 1] == c[count + start]) {
count++;
}
encodedStr.add(count);
encodeStr(c, start+count);
}
public static String encodeStr(String str) {
encodeStr(str.toCharArray(), 0);
return encodedStr.toString();
}
}
public static void main(String args[]){
String str = "aaaabbbbcccddddefgh";
StringBuilder sbr = new StringBuilder("");
int count=0;
for(int i=0;i<str.length();){
count=1;
sbr.append(str.charAt(i));
while(i<str.length() && (i+1)<str.length() && str.charAt(i)==str.charAt(i+1)){
count++;
i++;
}
sbr.append(count);
i++;
}
System.out.println(sbr);
}
import java.util.Scanner;
public class Encript {
public static void main(String [] arg){
int count=1;
String s1="",s2="";
Scanner in=new Scanner(System.in);
s1=in.nextLine();
System.out.print("The encripted stirng is....");
for(int i=0;i<s1.length()-1;i++)
{ if(s1.charAt(i)==s1.charAt(i+1))
count++;
else
{
System.out.print(s1.charAt(i));
System.out.print(count);
count=1;
}
}
System.out.print(s1.charAt(s1.length()-1));
System.out.print(count);
}
}
<pre class="language-java">
public static void Encrypt(){
String in="aaaabbbcccccccdddgggggg";
StringBuilder sb=new StringBuilder("");
int count=0;
char c=in.charAt(0);
for (int i = 0; i < in.length(); i++) {
if(c==in.charAt(i)) count++;
else {
sb=sb.append(c);
sb.append(count);
c=in.charAt(i);
count=1;
}
}
sb.append(c);
sb.append(count);
System.out.println(sb.toString());
}
</pre>
public static void Encrypt(){
String in="aaaabbbcccccccdddgggggg";
StringBuilder sb=new StringBuilder("");
int count=0;
char c=in.charAt(0);
for (int i = 0; i < in.length(); i++) {
if(c==in.charAt(i)) count++;
else {
sb=sb.append(c);
sb.append(count);
c=in.charAt(i);
count=1;
}
}
sb.append(c);
sb.append(count);
System.out.println(sb.toString());
}
This one could use a little more optimization. encode function will not reallocate string buffer. I used strdup in main to avoid access violations.
#include <stdio.h>
#include <string.h>
char* encode(char* arr);
int main (int argc, char * argv[]){
if (argc > 1){
printf ("\'%s\' > %s\n",argv[1], encode(strdup(argv[1])));
}
}
char* encode(char* arr){
char * orig = arr;
unsigned short int count = 1;
char * ref = arr;
char * wrt = arr;
while (*arr != '\0'){
if (*ref == *arr && arr > ref){
++count;
}else if (*ref != *arr && arr > ref){
if (count >= 2){
int pc = sprintf(++wrt,"%d",count);
wrt += pc;
}
*(wrt) = *arr;
ref = arr;
count = 1;
}else
count = 1;
arr ++;
}
if (count >= 2){
int pc = sprintf(++wrt,"%d",count);
wrt += pc;
}
return orig;
}
public String encodeString( String s ){
if ( s == null || s.isEmpty()) return "";
char curChar = s.charAt(0);
int counter = 0;
for ( int i = 0; i < s.length; i += 1){
char newChar = s.charAt(i);
if ( newChar == curChar ) counter += 1;
else{
s.replaceFirst(""+curChar+"+",""+curChar+counter);
curChar = newChar;
counter = 0;
}
}
}
#include<stdio.h>
#include<string.h>
void Encode(char ch[], int size)
{
char abc[10]="",abd[10]="";
int i,j,flag=0,size1;
for(i=0;i<size-1;i++)
{
flag=ch[i]-97;
if(abc[flag]>0)
{
abc[flag]++;
}
else
{
abc[flag]=1;
abd[flag]=ch[i];
}
}
size1=strlen(abc);
for(j=0;j<size1;j++)
printf("%c%d",abd[j],abc[j]);
}
int main()
{
char buf[] = "aaaabadbaccdbd";
int size = sizeof(buf)/sizeof(buf[0]);
Encode(buf, size);
return 0;
}
char ch;
char arr[3]="\0";
int count = 0;
char input[] = "aaaabbccdddddeeee";
char result[50] = "\0";
int i;
ch = input[0];
for ( i = 0 ; input[i] != '\0'; i++ )
{
if( input[i] == ch )
{
count++;
continue;
}
else
{
ch = input[i];
snprintf( arr,sizeof(arr),"%c%d", input[i-1], count);
strcat( result, arr);
count = 1;
continue;
}
}
printf("%s\n", result);
public class EncodeString {
public static void main(String[] args) {
String s = "aaaabbccdd";
char a[] = s.toCharArray();
StringBuilder sb = new StringBuilder();
int count = 1;
TreeMap<Character, Integer> map = new TreeMap();
for (int i = 0; i < a.length; i++) {
if (map.containsKey(a[i])) {
count = map.get(a[i]);
count++;
map.put(a[i], count);
} else
map.put(a[i], 1);
}
for (Object key : map.keySet()) {
System.out.print(key.toString() + map.get(key).toString());
}
}
}
Java Code:
- sksantoshkumar090 January 09, 2014code is simple,effective and easy to understand.
public class Encrypt {
public static void main(String[] args) {
String string="aaaabbccdd";
StringBuffer sb=new StringBuffer("");
int count=0;
char str=string.charAt(0);
for(int i=0;i<string.length();i++)
{
if(str==string.charAt(i))
{
count++;
}
else
{
sb=sb.append(str);
str=string.charAt(i);
sb.append(count);
count=1;
}
}
System.out.println(sb);
}
}