Microsoft Interview Question for Developer Program Engineers


Team: teamviewer
Country: India
Interview Type: In-Person




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- zahidbuet106 June 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

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

- zahidbuet106 June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- zprogd July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Saubhik Maiti August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think if we directly replace the occurrences, then we have to move the characters several times, so it is better to know which chars will be in final output and then append them.

- yuhuiming June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am unable to figure the challenge in this. In which round was this question asked and for what position? Were there constraints? We can do it easily using std::string or java string or link list.

- Sugarcane_farmer June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- gzyeli123 June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Scott June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

        }

- AdityaAstrik July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Colin July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rajan_Parmar August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Duduman Bogdan Vlad December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sai ram kolasani July 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Vezita June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Vezita- you can count the number of occurrences within StringReplace only right

- veena June 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@veena - working quite well in my machine.

- Vezita June 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry I hadn't logged in when I posted the ans.

- Veena June 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- New June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous June 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

consider to solve this problem by not using any standard library such as string.find ..

- zahidbuet106 June 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Max September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Update do not use that -1 in 5th to last line, thats a small error

- Max September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What's your algorithm's complexity? Other solutions are trying to do it in O(N), where N is the length of the original string. But yours is O(N^2). I think this is the interviewer's point.

- anonymous December 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

- Murali Mohan June 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

# 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')

- vsvicky June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- Vitali (Germany) June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.


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