Amazon Interview Question Software Engineer / Developers
Isn't this better.
You might have to input files to convert number to string(itoa) and I don't know if I have used right strcat.
But just trying to shorten the logic here.
void convert(char *string)
{
char *encode;
int count = 0;
char tmp;
while( string)
{
tmp = *string++;
count++;
if (tmp != *string)
{
*encode++ = tmp;
string numb = itoa(count);
strcat(encode,numb);
count = 0;
}
}
}
int main()
{
char input[100];
cout<<"Enter the string: ";
scanf("%s", input);
cout<<"You entered: "<<input<<"!!\n";
convert(input);
return 0;
}
adding on your idea: (now this works)
- itoa can't be used. It is non-ISO function. Also not defined in stdlib.h
- For now assuming that no letter will repeated more than 9 times. Hence our count will not exceed 9.
codE:
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
char *convert(char *string)
{
static char output[53]; // assuming 26 different in input; last one for '\0'
int count = 0, track=0;
char digit;
while(*string)
{
output[track] = *string++;
count++;
if (output[track] != *string) // //compare with next letter in string
{
track++;
if (count > 1) // block not reqd //when no repetitions (abb should be abb2)
{
digit = count + 48; // //adding ASCII value for the digit
output[track++] = digit;
}
count = 0;
}
}
output[track] = '\0'; // mark end of output //array, not reqd since static initializes to repetitive //'\0'
return(output);
}
int main()
{
char input[100];
char *now;
cout<<"Enter the string: ";
scanf("%s", input);
cout<<"You entered: "<<input<<"!!\n";
now = convert(input);
cout<<"Final Output: "<<now<<endl;
return 0;
}
Note:
- To allow more than 9 repetitions, we can implement a separate itoa function
Some bugs cleared
#include <iostream.h>
#include <string.h>
#include <conio.h>
char *convert(char *string)
{
static char output[53]; // assuming 26 different in input; last one for '\0'
int count = 0, track=0;
char digit;
while(*string)
{
output[track] = *string++;
count++;
if (output[track] != *string) // //compare with next letter in string
{
track++;
if (count > 1) // block not reqd //when no repetitions (abb should be abb2)
{
digit = count + 48; // //adding ASCII value for the digit
output[track++] = digit;
}
count = 0;
}
}
output[track] = '\0'; // mark end of output //array, not reqd since static initializes to repetitive //'\0'
return(output);
}
int main()
{
char input[100];
char *now;
cout<<"Enter the string: ";
cin>>input;
cout<<"You entered: "<<input<<"!!\n";
now = convert(input);
cout<<"Final Output: "<<now<<endl;
getch();
}
Actually itoa should work fine with this.
#include <iostream>
#include <string>
using namespace std;
char* convert(char *string)
{
char encode[50];
int count = 0,track =0;
char tmp;
char b[50];
char* numb;
while(*string)
{
tmp = *string++;
count++;
if (tmp != *string)
{
encode[track] = tmp;
track++;
numb = itoa(count,b,10);
encode[track++] = *numb;
count = 0;
}
}
encode[track] = '\0';
return encode;
}
int main()
{
char input[100];
char* converted;
memset(input, 0, 100);
cout<<"Enter the string: ";
cin >> input;
cout<<"You entered: "<<input<<"!!\n";
converted = convert(input);
return 0;
}
Opps, the above solution crashed when the number of duplicate exceed 10.
void encode(char *s)
{
int i,j=0,len=strlen(s);
int count;
char buffer[10];
int index;
char n;
for(i=0;i<len;i++){
s[j++]=s[i];
if(s[i]==s[i+1]){
count=2;
i++;
index=0;
while(s[i]==s[i+1]){
i++;count++;
}
while(count){
n=count%10+'0';
count/=10;
buffer[index++]=n;
}
index--;
while(index>=0)
s[j++]=buffer[index--];
}
}
s[j]='\0';
}
void code(std::string str) //Complexity o(n*n)
{
std::map<std::string,int> mp;
std::map<std::string,int>::iterator ii;
int len=str.length();
char *s=&str[0];
int count=0;
while(count<len)
{
char ch=*(s+count);
std::string sd(&ch,1);
mp[sd]=0;
count++;
}
count=0;
for(ii=mp.begin(); ii!=mp.end(); ++ii)
{
std::string ss=(*ii).first;
while(count<len)
{
char ch=*(s+count);
std::string sd(&ch,1);
if(!ss.compare(sd))
{
(*ii).second++;
}
count++;
}
count=0;
}
for(ii=mp.begin(); ii!=mp.end(); ++ii)
{
std::cout << (*ii).first << ": " << (*ii).second << std::endl;
}
}
void main()
{
int hash[256];
char *str="aaabbbbbbccccddddeeeeeee";
for(int i=0;i<256;i++) hash[i]=0;
int len=strlen(str);
for(i=0;i<len;i++)
{
hash[str[i]]++;
}
char buf[100];
char *p=buf;
for(i=0;i<256;i++)
{
if(hash[i])
{
len=sprintf("%c%d",i,hash[i]);
}
p = p + len;
}
p = NULL;
printf("%s\n",buf);
}
void main()
{
int hash[256];
char *str="aaabbbbbbccccddddeeeeeee";
for(int i=0;i<256;i++) hash[i]=0;
int len=strlen(str);
for(i=0;i<len;i++)
{
hash[str[i]]++;
}
char buf[100];
char *p=buf;
for(i=0;i<256;i++)
{
if(hash[i])
{
len=sprintf(buf,"%c%d",i,hash[i]);
}
p = p + len;
}
p = NULL;
printf("%s\n",buf);
}
sprintf writes to the buffer formatted strings... so, no tensions for itoa and all.. the code also runs in O(n)... best possible soln i can think of...
some minor bugs corrected
void main()
{
int hash[256];
char *str="aaabbbbbbccccddddeeeeeee";
for(int i=0;i<256;i++) hash[i]=0;
int len=strlen(str);
for(i=0;i<len;i++)
{
hash[str[i]]++;
}
char buf[100];
char *p=buf;
for(i=0;i<256;i++)
{
if(hash[i])
{
len=sprintf(p,"%c%d",i,hash[i]);
p = p + len;
}
}
p = NULL;
printf("%s\n",buf);
}
sprintf writes to the buffer formatted strings... so, no tensions for itoa and all.. the code also runs in O(n)... best possible soln i can think of...
void codeString(char s[])
{
int size = strlen(s);
int i, len=1, index=0;
char temp = s[0];
for (i=1; i< size; i++)
{
if (s[i] == temp )
{
len++;
continue;
}else
{
if (len > 1)
{
s[index++]= temp;
s[index++]= '0'+ len;
temp = s[i];
len=1;
}else
{
s[index++]= temp;
temp = s[i];
}
}
}
s[index++]= temp;
if (len >1)
s[index++]= '0'+ len;
s[index]='\0';
}
void codeString(char s[])
{
int size = strlen(s);
int i, len=1, index=0;
char temp = s[0];
for (i=1; i< size; i++)
{
if (s[i] == temp )
{
len++;
continue;
}else
{
if (len > 1)
{
s[index++]= temp;
s[index++]= '0'+ len;
temp = s[i];
len=1;
}else
{
s[index++]= temp;
temp = s[i];
}
}
}
s[index++]= temp;
if (len >1)
s[index++]= '0'+ len;
s[index]='\0';
}
public static void main(String args[]) {
String s = "abbbccddddeee";
char[] ca = s.toCharArray();
String s_ = "";
for(int i=0; i<ca.length; i++) {
s_ = s_ + ca[i];
int j=1;
for(;j+i<ca.length; j++) {
if(ca[i+j] != ca[i]) {
break;
}
}
if(j > 1) {
s_ = s_ + j;
i += j - 1;
}
}
System.out.println(s_);
}
std::string compress(std::string str){
std::string result="";
int i=0;
while(i<str.length()){
int count=1;
result.push_back(str[i]);
while((str[i]==str[i+1])&&(i<str.length())){
++count;
i++;
}
if(count>1){
char buffer[4];
memset(buffer,'\0',1);
itoa(count,buffer,10);
std::string temp(buffer);
result.append(buffer);
//result.push_back(temp.c_str());
}
i++;
}
return result;
}
It is simple
#include<stdio.h>
int main()
{
char string[60],i,j,count;
printf("Enter a string\n");
scanf("%s",&string);
for(i=0;i<=strlen(string);i++)
{
count=0;
for(j=i;j<=strlen(string);j++)
{
if(string[i]==string[j]) ++count;
else
{
if(count==1) printf("%c",string[i]);
else printf("%c%d",string[i],count);
i=i+count-1;
break;
}
}
}
getch();
return 0;
}
why are some of you guys just printing the string with the number of time it is repeated? You have to modify the string, not just print to the console. It's just plain stupid and dumb...
I know I am not helping anybody without writing any code...but it is better not to write anything rather than some stupid logic
package com.amazon.interview.general;
public class CompactString {
public static void main(String[] args) {
String str = "aabbbcddeefggg";
System.out.println(compact(str));
System.out.println(compact(null));
System.out.println(compact("a"));
System.out.println(compact("aa"));
System.out.println(compact("ab"));
System.out.println(compact("aabb"));
System.out.println(compact("abcedf"));
System.out.println(compact("aabbccddeeefffggg"));
System.out.println(compact("abccc"));
}
private static String compact(String str) {
System.out.println(str);
if (str == null)
return null;
if (str.length() < 1)
return str;
StringBuilder sb = new StringBuilder();
char ch = str.charAt(0);
int count = 0;
for (char t : str.toCharArray()) {
if ( t == ch) {
count ++;
} else {
sb.append(ch);
sb.append(count);
ch = t;
count = 1;
}
}
sb.append(ch);
sb.append(count);
return sb.toString();
}
}
Time O(n) and Space complexity using a buffer
public static void numberString()
{
String str = "abbbccddddeee";
StringBuilder build = new StringBuilder();
build.append(str.charAt(0));
int charCount = 1;
for (int i = 1; i < str.length(); i++)
{
if ( str.charAt(i) == str.charAt(i-1))
charCount++;
else
{
if (charCount > 1)
{
build.append(charCount);
charCount = 1;
}
build.append(str.charAt(i));
}
}
if ( charCount > 1)
build.append(charCount);
System.out.println("Modified String: " + build.toString());
}
void compress(char a[]){
int len = strlen(a), i, j = 0, count = 1;
for(i = 1; i <= len; i++){
if(a[i] != a[j]){
if(count > 1 && count < 10)
a[++j] = 48 + count;
a[++j] = a[i];
count = 1;
}
else
count++;
}
a[++j] = '\0';
}
#include<iostream>
- Ganesh December 22, 2008#include <strstream>
#include<stdlib.h>
#include<string.h>
using namespace std;
void convert(char *input)
{
char *start = input;
char *s1 = input;
char *s2 = input + 1;
int len = strlen(input);
int count = 0;
char *end = start;
while(--len && *s1 && *s2 )
{
while(*s1 && *s2 && len && *s1 == *s2)
{
++count;
s2++;
--len;
}
if(count)
{
ostrstream str;
str<<(count+1);
*start = *s1;
*++start = *(str.str());
start = start + strlen(str.str()) - 1;
count = 0;
}
else
*start = *s1;
start++;
s1 = s2;
s2++;
}
if(*s1 != *(s1-1))
*start++ = *s1;
*start = *s2;
cout<<"Magic: "<<end<<endl;
return;
}
int main()
{
char input[100];
memset(input, 0, 100);
cout<<"Enter the string: ";
scanf("%s", input);
cout<<"You entered: "<<input<<"!!\n";
convert(input);
return 0;
}
Guess we can still optimise the above program. Can someone give a try ?