Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
This solution works only if the repeat-count is one-digit, it is easy to change it to handle cases when repeat-count is 1+ digits
#include <stdio.h>
void convert(char *s);
int main() {
char string[] = "aaabbcccccccccddffffggaaaa";
convert(string);
printf("New string = %s\n", string);
return 0;
}
void convert(char *s) {
char *p = s; // points to the character to process in the original string
char *q = s; // points to where the result (char + repeat-counter) comes
int c;
int counter;
while (*p) {
c = *p;
counter = 0;
while (*p && *p == c) {
p++;
counter++;
}
*q++ = c;
*q++ = counter+'0'; // simple solution if < 10 chars repeated
}
*q = 0;
}
Considering the repetitive characters will appear consecutively, my solution is (in java)
public class testString {
public static void main(String args[])
{
String s = "aaaaabbcccccc";
for(int i=0;i<s.length();i++)
{
System.out.print(s.charAt(i)+""+(s.lastIndexOf(s.charAt(i))-s.indexOf(s.charAt(i))+1));
i = s.lastIndexOf(s.charAt(i));
}
}
}
You cannot do it without extra memory. You need at least a variable to keep the sums and a variable to keep the index of the character read/processed. A String is an immutable object, you cannot use it to store the sums or to pop elements to avoid the need of the index variable.
A string is immutable in Java or C#, but not in C ;)
So if you have a mutable string you can do it easily - given the condition that it is guaranteed that all characters happen more than once in the sequence as you can use the 2nd, 3rd, etc occurances to store the count (and beware of counts where it is >9!)
if the input is s="abc";
can input be lyk dis ..?
if yes it needs extra space na. since v hav 2 print lyk a1b1c1..?
am i ryt..?
if the input is s="abc";
can input be lyk dis ..?
if yes it needs extra space na. since v hav 2 print lyk a1b1c1..?
am i ryt..?
what about the input like aaabbacbc ? here also each character appeared more than once...
#include <iostream>
#include <string>
int main (int argc, char * argv[])
{
std::string str="aaabbbcccc";
while(str.rfind(str[0]) != std::string::npos){
std::cout << str[0] << str.rfind(str[0])+1;
str = str.substr(str.rfind(str[0]) + 1);
}
}
This is bad in several ways.
1. It is a completely incorrect algorithm. It only handles the case where all the occurrences of a given character are contiguous. For example, try it on the string ""aaabbbcccca".
2. It runs in O(n^2) time and O(n) extra space because of the substr() calls. It's possible for std::string to implement constant-time substr() if it uses reference counting to share substrings, but that is not required by the standard, nor is it commonplace in practice.
#include<stdio.h>
char* func(char *ip);
main(){
printf("%s\n",func("firefoxthunderbirddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd"));
getchar();
}
char* func(char *ip) {
int i=0,j=0,k=0;
int tmp[26] = {0,};
char temp_ch[100];
char *out = (char*) malloc(strlen(ip)+1);//this is to return required string from function
for(i=0; i<strlen(ip); i++){
tmp[ip[i]-'a']++;
}
i=0;
for(j=0;j<strlen(ip);j++){
if(tmp[ip[j]-'a'] != -1){
itoa(tmp[ip[j]-'a'],temp_ch ,10);
out[i++] = ip[j];
k=0;
while(temp_ch[k] != '\0')
{
out[i++] = temp_ch[k++];
}
tmp[ip[j]-'a'] = -1;
}
}
out[i] = '\0';
return out;
}
public static String compress(String data)
{
StringBuffer sb=new StringBuffer();
for(int i=0;i<data.length();)
{
sb.append(data.charAt(i));
int j=i;
int count=0;
while(j<data.length()&&data.charAt(i)==data.charAt(j))
{
j++;
count++;
}
if(count!=1)
sb.append(count);
i=i+count;
}
return sb.toString();
}
Java Code:
---------------
public class RunLengthEncoding {
public static void main(String [] args){
char[] a = {'a','a','a','a','b','b','b','b','a','c','b','c'};
int i =1;
char t = a[0];
int count = 1;
while(i<a.length){
if(a[i]==t){
count++;
} else {
System.out.print(t+""+count);
t = a[i];
count =1;
}
i++;
}
System.out.print(t+""+count);
}
}
Test cases:
a
aaaabbbbcc
aaaabbbbacbc
If we read the question properly we need not store the output , just need to print ,
So parse the string in O(n) and print the count if the string changes
void printOutput(String args[])
{
String s = args[] ;
s = "aaaaabbcccccc";
int count =1;
System.out.print(s.charAt(0));
for(int i=1;i<s.length();i++)
{
if(s[i-1]==s[i])
{
count++;
}
else
{
System.out.print(count);
System.out.print(s.charAt(i));
count=1;
}
}
System.out.print(count);
}
If we read the question properly we need not store the output , just need to print ,
So parse the string in O(n) and print the count if the string changes
void printOutput(String args[])
{
String s = args[] ;
s = "aaaaabbcccccc";
int count =1;
System.out.print(s.charAt(0));
for(int i=1;i<s.length();i++)
{
if(s[i-1]==s[i])
{
count++;
}
else
{
System.out.print(count);
System.out.print(s.charAt(i));
count=1;
}
}
System.out.print(count);
}
Since no extra memory is allowed, we can do an in place sorting (quick sort) O(nlogn) then in O(n) we can solve the problem. So over all time complexity is O(nlogn).
If we are allowed fixed memory use 32 elements int array. Use counting sort to count them out. Time complexity is O(n) then in fixed time we can complete the answer.
Since no extra memory is allowed, we can do an in place sorting (quick sort) O(nlogn) then in O(n) we can solve the problem. So over all time complexity is O(nlogn).
If we are allowed fixed memory use 26 elements int array. Use counting sort to count them out. Time complexity is O(n) then in fixed time we can complete the answer.
This problem is probably different than the one you had in mind. Basically all the repeated characters will be contiguous already without sorting. Plus the sorting approach won't work if the problem is like (id=12514668) where "aabbbaaaa" => "a2b3a4" instead of "a6b3", which is what I suspect you are trying to do.
public class Stringnumber {
public static void main(String[] args){
char [] str;
str = (new String("aaaabbbbcc")).toCharArray();
int cur =0, nex =1;
int i=0;
for(;nex<str.length;){
str[i]=str[cur];
i++;
int noOfRep=1;
while(nex<str.length && str[cur]==str[nex]){
noOfRep++;
nex++;
}
str[i]=new Integer(noOfRep).toString().charAt(0);
i++;
cur = nex;
nex++;
}
while(i<str.length){
str[i] = ' ';
i++;
}
System.out.println(str);
}
}
Since no extra memory is allowed, we can do an in place sorting (quick sort) O(nlogn) then in O(n) we can solve the problem. So over all time complexity is O(nlogn).
If we are allowed fixed memory use 26 elements int array. Use counting sort to count them out. Time complexity is O(n) then in fixed time we can complete the answer.
Map<Character, Integer> map = new TreeMap<Character, Integer>();
String input = "aaaabbbbcccccccccxxxxxxxxxxxxxxaaaaaaaaaaaaaaacc";
for (int i = 0; i < input.length(); i++) {
char in = input.charAt(i);
if(in == ' ' )continue;
if(map.get(in) != null){
int count = map.get(in);
map.put(in, ++count);
}else {
map.put(input.charAt(i), 1);
}
}
Iterator it = map.keySet().iterator();
input = "";
while (it.hasNext()) {
Character ch = (Character)it.next();
int i = map.get(ch);
input += ch.toString() + i;
}
System.out.print(input);
char* prev = 0;
int currentcount = 0;
char* writehere = source;
for( char* i = source; *i; i++ )
{
if( prev == NULL || *prev != *i )
{
if( prev != NULL )
{
*writehere++ = *prev
if( currentcount > 1 ){
char* temp = itoa( currentcount, writehere, 10 );
writehere += strlen(temp);
}
}
prev = i;
currentcount = 1;
}
else
currentcount++;
}
*writehere = 0;
public class AlphabetCount {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
System.out.println("Enter the string");
String s1 = in.next();
format(s1);
}
public static void format(String s1) {
char prev = s1.charAt(0);
StringBuffer str = new StringBuffer();
int count = 0;
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
if (c == prev) {
count++;
} else {
str.append(prev);
str.append(count);
count = 1;
}
prev = c;
}
str.append(prev);
str.append(count);
System.out.println(str);
}
}
public class AlphabetCount {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
System.out.println("Enter the string");
String s1 = in.next();
format(s1);
}
public static void format(String s1) {
char prev = s1.charAt(0);
StringBuffer str = new StringBuffer();
int count = 0;
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
if (c == prev) {
count++;
} else {
str.append(prev);
str.append(count);
count = 1;
}
prev = c;
}
str.append(prev);
str.append(count);
System.out.println(str);
}
}
public class AlphabetCount {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
System.out.println("Enter the string");
String s1 = in.next();
format(s1);
}
public static void format(String s1) {
char prev = s1.charAt(0);
StringBuffer str = new StringBuffer();
int count = 0;
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
if (c == prev) {
count++;
} else {
str.append(prev);
str.append(count);
count = 1;
}
prev = c;
}
str.append(prev);
str.append(count);
System.out.println(str);
}
}
String test="eaavevvqwqaa";
int count=0,start=0,end=0;
int length=test.length();
for(int i=0;i<length-1;i++){
if(test.charAt(i)!=test.charAt(i+1)){
end=i;
test=test+""+test.charAt(i)+( end-start+1);
count=count+(end-start+1);
start=end+1;
}
}
System.out.println(test.length());
if(count<length){
test=test+test.charAt(count)+(length-count);
}
test=test.substring(length,test.length());
System.out.println(test);
System.out.println(test.length());
package com.mishra;
import java.util.Scanner;
public class PrintArraywithRepetation {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s = new Scanner(System.in);
String input = s.next();
int count=1;
for(int i=0 ;i<input.length();i++){
if(i<input.length()-1){
if(input.charAt(i)!=input.charAt(i+1)){
System.out.print(input.charAt(i));
System.out.print(count);
count=1;
}
else
count++;
}
else if(i==input.length())
{
if(input.charAt(i)!=input.charAt(i-1)){
System.out.print(input.charAt(i));
System.out.print(count);
count=1;
}
else
count++;
}
else {
System.out.print(input.charAt(i));
System.out.print(count);
count++;
}
}
}
}
package com.mishra;
import java.util.Scanner;
public class PrintArraywithRepetation {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s = new Scanner(System.in);
String input = s.next();
int count=1;
for(int i=0 ;i<input.length();i++){
if(i<input.length()-1){
if(input.charAt(i)!=input.charAt(i+1)){
System.out.print(input.charAt(i));
System.out.print(count);
count=1;
}
else
count++;
}
else if(i==input.length())
{
if(input.charAt(i)!=input.charAt(i-1)){
System.out.print(input.charAt(i));
System.out.print(count);
count=1;
}
else
count++;
}
else {
System.out.print(input.charAt(i));
System.out.print(count);
count++;
}
}
}
}
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));
strBuf.append(count);
count = 1;
}
}
strBuf.append(str.charAt(str.length()-1));
strBuf.append(count);
return strBuf.toString();
}
I don't really understand what are restricted to use by saying no extra space. Because in Java, a String is immutable, so we have to create a character array from the given String, and create a String back from the modified character array. If those are the valid usage of extra memory, then here's my implementation in Java.
I've explained the code with appropriate comment, in case anyone needs an explanation:
public static void encodeString(String str) {
char[] arr = str.toCharArray();
int i = 0;
int indicesLeftVacant = 0;
while (i < arr.length - 1) {
int j = i + 1;
while (j < arr.length && arr[j] == arr[i]) {
j++;
}
// Move the current character to next eligible index, that will be after the
// previous occurrence count was written. So, we need to move the character
// indicesLeftVacant times from the original index.
arr[i - indicesLeftVacant] = arr[i];
// (j - i) gives the total number of the current character. We need to put
// it in the index next to this character. (i - indicesLeftVacant + 1)
arr[i - indicesLeftVacant + 1] = (char)((j - i) + (int)'0');
// (j - i - 2) will be the number of indices left free.
// So, add it to indicesLeftVacant
indicesLeftVacant += (j - i) - 2;
// Set i to j, to start looking from the next sequence of characters.
i = j;
}
// The new array length will be the original length reduced by indicesLeftVacant.
// So, create the new String from index 0 till that length from array.
System.out.println(new String(arr, 0, arr.length - indicesLeftVacant));
}
In some other languages, you can modify strings, so the problem statement is a little more restrictive than that. Think of it as having an array that contains all the characters of the string. You need to perform the specified operation on the array without taking any extra arrays or other extra storage beyond a constant amount (for example a few primitive variables).
This code handles everything one wants.
- nihaldps March 06, 2012