Amazon Interview Question
SDETsCountry: United States
Interview Type: Phone Interview
import java.util.Scanner;
public class replaceString {
public static void main(String[] args) {
System.out.println("Enter the String : ");
Scanner scan = new Scanner(System.in);
String actStr = scan.next();
System.out.println("Aactual String = " + actStr);
String replacedStr = actStr.replaceAll("%20", " ");
System.out.println("Changed String = " + replacedStr);
}
}
import java.util.Scanner;
class Cc
{
public static void main(String args[])
{
Scanner in =new Scanner (System.in);
String s1=new String ();
s1="";
s1=in.next();
for(int i=0;i<s1.length()-2;i++)
{
if(s1.substring(i,i+3).compareTo("%20")==0)
{
s1=s1.substring(0,i)+s1.substring(i+3);
}
}
System.out.println(s1);
}
}
package com.shashi;
public class ChangingData {
public static void main(String []args)
{
String input="space%20com";
StringBuffer buff=new StringBuffer();
for(int i=0;i<input.length();i++)
{
if(input.charAt(i)=='%' && input.charAt(i+1)=='2' && input.charAt(i+2)=='0')
{
//do nothing
}
else if(input.charAt(i)=='2' && input.charAt(i+1)=='0')
{
//do nothing
}
else if(input.charAt(i)=='0')
{
buff.append(' ');
}
else
buff.append(input.charAt(i));
}
System.out.print(buff);
}
}
This is a fairly direct question, but you can really exhibit your skill by being thorough. This has a solution that is O(n) runtime and O(n) space. You can most likely do better on the space, but that will add some more complex code. Here's my solution with comments for explanation:
public static String replaceTwenty(String s){
//Create StringBuilder to utilize mutability (this is the O(n) extra space)
StringBuilder sb = new StringBuilder(s);
//Cycle through 1 char at a time - the length - 2 is a safety to prevent out of bounds error
for(int pos = 0; pos < sb.length()-2; pos++){
//Do char by char search to find leading indicator, then check for full %20 flag to replace
if(sb.charAt(pos) == '%' && sb.substring(pos, pos+3).equals("%20")){
sb .replace(pos, pos+3, " "); //Replace %20 with " "
}
}
return sb.toString();
}
Language: C++
Overview: Extract a token, append to new string, append space, and move on to next token until the end of the original string
Shortcomings: More memory is used because, firstly, we are copying to a new string instead of the original string. Secondly, we are keeping a temp local copy of the string in the 'reverse' function to avoid a modification of the original string by strtok.
#include <iostream>
#include <cstring>
#include <cstdlib>
void reverse (char * string, char * newstring) {
char * oldstring = new char (strlen(string));
strcpy (oldstring, string);
char * token = strtok (oldstring, "%20");
while (token !=NULL) {
strcat(newstring, token);
strcat(newstring," ");
token = strtok(NULL, "%20");
}
}
int main (int argc, char * * argv) {
char string [] = "This%20is%20a20%string";
int size = strlen (string);
//printf ("size:%u\n", size);
char * newstring = new char (size);
reverse (string, newstring);
printf ("Original string: %s\n", string);
printf ("New string: %s\n", newstring);
}
}
In java without using replace or scanners (which seems to be in the spirit of the question) and O(n):
public static String replaceSpace(String str){
final char[] smallArr = "%20".getChars();
final char[] largeArr = str.getChars();
StringBuilder builder = new StringBuilder();
for(int i = 0; i < largeArr.length; i++){
if(matches(i, largeArr, smallArr){
builder.append(' ');
i+=2;
}
else{
builder.append(largeArr[i]);
}
return builder.toString();
}
public static boolean matches(int pos, char[] largeArr, char[] smallArr){
if(largeArr.length - pos < smallArr.length){
return false;
}
int count = 0;
while(count < smallArr.length){
if(smallArr[count] != largeArr[pos + count]){
return false;
}
count++;
}
return true;
}
%20 is the hex value of space. When the string is encoded, space will be replaced with %20 and you can get the space back when you decode the string with %20
public void static main(String args[]){
String input="space%20com";
String decoded = URLDecoder.decode(input, "UTF-8");
System.out.println(decoded);
}
void string_replace(string &s, const string &src, const string &target) {
int sind = 0, dind = 0;
int slen = src.length();
int tlen = target.length();
int diff = slen - tlen;
int cnt = 0;
for (sind = 0, dind = 0; sind < s.length(); sind++, dind++) {
if (s.substr(sind, slen) == src) {
for (int j = 0; j < tlen; j++)
s[dind++] = target[j];
sind += slen;
cnt++;
}
if (sind != dind) {
s[dind] = s[sind];
}
}
s.resize(s.length() - (cnt * diff));
}
#include <iostream>
#include <string>
using namespace std;
int main()
{
cout<<"Enter String"<<endl;
string str, temp_str, rep_str=" ";
getline(cin, str);
int i=0;
while(i<str.length())
{
temp_str = str.substr(i,3);
if(temp_str=="%20")
{
swap(str[i], rep_str[0]);
str.erase(i+1,2);
}
i++;
}
cout<<str<<endl;
}
Why not to generate a new string applying replaceAll() ?
import java.util.Scanner;
public class replaceURL{
public static void main(String[] args){
Scanner user_input = new Scanner(System.in);
String url = new String();
url = user_input.next();
int indexOfSign = url.indexOf("%20");
if(indexOfSign !=-1){
String changeURL = url.replaceAll("%20"," ");
System.out.println(changeURL);
}
}
}
import java.util.LinkedList;
import java.util.List;
public class StringInterviewQuestion {
public static String replace(String original, String stringToReplace, String stringToReplaceWith) {
if(
null == original ||
null == stringToReplace ||
stringToReplace.isEmpty() ||
null == stringToReplaceWith ||
(stringToReplace.length() > original.length())
)
return original;
int index = original.indexOf(stringToReplace);
if(index == -1)
return original;
char[] replaceCharArray = stringToReplace.toCharArray();
char[] newCharArray = stringToReplaceWith.toCharArray();
List<Character> givenList = convertToList(original);
int j = original.length() - stringToReplace.length() + 1;
for(int i=0; i< j; i++) {
if(givenList.get(i) == replaceCharArray[0]) {
int tempi = i;
boolean found = true;
for(int a = 0; a<replaceCharArray.length; a++) {
if(replaceCharArray[a] != givenList.get(tempi)) {
found = false;
break;
}
tempi++;
}
if(found) {
tempi = i;
for(int a = 0; a<replaceCharArray.length; a++) {
givenList.remove(tempi);
}
for(int a = 0; a<newCharArray.length; a++) {
givenList.add(tempi, newCharArray[a]);
tempi++;
}
}
i = tempi;
}
}
return convertToString(givenList);
}
public static List<Character> convertToList(String given) {
if(null == given || given.isEmpty())
return null;
List<Character> list = new LinkedList<Character>();
char[] cArray = given.toCharArray();
for(int i=0; i<cArray.length; i++) {
list.add(cArray[i]);
}
return list;
}
public static String convertToString(List<Character> list) {
if(null == list || list.isEmpty())
return null;
StringBuilder sb = new StringBuilder("");
for(int i=0; i<list.size(); i++) {
sb.append(list.get(i));
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(replace("space%20.com", "%20", " "));
System.out.println(replace("space%20.com", "%20", "this"));
}
}
public class StringUtil {
enum CharMatchingState {
YES,
NO
}
public static void replace(char[] original, char[] stringToReplace, char[] stringToReplaceWith) {
if ((original.length == 0) || (stringToReplace.length == 0) || stringToReplaceWith.length == 0) {
return;
} else if ((stringToReplace.length > original.length)) {
return;
} else if ((stringToReplaceWith.length > stringToReplace.length)) {
System.out.println("In place replacement does not allow this");
return;
}
CharMatchingState state = CharMatchingState.NO;
int j = 0;
int k = 0;
for (int i = 0; i < original.length; ++i) {
if (state == CharMatchingState.NO) {
if (original[i] != stringToReplace[j]) {
original[k++] = original[i];
} else {
j++;
if (j == stringToReplace.length) {
for (int t = 0; t < stringToReplace.length; ++t) {
original[k++] = stringToReplaceWith[t];
}
j = 0;
state = CharMatchingState.NO;
}
state = CharMatchingState.YES;
}
} else if (state == CharMatchingState.YES) {
if (original[i] != stringToReplace[j]) {
for (int t = 0; t < j; ++t) {
original[k++] = stringToReplace[t];
}
j = 0;
state = CharMatchingState.NO;
} else {
j++;
if (j == stringToReplace.length) {
for (int t = 0; t < stringToReplace.length; ++t) {
original[k++] = stringToReplaceWith[t];
}
j = 0;
state = CharMatchingState.NO;
}
}
}
}
while(k < original.length) {
original[k++] = ' ';
}
}
public static void main(String[] args) {
char[] original = "wwwspace%20com".toCharArray();
StringUtil.replace(original, "%20".toCharArray(), "xxx".toCharArray());
System.out.println("Result: " + new String(original));
}
}
Solution using C# String Builder and time complexity = O(n)
public void ReplaceString(string str1)
{
if (str1.Length <= 0)
{
Console.WriteLine("string is null");
return;
}
StringBuilder strbuilder = new StringBuilder();
for (int i = 0; i < str1.Length; i++ )
{
if (str1[i] != '%')
{
strbuilder.Append(str1[i]);
}
else if (str1[i] == '%' && str1[i + 1] == '2' && str1[i + 2] == '0')
{
i = i + 2;
strbuilder.Append(" ");
}
else
{
strbuilder.Append(str1[i]);
}
}
Console.WriteLine(strbuilder.ToString());
}
Python Solution
# Approach 1: using built in replace
def replaceSpaces(mystring):
return mystring.replace(" ", '%20')
# Approach 2: using built in split and join - which is faster than replace
# Fails to address if there is a space at the end of the string.
def replaceSpaces(mystring):
return "%20".join(mystring.split())
# Approach 3: using append TC: SC: ?
def replaceSpaces(mystring):
charlist = []
for i in mystring:
if i == ' ':
i = '%20'
charlist.append(i)
return ''.join(charlist)
Use right tools!
- ninhnnsoc October 17, 2014