Interview Q&A - Write a C# console application to implement a string replacement function

Requirements

Given three strings: input, oldValue and newValue. Look for oldValue in input and replace it with newValue.

Signature:

Replace(string input, string oldValue, string newValue);

For example:

Replace("hello, world", "world", "galaxy") should return "hello, galaxy".

Important Note

1. You cannot use built-in string replacement methods such as string.Replace, StringBuilder.Replace, Regex.Replace, etc.

2. You cannot use built-in string search method such as SubString, IndexOf. It is recommended to implement your own SubString, IndexOf methods.

3. C# string is an immutable object. You might want to use char array or StringBuilder to do string manipulations. However, if you use StringBuilder, you can not use StringBuilder‘s built-in methods to do string replacements and searching (Replace, SubString, IndexOf, Append, Insert, Delete, etc. are not allowed).

using System;
using System.Collections.Generic;
using System.Text;

namespace StringReplacement
{
    static class Program
    {
        static void Main()
        {
            string s = Replace("Today arare arein what aarae Monday!", "are", "is");
            Console.WriteLine(s);
        }

        /// <summary>
        /// Given three strings: input, oldValue and newValue. Look for oldValue in input and replace it with newValue.
        /// </summary>
        /// <param name="input">input string</param>
        /// <param name="oldValue">old value</param>
        /// <param name="newValue">new value</param>
        /// <returns>The replaced string.</returns>
        static string Replace(string input, string oldValue, string newValue)
        {
            StringBuilder strBuilder = new StringBuilder();
            int inputLen = input.Length;
            int oldValLen = oldValue.Length;
            int newValLen = newValue.Length;
            List<int> posList = SubString(input, oldValue);

            // Found that input has old value, replace it with new value.
            if (posList.Count > 0)
            {
                for (int i = 0; i < inputLen; )
                {
                    if (posList.Contains(i))
                    {
                        for (int j = 0; j < newValLen; j++)
                        {
                            strBuilder.Append(newValue[j]);
                        }

                        i += oldValLen;
                    }
                    else
                    {
                        strBuilder.Append(input[i]);
                        i++;
                    }
                }
            }

            return strBuilder.ToString();
        }

        /// <summary>
        /// To determine if subStr is sub string of str or not. If it is, add the sub string start position to the return list; null otherwise.
        /// </summary>
        /// <param name="str">string</param>
        /// <param name="subStr">sub string</param>
        /// <returns>The return list which contains the start positions of sub string.</returns>
        static List<int> SubString(string str, string subStr)
        {
            List<int> list = new List<int>();
            int strLen = str.Length;
            int subStrLen = subStr.Length;
            int i = 0;
            int j = 0;
            while (i < strLen)
            {
                if (j >= subStrLen)
                {
                    list.Add(i - subStrLen);
                    j = 0;
                }

                if (str[i].Equals(subStr[j]))
                {
                    i++;
                    j++;
                    continue;
                }

                j = 0;
                if (!str[i].Equals(subStr[j]))
                {
                    i++;
                }
            }

            return list;
        }
    }
}