Did-it.com Interview Question
Software Engineer / DevelopersThis seems easy. Have a second string or a char array. Read the given string char by char & copy every char to the new string. Whenever we encounter 'A' or 'a' in the given string, copy the char 'o', 'n' & 'e' into the new string at the current index. We will obviously need 2 indices, one to parse the given string and another to form the new string.
Eg. "This is a bus" becomes "This is one bus".
This process just takes one loop. Hence, O(n) is the complexity.
Java Code:
public static String replace(String oldStr)
{
String replacedRst="";
char curChar;
for(int i=0; i<oldStr.length(); i++)
{
curChar=oldStr.charAt(i);
if((curChar=='a')||(curChar=='A'))
{
replacedRst=replacedRst+"one";
}
else
replacedRst=replacedRst+curChar;
}
return replacedRst;
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char a[25], b[35];
int i,j;
clrscr();
printf("\nEnter string: ");
scanf("%s",&a);
j=0;
for(i=0;i<strlen(a);i++)
{
if(a[i]=='A' || a[i]=='a')
{
b[j]='o';
b[j+1]='n';
b[j+2]='e';
j=j+3;
}
else
{
b[j]=a[i];
j=j+1;
}
}
printf("\nNew string is: ");
for(i=0;i<strlen(b);i++)
printf("%c",b[i]);
getch();
}
C# Code
using System;
using System.Collections.Generic;
using System.Text;
namespace ReplaceString
{
class Program
{
static void Main(string[] args)
{
string stringinput = Console.ReadLine();
string stringReplaced = "";
for (int i = 0; i < stringinput.Length; i++)
{
if (stringinput[i] != 'a' && stringinput[i] != 'A')
stringReplaced += stringinput[i].ToString();
else
stringReplaced += "one";
}
Console.WriteLine(stringReplaced);
Console.ReadLine();
}
}
}
step1 : words[] = sentence.split(" ") // splitting sentence on every space
step2: foreach word in words[], check if it is "A" or "a", word = "One"
Step3: StringBuilder replacedSentence = replacedSentence.append(word+" ");
Complexity overview: Extra memory complexity in terms of String array, builder usage, but O(n) in solving the problem
Any Comments ?
Another approch which can somewhat reduce memory complexity is using a stringTokenizer as follows:
public String replaceAllWords() {
String original = "A man and a woman";
String result = "";
String delimiters = " ";// space
StringTokenizer st = new StringTokenizer(original, delimiters, true);
while (st.hasMoreTokens()) {
String w = st.nextToken();
if (w.equals("a") ||w.equals("A")) {
result = result + "One";
} else {
result = result + w;
}
}
return result;
}
#include<iostream>
#include<string.h>
#include <iomanip>
using namespace std;
int main()
{
int n,i;
string str;
cin>>str;
n=str.length();
cout<<n<<endl;
/*char *a=new char[n+1];
strcpy(a,str.c_str());
for (i=0;i<n;i++)
{
if (a[i]=='a'||a[i]=='A')
{
a[i]='1';
}
}*/
for(i=0; i<=n; i++)
{
if(str.at(i) == 'a')
str.at(i) = '1';
}
cout<<str<<endl;
return 0;
}
This seems easy. Have a second string or a char array. Read the given string char by char & copy every char to the new string. Whenever we encounter 'A' or 'a' in the given string, copy the char 'o', 'n' & 'e' into the new string at the current index. We will obviously need 2 indices, one to parse the given string and another to form the new string.
- Vik October 18, 2009Eg. "This is a bus" becomes "This is one bus".
This process just takes one loop. Hence, O(n) is the complexity.