Google Interview Question
Software AnalystsCountry: United States
import java.util.Arrays;
import java.util.List;
public class Test {
public static String makeBold(String s, List<String> sub) {
for(String eachSub : sub) {
String[] parts = s.split(eachSub);
StringBuilder sb = new StringBuilder();
String insert = new StringBuilder("<b>").append(eachSub).append("</b>").toString();
for(int i = 0; i < parts.length ; i++) {
sb.append(parts[i]);
if(i < parts.length -1)
sb.append(insert);
}
s = sb.toString();
}
return s;
}
public static void main(String[] args) {
System.out.println(Test.makeBold("HelloWorld HelloWorld", Arrays.asList("el", "rl")));
}
}
class Program
{
static void Main(string[] args)
{
string s = "HelloWorld HelloWorld";
string[] substring = { "el", "rl" };
Program nik = new Program();
StringBuilder nikhik = nik.bold(s, substring);
Console.WriteLine(nikhik);
Console.ReadLine();
}
public StringBuilder bold(string s, string[] sub)
{
List<int> indexes = new List<int>();
int index = 0;
int a = 0;
int b = 0;
int i = 0;
var builder = new StringBuilder();
while(i<=s.Length)
{
index = Convert.ToInt32(s.IndexOf(sub[0]));
if (index == -1)
{
builder = builder.Append(s);
break;
}
else
{
indexes.Add(index);
a = sub[0].Length;
b = sub[1].Length;
builder = builder.Append(s.Substring(i, index));
builder = builder.Append("<br>");
builder = builder.Append(sub[0]);
builder = builder.Append("</br>");
s = s.Substring(index + 2);
index = Convert.ToInt32(s.IndexOf(sub[1]));
builder = builder.Append(s.Substring(i, index));
builder = builder.Append("<br>");
builder = builder.Append(sub[1]);
builder = builder.Append("</br>");
s = s.Substring(index + 2);
// i = i + b;
s = s.Substring(i);
}
}
return builder;
}
}
class Program
{
static void Main(string[] args)
{
string s = "HelloWorld HelloWorld";
string[] substring = { "el", "rl" };
Program nik = new Program();
StringBuilder nikhik = nik.bold(s, substring);
Console.WriteLine(nikhik);
Console.ReadLine();
}
public StringBuilder bold(string s, string[] sub)
{
List<int> indexes = new List<int>();
int index = 0;
int a = 0;
int b = 0;
int i = 0;
var builder = new StringBuilder();
while(i<=s.Length)
{
index = Convert.ToInt32(s.IndexOf(sub[0]));
if (index == -1)
{
builder = builder.Append(s);
break;
}
else
{
indexes.Add(index);
a = sub[0].Length;
b = sub[1].Length;
builder = builder.Append(s.Substring(i, index));
builder = builder.Append("<br>");
builder = builder.Append(sub[0]);
builder = builder.Append("</br>");
s = s.Substring(index + 2);
index = Convert.ToInt32(s.IndexOf(sub[1]));
builder = builder.Append(s.Substring(i, index));
builder = builder.Append("<br>");
builder = builder.Append(sub[1]);
builder = builder.Append("</br>");
s = s.Substring(index + 2);
// i = i + b;
s = s.Substring(i);
}
}
return builder;
}
}
class Program
{
static void Main(string[] args)
{
string s = "HelloWorld HelloWorld";
string[] substring = { "el", "rl" };
Program nik = new Program();
StringBuilder nikhik = nik.bold(s, substring);
Console.WriteLine(nikhik);
Console.ReadLine();
}
public StringBuilder bold(string s, string[] sub)
{
List<int> indexes = new List<int>();
int index = 0;
int a = 0;
int b = 0;
int i = 0;
var builder = new StringBuilder();
while(i<=s.Length)
{
index = Convert.ToInt32(s.IndexOf(sub[0]));
if (index == -1)
{
builder = builder.Append(s);
break;
}
else
{
indexes.Add(index);
a = sub[0].Length;
b = sub[1].Length;
builder = builder.Append(s.Substring(i, index));
builder = builder.Append("<br>");
builder = builder.Append(sub[0]);
builder = builder.Append("</br>");
s = s.Substring(index + 2);
index = Convert.ToInt32(s.IndexOf(sub[1]));
builder = builder.Append(s.Substring(i, index));
builder = builder.Append("<br>");
builder = builder.Append(sub[1]);
builder = builder.Append("</br>");
s = s.Substring(index + 2);
// i = i + b;
s = s.Substring(i);
}
}
return builder;
}
}
Use a regular expression in `g` mode, also deal with the substring 'b'
module.exports = function (s, l) {
var tmp = []
for (var i = 0; i < l.length; ++i) {
if (l[i] === 'b') {
tmp.unshift('b')
} else {
tmp.push(l[i])
}
}
for (i = 0; i < tmp.length; ++i) {
s = s.replace(new RegExp(tmp[i], 'g'), '<b>$&</b>')
}
return s
}
var solution = module.exports('HelloWorld HelloWorld', ['el', 'b', 'rl'])
console.log(solution)
Solution using string buffer
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MakeSubstringBold {
public static String makeSubstringBold(String testString,List<String> substrlist){
StringBuffer buffer=new StringBuffer(testString);
for(int i=0;i<substrlist.size();i++){
int index=buffer.indexOf(substrlist.get(i));
buffer.insert(index,"<b>");
buffer.insert(index+3+substrlist.get(i).length(), "</b>");
}
return buffer.toString();
}
public static void main(String args[]){
System.out.println(makeSubstringBold("Hello World",new ArrayList<String>(Arrays.asList("el","rl"))));
}
}
Solution using string buffer
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MakeSubstringBold {
public static String makeSubstringBold(String testString,List<String> substrlist){
StringBuffer buffer=new StringBuffer(testString);
for(int i=0;i<substrlist.size();i++){
int index=buffer.indexOf(substrlist.get(i));
buffer.insert(index,"<b>");
buffer.insert(index+3+substrlist.get(i).length(), "</b>");
}
return buffer.toString();
}
public static void main(String args[]){
System.out.println(makeSubstringBold("Hello World",new ArrayList<String>(Arrays.asList("el","rl"))));
}
}
solution using string buffer
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MakeSubstringBold {
public static String makeSubstringBold(String testString,List<String> substrlist){
StringBuffer buffer=new StringBuffer(testString);
for(int i=0;i<substrlist.size();i++){
int index=buffer.indexOf(substrlist.get(i));
buffer.insert(index,"<b>");
buffer.insert(index+3+substrlist.get(i).length(), "</b>");
}
return buffer.toString();
}
public static void main(String args[]){
System.out.println(makeSubstringBold("Hello World",new ArrayList<String>(Arrays.asList("el","rl"))));
}
}
It is a very clever question.
From my point of view, it is not about the implementation itself, since it is pretty much easy to write such algorithm.
It is about design patterns, I faced similar challenge, and I thought: "Why those guys are asking me to solve such an easy challenge?" - after that I started thinking about how we can extend solution and so on - and it turned out that it is a question about how I can handle different design patterns.
So, regarding the challenge, from my point of view there are to cases here:
1. applying a tag -> Decorator pattern (How we can easily modify our solution to handle the '<i>' tag?)
2. list of substrings -> Strategy pattern (What will be in case if for different strings we would like to use different tags?)
And my solution is:
public class BoldTheSubstrings {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
String initialString = scanner.nextLine();
int amountOfSubstrings = scanner.nextInt();
HTMLTagStrategy strategy;
HTMLTag decorateWithBoldStyle = new SimpleHTMLTagImpl("b");
for (int i = 0; i < amountOfSubstrings; i++) {
strategy = new SimpleHTMLTagStrategyImpl(scanner.next());
initialString = strategy.applyTagToSubstring(decorateWithBoldStyle, initialString);
}
System.out.println(initialString);
}
}
}
/**
* Definition of the Decorator pattern
*/
// Interface
interface HTMLTag {
String applyTag(String string);
}
// Implementation
class SimpleHTMLTagImpl implements HTMLTag {
private String tagName;
public SimpleHTMLTagImpl(String tagName) {
this.tagName = tagName;
}
@Override
public String applyTag(String string) {
return "<" + tagName + ">" + string + "</" + tagName + ">";
}
}
/**
* Definition of the Strategy pattern
*/
// Interface
interface HTMLTagStrategy {
String applyTagToSubstring(HTMLTag decorator, String theString);
}
// Implementation
class SimpleHTMLTagStrategyImpl implements HTMLTagStrategy {
private String substring;
public SimpleHTMLTagStrategyImpl(String substring) {
this.substring = substring;
}
@Override
public String applyTagToSubstring(HTMLTag decorator, String theString) {
StringBuilder resultOutput = new StringBuilder();
String[] splitParts = theString.split(substring);
resultOutput.append(splitParts[0]);
for (int i = 1; i < splitParts.length; i++) {
resultOutput.append(decorator.applyTag(substring)).append(splitParts[i]);
}
return resultOutput.toString();
}
}
Input:
HelloWorld HelloWorld
2
el
rl
Output:
H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d
Please correct me if I am wrong with such approach :)
I think the other answers missed the hardest part of this problem which is to make sure that overlap between two or more substrings will be under the same bold tag.
For example:
String = "HelloWorld HelloWorld"
Substrings = {"el", "llo", "rl"}
Output = "H<b>ello</b>Wo<b>rl</b>d H<b>ello</b>Wo<b>rl</b>d"
Another example:
String = "HelloWorld HelloWorld";
Substrings = {"He", "el", "llo", "oW", "Wor", "rl", "ld"};
Output = "<b>HelloWorld</b> <b>HelloWorld</b>"
import java.util.*;
public class BoldSubstring {
public static void main(String[] args) {
String s = "HelloWorld HelloWorld";
String[] substrings = {"el", "llo", "rl"};
System.out.println(boldenSubstring(s, substrings));
}
public static String boldenSubstring(String s, String[] substrings) {
boolean currentBold = false;
StringBuilder sb = new StringBuilder();
int currentBoldLength = 0;
for(int i = 0; i < s.length(); i++) {
String currentString = s.substring(i);
boolean hasSubstring = false;
for(int j = 0; j < substrings.length; j++) {
if(currentString.indexOf(substrings[j]) == 0) {
if(!currentBold) {
currentBold = true;
sb.append("<b>");
}
currentBoldLength = Math.max(currentBoldLength, substrings[j].length());
}
}
sb.append(s.charAt(i));
if(hasSubstring == false && currentBoldLength == 1) {
if(currentBold) {
currentBold = false;
sb.append("</b>");
}
}
if(currentBoldLength > 0) currentBoldLength--;
}
return sb.toString();
}
}
public class boldWordsInaString {
public static void getHTMLresponse(String str, String[] substringList){
for(int i=0;i<substringList.length;i++){
if(str.contains(substringList[i])){
str = str.replace(substringList[i], "<b>" + substringList[i] + "</b>");
int index = str.indexOf(substringList[i]);
}
}
System.out.println(str);
}
public static void main(String[] args) {
String str = "rlHelloWorld HelloWorldel";
String[] substringList = {"el", "rl"};
getHTMLresponse(str, substringList);
}
}
public class boldWordsInaString {
public static void getHTMLresponse(String str, String[] substringList){
for(int i=0;i<substringList.length;i++){
if(str.contains(substringList[i])){
str = str.replace(substringList[i], "<b>" + substringList[i] + "</b>");
int index = str.indexOf(substringList[i]);
}
}
System.out.println(str);
}
public static void main(String[] args) {
String str = "rlHelloWorld HelloWorldel";
String[] substringList = {"el", "rl"};
getHTMLresponse(str, substringList);
}
}
- Joy January 27, 2017