Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Or A1B1C4 where the starting and ending string are of the same length and you start from the end overwriting B1
public class ExpandString {
public static void main(String[] args) {
String data ="A2B3C4 ";
char[] arr = data.toCharArray();
expandString(arr);
System.out.println(arr);
}
public static void expandString(char[] arr){
int endOfModified = arr.length -1;
int i = arr.length;
while (i>0){
i--;
if (arr[i]!=' '){
int n = arr[i]-'0';
i--;
char c = arr[i];
//System.out.format("n=%c, c=%c",n,c);
for (int j=1;j<=n;j++){
arr[endOfModified] = c;
endOfModified--;
}
}
}
}
}
any character with 0 frequency will not be there....i mean D0 can't be there in your string otherwise A3B24C1 can be there...
public void decompress(char[] str) {
int lookAt = str.length - 1;
while (!Character.isLetterOrDigit(str[lookAt])) {
--lookAt;
}
int assignTo = str.length - 1;
while (lookAt > 0) {
if (Character.isLetter(str[lookAt])) {
str[assignTo--] = str[lookAt--];
continue;
}
int count = Integer.valueOf("" + str[lookAt]);
--lookAt;
while (count-- > 0) {
str[assignTo--] = str[lookAt];
}
--lookAt;
}
}
public static void main(String[] args) {
String str="a1f1b2c3d4";
char char1;
for(int i=0;i<str.length();i++)
{
char1=str.charAt(i);
//System.out.println("chacr1::"+char1);
char c2=str.charAt(i);
if(char1 >=97 && char1 <=123)
{
//System.out.println("chacr122::"+char1);
}
else
{
//int no=(int)char1;
String st=Character.toString(char1);
int x=Integer.parseInt(st);
//System.out.println("no:::"+no+"DDD"+x);
for(int k=0;k<x;k++)
System.out.print(" "+str.charAt(i-1));
}
}
}
I think my code will work.
public static void main(String args[]){
String sat = "A2B3C4";
char[] sat1 = sat.toCharArray();
for(int i=1;i<sat1.length;i=i+2){
int num = Character.getNumericValue(sat1[i]);
for(int j=0;j<num;j++){
System.out.print(sat1[i-1] + " ");
}
}
}
I guess instead of Character.getNumericValue(sat1[i]) we should use Integer.parseInt(String.valueOf(sat1[i]))
public class StringDemo {
/**
* @param args
*/
String demo="A2B3C2";
int arr[]=new int[5];
char finalString[]=new char[7];
public void STringExpanded(){
int len=demo.length();
int j=0;
System.out.println(len);
for(int i=1;i<len;i++)
{
if(i%2!=0)
{
char a=demo.charAt(i);
arr[j]=(int) (demo.charAt(i)-'0');
System.out.println("value of a"+a);
j++;
}
}
PrintString();
System.out.println(arr[1]);
}
public void PrintString()
{
int p=0;
int j=0;
for(int i=0;i<demo.length();i++)
{
if(i%2==0)
{
for(int k=0;k<arr[j];k++)
{
System.out.println(demo.charAt(i));
finalString[p]=demo.charAt(i);
p++;
}
j++;
}
}
System.out.println(finalString);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
StringDemo str=new StringDemo();
str.STringExpanded();
}
}
static void Main(string[] args)
{
String str = "A2B3C9";
int i=str.Length-1;
String finalString = "";
while (i != -1)
{
if (Char.IsDigit(str, i))
{
char charToCopy = str[i-1];
String tempString = null;
for (int j = 0; j < char.GetNumericValue(str[i]); j++)
{
tempString += charToCopy;
}
finalString = tempString + finalString;
i--;
}
else
{
finalString = str[i] + finalString;
}
i--;
}
Console.WriteLine("Original string is " + str);
Console.WriteLine("Final string is "+finalString);
}
Here is the code that will uncompress even when the no of repetitions are >=10 (two digits or more)
Logic:
1. Two pass. First pass will identify the length of the output string
2. Second pass will run from the end to the beginning of string and writes the repeated character back
Code below -
#include <stdio.h>
#include <string.h>
#include <ctype.h>
void uncompress(char *str, int len)
{
/* First pass to find the length of decompressed string */
int read_idx = 0, new_len = 0;
while ( read_idx < len ) {
read_idx++; /* Skip char */
int curr_char_len = 0;
/* Run till we find a char or reach the end;
and count the no of characters that will be written */
while ( isdigit( str[read_idx] ) && read_idx < len )
curr_char_len = 10 * curr_char_len + ((int) str[read_idx++] - '0');
new_len += curr_char_len;
}
/* Second pass to write the uncompressed string. Will start reading and writing from the end */
str[new_len] = '\0';
int write_idx = new_len - 1;
while ( --read_idx > 0 ) { /* Skipping char in the loop check */
int curr_char_len = 0, power_of_ten = 1;
while ( isdigit( str[read_idx] ) && read_idx >= 0) {
curr_char_len = curr_char_len + power_of_ten * ((int) str[read_idx--] - '0');
power_of_ten = 10 * power_of_ten;
}
/* Write the char at str[read_idx] to write_idx position curr_char_len times */
while (curr_char_len--) str[write_idx--] = str[read_idx];
}
}
int main()
{
char str[100] = "A12B3C24D1E7D11K1";
uncompress(str, strlen(str));
printf("Uncompressed string is %s\n", str);
}
Hope this suffices. Please update if you find any issues.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void main()
{
int len,sum=0,i,j,k=0;
char *a,b[20];
printf("\nEnter string");
scanf("%s",b);
for(i=0;i<strlen(b);i=i+2)
{
sum=sum+b[i+1]-'0';
}
sum=sum+(strlen(b)/2);
a=(char *)malloc(sizeof(char)*sum+1);
for(i=0;i<strlen(b);i=i+2)
{
len=b[i+1]-'0';
a[k++]=b[i];
while(len---1)
a[k++]=b[i];
}
printf("%s",a);
}
This is the C# code - this should work just fine
TESTED with
a0b1c1
a100b44c22
a2b3c4
(Only thing left in the code is to check the length of input and output and make decision accordingly)
public static string runLengthDecodeSB(string str)
{
if (string.IsNullOrEmpty(str)) return str;
StringBuilder sb = new StringBuilder();
char lastChar = str[0];
int counter = 0;
for (int i = 1; i < str.Length; i++)
{
char thisChar = str[i];
//If couldn't think of the inspiration - char.IsDigit - think, how about ASCII range for numbers 0 - 9
if (!char.IsDigit(thisChar))
{
//Realize that you should print first. Before resetting the lastChar and counter.....
for (int j = 0; j < counter; j++)
sb.Append(lastChar);
lastChar = thisChar;
counter = 0;
}
else
{
if (counter == 0)
counter = int.Parse(thisChar.ToString());
else
counter = (counter * 10) + int.Parse(thisChar.ToString());
}
}
//Easy to forget this - tricky, don't be off by one.....
for (int j = 0; j < counter; j++)
sb.Append(lastChar);
return sb.ToString();
}
JavaScript solution
function decompress(content) {
var result = [];
for (var i = 0; i < content.length; ++i) {
var curChar = content.charAt(i);
if (i + 1 < content.length) {
var nextChar = content.charAt(i + 1);
var charNum = parseInt(nextChar, 10);
if (!isNaN(charNum)) {
curChar = new Array(charNum + 1).join(curChar);
++i;
}
}
result.push(curChar);
}
return result.join('');
}
public void uncompressString(String value){
char[] values = value.toCharArray();
char prev = values[0];
StringBuilder sb = new StringBuilder("");
sb.append(prev);
for(int i=1 ; i < values.length ;i++){
if(values[i]>='0' && values[i] <='9'){
int count = Integer.parseInt("" + values[i]);
for(int j = 1 ; j < count ; j++ ){
sb.append(prev);
}
}
else{
prev = values[i];
sb.append(prev);
}
}
System.out.println(sb.toString());
}
#include<iostream>
#include<conio.h>
#include<cmath>
using namespace std;
template<class Object>
class Singly;
template<class Object>
class Node{
public:
Node()
{
m_pNodeNext = NULL;
}
friend Singly<Object>;
private:
Node<Object>* m_pNodeNext;
Object objElement;
};
template<class Object>
class Singly{
public:
Singly()
{
m_pNodeFirst = NULL;
}
void insert(const Object& refObjElement);
void print();
private:
Node<Object>* m_pNodeFirst;
};
template<class Object>
void Singly<Object>::insert(const Object& refObjElement)
{
if(m_pNodeFirst == NULL)
{
m_pNodeFirst = new Node<Object>;
m_pNodeFirst->objElement = refObjElement;
m_pNodeFirst->m_pNodeNext = NULL;
}
else
{
Node<Object>* pNodeCurrent = m_pNodeFirst;
while(pNodeCurrent->m_pNodeNext != NULL)
{
pNodeCurrent = pNodeCurrent->m_pNodeNext;
}
Node<Object>* pNodeNew = new Node<Object>;
pNodeNew->objElement = refObjElement;
pNodeNew->m_pNodeNext = NULL;
pNodeCurrent->m_pNodeNext = pNodeNew;
}
}
template<class Object>
void Singly<Object>::print()
{
if(m_pNodeFirst == NULL)
{
cout << "list is empty" << endl;
}
else
{
Node<Object>* pNodeCurrent = m_pNodeFirst;
while(pNodeCurrent != NULL)
{
cout << pNodeCurrent->objElement << ",";
pNodeCurrent = pNodeCurrent->m_pNodeNext;
}
cout << endl;
}
}
Singly<char> expandstring(char* pChrArray, int nLength)
{
Singly<char> singlyListOfExpandedChars;
for(int i = 0; i < nLength; i++)
{
int nCurrentChar = pChrArray[i];
if(nCurrentChar >= 48 && pChrArray[i] <= 57)
{
int j = i;
while(nCurrentChar >= 48 && nCurrentChar <= 57)
{
i++;
nCurrentChar = pChrArray[i];
}
int nTotal = 0;
for(int t = j; t < i; t++)
{
int nCharAsNum = pChrArray[t];
int nActualValue = nCharAsNum - 48;
nTotal = nTotal + nActualValue * pow(10.0,(i - t - 1));
}
for(int k = 0; k < nTotal; k++)
{
singlyListOfExpandedChars.insert(pChrArray[j - 1]);
}
i--;
}
}
return singlyListOfExpandedChars;
}
int main()
{
char chrArray[] = "A2B3C4D10E11";
cout << "orriginal string-" << endl;
for(int i = 0; i < strlen(chrArray); i++)
{
cout << chrArray[i] << ",";
}
cout << endl;
Singly<char> chrListExpanded = expandstring(chrArray, strlen(chrArray));
cout << "expanded string" << endl;
chrListExpanded.print();
_getch();
}
public class expand
{
public static void main(String args[])
{
String s = "A2B3C1";
int length = s.length();
StringBuffer result = new StringBuffer();
for(int i = 0; i<length-1; )
{
char a1 = s.charAt(i);
int a2 = Character.getNumericValue((s.charAt(i+1)));
while(a2!=0)
{
result.append(a1);
a2--;
}
i=i+2;
}
String s2 = result.toString();
System.out.println(s2);
}
}
content = ['A',3,'B',3,'C',5,'','','','','']
totalLen = len(content)
def expand(content,indx):
if content[indx].__str__().strip() == '':
return len(content)
totalLen = expand(content,indx+1)
if type(content[indx])==int:
l = content[indx]
for num in xrange(content[indx]):
content[totalLen-l+num] = content[indx-1]
totalLen = totalLen-l
return totalLen
if __name__ == "__main__":
expand(content,0)
print content
content = ['A',3,'B',3,'C',5,'','','','','']
totalLen = len(content)
def expand(content,indx):
if content[indx].__str__().strip() == '':
return len(content)
totalLen = expand(content,indx+1)
if type(content[indx])==int:
l = content[indx]
for num in xrange(content[indx]):
content[totalLen-l+num] = content[indx-1]
totalLen = totalLen-l
return totalLen
if __name__ == "__main__":
expand(content,0)
print content
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char expanded_string[1000];
void expand_string(char* src)
{
char temp;
int i = 0, j = 0, k = 0;
int no_of_times = 0;
for(i=0;i<strlen(src);i+=2)
{
no_of_times = src[i+1] - '0';
for(j=0;j<no_of_times;j++)
{
expanded_string[k++] = src[i];
}
}
}
int main()
{
expand_string("A3B4C4");
printf("expanded string: %s", expanded_string);
return 0;
}
Simple C# solution
private static string expandString2(string s)
{
var target = new List<string>();
for (int i = 0; i < s.Length; i++)
{
string c = Convert.ToString(s[i]);
int x = 0;
if (int.TryParse(c, out x))
{
for (int j = 0; j < x - 1; j++)
{
target.Add(Convert.ToString(s[i - 1]));
}
}
else
{
target.Add(Convert.ToString(s[i]));
}
}
var sb = new StringBuilder();
for (int i = 0; i < target.Count; i++)
{
sb.Append(target[i]);
}
return sb.ToString().Length == s.Length ? s : sb.ToString();
}
i dont know whether i am right or wrong ...i have developed this code and it works fine with the condition
#include<stdio.h>
main()
{
char str[6]={'a',6,'b',8,'c',4};
int i,j;
for(i=0;i<6;)
{
for(j=0;j<3;j++)
{
printf("%c ",str[i]);
}
i=i+2;
}
system("PAUSE");
}
package notcert;
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Propagate
{
public static void main (String[] args) throws java.lang.Exception
{
String s="a11b4c5";
char[] chars= s.toCharArray();
StringBuilder sb=new StringBuilder();
int i=0;
int optionalNumberValue = 0;
do{
char ch=chars[i];
int numberValue=Character.getNumericValue(chars[i+1]);
if(i+2<chars.length){
optionalNumberValue=Character.getNumericValue(chars[i+2]);
}
if(optionalNumberValue>=1 && optionalNumberValue<=9){
numberValue=Integer.parseInt(String.valueOf(numberValue)+String.valueOf(optionalNumberValue));
i++;
}
for(int j=0;j<numberValue;j++){
sb.append(ch+"");
}
i+=2;
}while(i<chars.length);
System.out.println(sb);
}
}
public class ExpandString {
public static void main(String[] args) {
String data ="AB12B3C14";
char[] arr = data.toCharArray();
String tmpStr = "";
String tmpNum = "";
for (int i = 0; i < arr.length; i++) {
try{
Integer.parseInt(arr[i]+"");
tmpNum = tmpNum+arr[i];
}catch(Exception e){
if(!(tmpStr.equals("") || tmpNum.equals(""))){
for(int j=0;j<Integer.parseInt(tmpNum);j++){
System.out.print(tmpStr);
}
tmpStr = "";
tmpNum = "";
}
tmpStr = tmpStr+arr[i];
}
if(i==arr.length-1){
for(int j=0;j<Integer.parseInt(tmpNum);j++){
System.out.print(tmpStr);
}
}
}
}
}
#include<stdio.h>
#include<string.h>
int main(){
char *s,str[10],ch;
int l,i,j,count=0;
scanf("%s",str);
l=strlen(str);
s=&str;
for(j=0;j<l;j++)
{
if((*s>='a'&&*s<='z')||(*s>='A'&&*s<='Z'))
{
ch=*s;
s++;
}
else
{
count = *s-48;
for(i=0;i<count;i++)
{
printf("%c ",ch);
}
s++;
}
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
void string_expansion(char* str) {
if (!str) return;
char * tmp = (char*) malloc(strlen(str)+1);
int i = 0, j =0;
for (i = 0; i < strlen(str); i+=2)
{
int idx = *(str+i+1) - '0';
while(idx--) {
tmp[j++] = *(str+i);
}
}
tmp[j] = '\0';
strcpy(str,tmp);
free(tmp);
}
main() {
char str[10] = "a2b3c4";
string_expansion(str);
printf("str: %s\n", str);
getchar();
}
The trick is to start from the end.
- Nitin Gupta March 04, 2013