Google Interview Question for Software Analysts


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

#Write a program which will bold the sub-string found in string (HTML Style).
inputstr = 'HelloWorld HelloWorld'
substrlist = ['el', 'rl']
replacestring = '<b>{0}</b>'
newstring = "H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d"

def boldsubstring(string):
    for sub in substrlist:
        if sub in string:
            string = string.replace(sub, replacestring.format(sub))
    return string
#    while i < len(string):
#        tmpstr = string[i : i + 2]
#        if tmpstr in substrlist:
#            replaced = replacestring.format(tmpstr)
#            string = string.replace(tmpstr, replaced)
#        i += 1
#    return string

output = boldsubstring(inputstr)
print('HTML Style string:%s' % output)
assert output == newstring, 'Output must match to - %s' % (newstring)

- Joy January 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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")));
	}
}

- Jr January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}
}

- Nikhil January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}
}

- Nikhil January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}
}

- nikhil January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply we can use kmp algoritham with time complexity O(l*m) l-> time complexity of the longest string in the list and m is the length of the list

- SUMIT KESARWANI January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply we can use kmp algoritham with time complexity O(LM).

L -; Length of the longest string
M-; Length of the list

- sumit.polite January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- srterpe January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"))));
    }

}

- Pawan January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"))));
    }

}

- pawan January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"))));
    }

}

- pawan January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :)

- Mike L January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
  }
}

- obed.tandadjaja January 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

- Rizma March 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- Anonymous March 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re
arr = "hello world AAAAAABBBBBBBCCCCCChello"
sub = ['el', 'AA', 'BBB', 'BC']
for i in sub:
    arr = re.sub(i, '<b>' + i + '</b>', arr)
print arr

- rasmiranjanbabu March 27, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More