Microsoft Interview Question
Developer Program EngineersTeam: teamviewer
Country: India
Interview Type: In-Person
So, we will use the KMP algorithm to find all the occurrences of the second string (pattern) in the first string (text) in O(n). Save these positions into an array of integers (lets say positionArray). We will use a StringBuilder to construct the replaced string. Also We need to keep a pointer to the first index of the position array (lets say positionPointer).
Scan the text from left to right and append the character in current position into the string builder except for the position where the positionPointer is currently pointing to in the positionArray, in which case we append the given string (replace string) in the string builder and skip the whole pattern in the text from current scan position.
Once we've replaced the string we need to increment the positionPointer to skip the overlapping pattern positions (research this example: text="aaaaaa", pattern = "aa", replaceWith = "X"). We can do it by aligning the positionPointer with the scan index.
The overall operation is O(n) time and O(n) space. Below is a pseudocode assuming that one can easily implement standard KMP from internet sources.
public String replace(final String text, final String pattern, final String replaceWith) {
if (text.equals(pattern)) {
return replaceWith;
}
if (pattern == null || pattern.isEmpty() || replaceWith == null || replaceWith.isEmpty()) {
return text;
}
final int[] substringPositions = KMPSearch(text, pattern);
int positionPointer = 0;
final StringBuilder replacedString = new StringBuilder();
final char[] textChars = text.toCharArray();
for (int i = 0; i < textChars.length; i++) {
while (positionPointer < substringPositions.length && i > substringPositions[positionPointer]) {
positionPointer++;
}
if (positionPointer < substringPositions.length && i == substringPositions[positionPointer]) {
replacedString.append(replaceWith);
i += pattern.length() - 1;
} else {
replacedString.append(textChars[i]);
}
}
return replacedString.toString();
}
So, we will use the KMP algorithm to find all the occurrences of the second string (pattern) in the first string (text) in O(n). Save these positions into an array of integers (lets say positionArray). We will use a StringBuilder to construct the replaced string. Also We need to keep a pointer to the first index of the position array (lets say positionPointer).
Scan the text from left to right and append the character in current position into the string builder except for the position where the positionPointer is currently pointing to in the positionArray, in which case we append the given string (replace string) in the string builder and skip the whole pattern in the text from current scan position.
Once we've replaced the string we need to increment the positionPointer to skip the overlapping pattern positions (research this example: text="aaaaaa", pattern = "aa", replaceWith = "X"). We can do it by aligning the positionPointer with the scan index.
The overall operation is O(n) time and O(n) space. Below is a pseudocode assuming that one can easily implement standard KMP from internet sources.
public String replace(final String text, final String pattern, final String replaceWith) {
if (text.equals(pattern)) {
return replaceWith;
}
if (pattern == null || pattern.isEmpty() || replaceWith == null || replaceWith.isEmpty()) {
return text;
}
final int[] substringPositions = KMPSearch(text, pattern);
int positionPointer = 0;
final StringBuilder replacedString = new StringBuilder();
final char[] textChars = text.toCharArray();
for (int i = 0; i < textChars.length; i++) {
while (positionPointer < substringPositions.length && i > substringPositions[positionPointer]) {
positionPointer++;
}
if (positionPointer < substringPositions.length && i == substringPositions[positionPointer]) {
replacedString.append(replaceWith);
i += pattern.length() - 1;
} else {
replacedString.append(textChars[i]);
}
}
return replacedString.toString();
}
void replace(const char* src, const char* old_value, const char* new_value, char* dest) {
int i = 0;
int j = 0;
while (src[i]) {
if (src[i] == old_value[0]) {
int k = 1;
while (src[i+k] && old_value[k] && src[i+k]==old_value[k])
k++;
if (!old_value[k]) {
for (int m=0; new_value[m]; m++)
dest[j++] = new_value[m];
i += k;
continue;
}
}
dest[j++] = src[i++];
}
dest[j]=0;
}
private string GetOccuranceString_ReplaceByNewVal(string input, string occ, string newval)
{
string news = "";
MatchCollection matches = Regex.Matches(input, occ);
news = Regex.Replace(input, occ, newval);
// Console.WriteLine("How many occurance :# "+matches.Count);
// Console.WriteLine("\nNew String :# " + news);
return news;
}
If I am wrong please correct me.
I use KMP algorithm to match all the occurrences and replace them one by one.
public class test {
public static void main(String[] args) {
String thestring = "Microsoft";
String occur = "ic";
String replace = "MSFT";
int count = 0;
int i=0, m;
int length = thestring.length();
while(i<length)
{
length = thestring.length();
m=0;
if(thestring.charAt(i)!=occur.charAt(m))
{
i++;
}
else
{
int oldi = i;
while(thestring.charAt(oldi) == occur.charAt(m))
{
oldi++;
m++;
if(m>=occur.length()-1)
{
break;
}
}
if(m<occur.length()-1)
{
i = oldi+m+1;
}
else
{
count++;
thestring = thestring.substring(0, i) + replace + thestring.substring(i+occur.length());
i = oldi+occur.length();
}
}
}
System.out.println("The string: "+thestring);
System.out.println("replaces "+count+" occurrences.");
}
}
public String removeOneString (String text , String find , String r) {
Stack <Character> stack = new Stack<Character> ();
char [] chs = text.toCharArray() ;
char [] replace = r.toCharArray() ;
int count = 0 ;
StringBuilder sb = new StringBuilder ();
for (int i = 0 ; i < chs.length ; ++i) {
if (stack.isEmpty()) {
stack.push(chs[i]) ;
continue ;
}
sb.append(stack.peek()) ;
sb.append(chs[i]) ;
if (find.equals(sb.toString())) {
stack.pop() ;
count++;
} else {
int p = 0;
while (p < count) {
for (char c : replace ) {
stack.push(c) ;
}
p++;
}
count = 0 ;
stack.push(chs[i]) ;
}
sb.setLength(0) ;
}
while (!stack.isEmpty()) {
sb.append(stack.pop()) ;
}
return sb.reverse().toString() ;
}
public static string ReplaceString (string originalStr, string pattern, string replacementStr, out int numberOfocc)
{
string[] tokens = originalStr.ToLower().Split(new string[] { pattern.ToLower() }, StringSplitOptions.None);
numberOfocc = tokens.Length - 1;
StringBuilder temp = new StringBuilder();
for (int i = 0; i < tokens.Length;i++ )
{
temp.Append(tokens[i]);
if (i == tokens.Length - 1) break;
temp.Append(replacementStr);
}
return temp.ToString();
}
// Program to replace a substring from a string with user input
// ex. input: mydog
// string to_change: yd
// change_to: bob
// == mbobog
#include <iostream>
using namespace std;
int replaceStuff(string &word, const string &tmp, const string &change){
int countReplaces = 0;
string newstr = "";
bool test = false;
if (word.length() == 0) || (word.length() < tmp.length())
return 0;
for (int x = 0; x < word.size(); x++){
test = true;
if (word[x] == tmp[0] && word.length()-x >= tmp.length()){
for (int y = 1; y<tmp.size(); y++){
if (word[x+y] != tmp[y]){
test = false;
break;
}
}
if (test == true){
for (int t = 0; t<change.size(); t++){
newstr.push_back(change[t]);
}
x+=tmp.size();
countReplaces++;
}
}
newstr.push_back(word[x]);
}
word = newstr;
return countReplaces;
}
int main()
{
string test = "call me maybe";
string to_change = "ay";
string change_to = "bob";
cout << "Number of Changes made: " << replaceStuff(test,to_change,change_to) << endl;
cout << test << endl;
return 0;
}
#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<conio.h>
void main()
{
clrscr();
char str[20]="microsoft";
char occ[]="ic";
char repl[]="MSFT";
int m=0;
for(int i=0;i<strlen(str);i++)
{
if(str[i]!=occ[m])
{
m=0;
continue;
}
if(m==1)
{
int in;
in=i;
int len=strlen(repl)-strlen(occ);
for(int j=strlen(str)-1;j>in;j--)
{
str[j+len]=str[j];
}
--j;
for(int k=0;k<strlen(repl);k++)
{
str[j]=repl[k];
j++;
}
}
m++;
}
cout<<"\n"<<str;
getch();
}
String - "micrictaiact", replace string is "ic" with "02B" and result is "m02Br02Btaiact"
public void Start(string mainString, string subString, string newString)
{
if (mainString.Length == 0)
{
throw new ArgumentNullException();
}
if (mainString.Length < subString.Length)
{
throw new ArgumentNullException();
}
char[] chars = mainString.ToCharArray();
bool founded = true;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] == subString[0])
{
if (chars.Length - i < subString.Length)
{
break;
}
for (int j = 0; j < subString.Length; j++)
{
if (chars[i+j] != subString[j])
{
founded = false;
break;
}
}
if (founded)
{
for (int j = 0; j < newString.Length; j++)
{
sb.Append(newString[j]);
}
i = i + subString.Length - 1;
}
else
{
sb.Append(chars[i]);
}
} else{
sb.Append(chars[i]);
}
}
Console.WriteLine("New string from" + " " + mainString + " is " + sb.ToString());
}
string MainString = "Microsoft";
string occurString = "ic";
string replaceString = "MSFT";
int count =0;
//Gets the count of occurances
for(int i =0; i<MainString.Length - occurString.Length; i++)
{
if (MainString.Substring(i, occurString.Length) == occurString)
count++;
}
char [] mainArr = MainString.ToCharArray();
char [] occArr = occurString.ToCharArray();
StringBuilder sb = new StringBuilder();
for(int j =0; j< mainArr.Length; j++)
{
bool Append = false;
if(mainArr[j] == occArr[0])
{
for(int k =1; k<occArr.Length; k++)
{
if (mainArr[j + k] == occArr[k])
Append = true;
else
Append = false;
}
}
if (Append)
{
sb.Append(replaceString);
j = j + occArr.Length - 1;
}
else
sb.Append(mainArr[j]);
}
Console.WriteLine("Count :{0}", count.ToString());
Console.WriteLine("Count :{0}", sb.ToString());
Console.Read();
2 methods -
1st for replacing
2nd for counting the number of occurrence of substring
//to replace the string
//original = "Microsoft", substr = "ic" ,Replacement = "MSFT"
public static String StringReplace(String original, String substr, String Replacement)
{
String[] arr = original.split(substr);
StringBuilder output = new StringBuilder();
int i = 0;
for ( ; i < arr.length-1 ; i++)
output.append(arr[i]).append(Replacement);
output.append(arr[i]);
System.out.println(output);
if(original.substring(original.lastIndexOf(substr)).equalsIgnoreCase(substr))
output.append(Replacement);
System.out.println(""+output);
return output.toString();
}
//count the number of ocurrence of the replacement
public int NumOccurrence(String original, String substr)
{
int nOccurrence=0;
int n=0;
while(n <= original.length())
{
if ((original.indexOf(substr , n)) == -1)
break;
else
{
n= original.indexOf(substr,n);
nOccurrence++;
n++;
}
}
return nOccurrence;
}
}
Use pointers...In java since there are no pointer I am using substring method.
Logic: 'ic' is of length 2. so check is Mi== ic. Since it's not append M to Stringbuilder. Now increment the index by 1. Check ic == ic. Since it is, append stringbuilder with MSFT and increment index by length of ic instead of 1 now. Now is ro==ic. No so append r to String Builder. Now the loop breaks when u reach index 6. U need to do an extra check to see if the last two characters are equal to ic. If yes then replace it with MSFT else copy the contents of input string to string builder.
if(inputString.isEmpty() || replaceOccurence.isEmpty() || replaceWith.isEmpty())
return "String is Empty";
int noOfOccurence = 0;
StringBuilder result = new StringBuilder();
for(int index = 0 ; (index+replaceOccurence.length()) < inputString.length(); index++){
if(inputString.substring(index, index+replaceOccurence.length()).equals(replaceOccurence)){
result.append(replaceWith);
noOfOccurence++;
index += replaceOccurence.length()-1;
}
else
result.append(inputString.charAt(index));
}
if(inputString.substring(inputString.length()-replaceOccurence.length(), inputString.length()).equals(replaceOccurence)){
result.append(replaceWith);
noOfOccurence++;
}
else{
result.append(inputString.substring(inputString.length()-replaceOccurence.length(), inputString.length()));
}
System.out.println("Number of Occurence:"+noOfOccurence);
return result.toString();
}
public static String replace(String original,String oldst, String newst) {
if(original.equals(oldst))
return newst;
if(oldst.length() == 0)
return original;
String st = original;
String fi = "";
ArrayList<String> sa = new ArrayList<String>();
int carriage = oldst.length();
String terminal = null;
int index = 0;
//Split the String when the oldst is found
//Add the remaining to the list
for(int i=0;(i+carriage)<=st.length();i++){
if(st.substring(i, i+carriage).equals(oldst)){
if(st.substring(index,i) !=null )
sa.add(st.substring(index,i));
index=i+carriage;
terminal = st.substring(index, st.length());
}
}
//Construt the string with newst
for(int j=0;j<(sa.size());j++){
fi =fi+ sa.get(j)+newst;
}
//addition if anything left after splitting
fi = fi+terminal;
return fi;
}
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str= "ICMICROSOFT";
string pat= "IC";
int pos= str.find(pat);
while(pos==0)
{
str= str.substr(pat.length());
pos= str.find(pat);
}
while(pos > 0)
{
string str1= str.substr(0, pos);
cout << str1 << " ";
string str2= str.substr(pos + pat.length());
cout << str2 << " ";
str= str1+"MSFT"+str2;
pos= str2.find(pat);
cout << str << " \n";
}
cout << str << "\n";
}
void stringReplace(string *str, string pattern, string replacement)
{
/*
string myString = "My name is 1234. your name is 3464";
string pattern= "name";
string replacement = "number";
*/
int pos = str->find(pattern);
int patlen = pattern.length();
while (pos != string::npos)
{
string str1 = str->substr(0,pos); // first half od string
string str2 = str->substr(pos+patlen); // second half od string
*str = str1 + replacement +str2;
pos = str->find(pattern);
}
}
All of these other answers are stupid they are long and complex, listen to mine
public String replace(String ori, String getOut, String addIn) {
if(ori == null || getOut == null || ori.length() == 0 || getOut.length() == 0
|| addIn == null || addIn.length() == 0 )
throw new RuntimeException();
while (ori.contains(getOut)) {
int index = ori.indexOf(getOut);
StringBuffer sb = new StringBuffer();
sb.append(ori.substring(0,index));
sb.append(addIn);
sb.append(ori.substring(index + getOut.length() - 1 ));
ori = sb.toString();
}
return ori;
}
In the forward pass count the number of 'ic's in the string. Let the count be n. In the backward pass, start at 2*n places beyond the end of the string and keep copying the characters until (ic) is encountered. (ofcourse a look-ahead of 1 character is needed in the scan to capture 'ic'). Once ic is encountered, replace it with MSFT and continue till the beginning of the array.
# this code works for all generalized examples
# s1 is the original string; substring='ic'; replaceWith='MSFT'
def replaceString(s1,substring,replaceWith):
s2=''
l=len(s1)
count=0
i=0
while i<l:
if i!=l-1 && substringCompare(s1,substring,i):
s2=s2+replaceWith
count+=1
i=i+1
else:
s2=s2+s1[i]
i+=1
print s2,count
def substringCompare(s1,substring,i):
if i==len(s1)-1:
return 0
for j in range(i,i+len(substring)):
if s1[j]!=substring[j-i]:
return 0
return 1
replaceString('microsoft,'ic','MSFT')
replaceString('microsoftic,'ic','MSFT')
replaceString('icici','ic','MSFT')
Recursion based solution, I hope it helps.
public static void main(String[] args) {
char[] inputText = "Microsoft".toCharArray();
char[] replaceToken = "MSFT".toCharArray();
char[] replaceWord = "ic".toCharArray();
replaceOccurences(inputText, replaceToken, replaceWord);
}
private static void replaceOccurences(char[] inputText, char[] replaceToken, char[] replaceWord) {
StringBuilder outputWord = new StringBuilder();
for (int i = 0; i<inputText.length;i++) {
//Check if other chars do match, if not process with the next
if (replaceTokenIfMatches(inputText, replaceToken, replaceWord, i, 0, outputWord)) {
i += replaceWord.length;
} else {
outputWord.append(inputText[i]);
}
}
System.out.println(outputWord.toString());
}
private static boolean replaceTokenIfMatches(char[] inputText,
char[] replaceToken, char[] replaceWord, int startInputText, int startToken, StringBuilder outputWord) {
if (startToken>=replaceWord.length) {
//Reached the end, append token to the word
outputWord.append(replaceToken);
return true;
}
if (startInputText<inputText.length && inputText[startInputText]==replaceWord[startToken]) {
return replaceTokenIfMatches(inputText, replaceToken, replaceWord, startInputText+1,
startToken+1, outputWord);
}
return false;
}
With KMP algorithm find all occurrences of a particular string in a string and then replace those occurrences with the given string.
- vgeek June 09, 2014