Поделиться через


Interview question

Here’s a nice simple interview question:

In a given .NET string, assume there are line breaks in standard \r\n form (basically Environment.NewLine).

Write a method that inserts a space between two consecutive line breaks to separate any two line breaks from each other.

Also, anyone venture a guess what is a practical application for such a method?

Comments

  • Anonymous
    March 25, 2010
    string.Replace("rnrn", "rn rn");

  • Anonymous
    March 25, 2010
    Good one Robert, I like it, its simpler than mine. string insertSpaceBetweenLineBreaks(string input) {    return Regex.Replace(input, "(rn)(\1)", "$1 $2"); }

  • Anonymous
    March 25, 2010
    Beaten to it. I was thinking exactly the same as Robert.

  • Anonymous
    March 25, 2010
    I'm afraid it's not that easy. What about rnrnrn ? :)

  • Anonymous
    March 25, 2010
    As Ben mentionned, you need to take care of more than 2 consecutive breaks. I think it is necessary to iterate through the chars and create a new string as you go (which isn't an optimum solution): string text = "hello rnrnrn world!"; string textResult = ""; char[] caFromText = text.ToCharArray(); for (int i = 0; i < caFromText.Length; ++i) { textResult += caFromText[i]; if ((int)caFromText[i] == CARRIAGE_RETURN) {  // check if not reaching the end of the array  if (i + 3 < caFromText.Length)  {   if ((int)caFromText[i + 1] == NEW_LINE   && (int)caFromText[i + 2] == CARRIAGE_RETURN   && (int)caFromText[i + 3] == NEW_LINE)   {    // two consecutive breaks where detected    textResult += "n ";    // jump to the next break    ++i;   }  } } }

  • Anonymous
    March 25, 2010
    Hmmm, this version works via loop but I'd like to see a recursive version. This version uses a dash instead of space so its easy to see result. string insertSpaceBetweenLineBreaks(string input) {    while (Regex.Match(input, "(rn)(\1)").Success)    {        input = Regex.Replace(input, "(rn)(\1)", "$1-$1");    }    return input; } The test string I used was "ArnBrnrnCrnrnrnDrnrnrnrnE". This is the result A B

C

D

E

  • Anonymous
    March 25, 2010
    Recursive version, same result as previous while loop version. string insertSpaceBetweenLineBreaksRec(string input) {    if (!Regex.Match(input, "(rn)(\1)").Success)    {        return input;    }    else    {        input = Regex.Replace(input, "(rn)(\1)", "$1-$1");        return insertSpaceBetweenLineBreaksRec(input);    } }

  • Anonymous
    March 25, 2010
    Ben is right, Robert's original way doesn't work. Longer solutions will work, yes, but what about performance? I'm still not happy :) Any other ideas?

  • Anonymous
    March 25, 2010
    BTW it is amazing how the comments reflect my own train of thought as I was solving it.

  • Anonymous
    March 25, 2010
    In terms of why you might want this - SMTP?

  • Anonymous
    March 25, 2010
    Jon - pretty close. Not SMTP, but another web protocol, yes. Thanks for not revealing the answer just yet ;)

  • Anonymous
    March 25, 2010
    Sorry, not protocol - I should say "markup language"

  • Anonymous
    March 25, 2010
    Slightly faster : public static string Method3(string input)        {            int startIndex = 0;            var sb = new StringBuilder(input.Length * 2);            while (true)            {                int index = input.IndexOf("rn", startIndex);                if (index == -1)                {                    break;                }                int length = index - startIndex;                sb.Append(input.Substring(startIndex, length));                if (length == 1)                {                    sb.Append("-");                }                startIndex = index + 1;            }            return sb.ToString();        } Not much of a difference though.

  • Anonymous
    March 25, 2010
    straigtforward solution let insertSpaces (s : string) =    let rec loop (i : int) acc =        let newIndex = s.IndexOf("rnrn", i)        if newIndex = -1 then acc + s.Substring(i)        else loop (newIndex + 2) (acc + s.Substring(i, newIndex - i) + "rn ")    loop 0 "" or let insertSpaces2 (s : string) =    let checkCrlf i =        if i < s.Length - 1 then s.[i] = 'r' && s.[i+1] = 'n'        else false    let rec loop i crlf (acc : System.Text.StringBuilder) =        if i >= s.Length then acc.ToString()        else            let found = checkCrlf i            match found, crlf with            | true, true -> loop i false (acc.Append(' '))            | true, false -> loop (i + 2) true (acc.Append("rn"))            | false, _ -> loop (i + 1) false (acc.Append(s.[i]))    loop 0 false (new System.Text.StringBuilder())

  • Anonymous
    March 25, 2010
    Here's my take at it :        public static string InsertSpacesBetweenLineBreaks(string s)        {            StringBuilder sb = new StringBuilder();            bool prevCrLf = false;            char prev = '�';            foreach (char c in s)            {                if (c == 'n' && prev == 'r')                {                    if (prevCrLf) sb.Append(' ');                    prevCrLf = true;                }                else if (c != 'r')                {                    prevCrLf = false;                }                sb.Append(c);                prev = c;            }            return sb.ToString();        }

  • Anonymous
    March 25, 2010
    Let's take the declarative route ;) . // 4.0 Join overload string.Join(Environment.NewLine, input.Split(new[] { Environment.NewLine }, StringSplitOptions.None).Select(s => s == "" ? " " : s)) Oh, who said it has to be C# anyway? input.Split([| Environment.NewLine |]. StringSplitOptions.None) |> Seq.map (function "" -> " " | s -> s) |> String.concat Environment.NewLine

  • Anonymous
    March 25, 2010
    Here's my F# solution let addSpaces (data:string) =    let addStateToList state list =        match state with        | 0 -> list        | 1 -> 'r'::list        | 2 -> 'n'::'r'::list        | 3 -> 'r'::'n'::'r'::list        | _ -> failwith "invalid"    let list,state=          data        |> Seq.fold ( fun (l,state) cur ->              match state,cur with            | 0,'r' -> (l,1)            | 1,'n' -> (l,2)            | 2,'r' -> (l,3)            | 3,'n' -> (' '::'n'::'r'::l,2)            | _ -> (cur :: (l |> addStateToList state), 0)) (List.empty,0)    let list = addStateToList state list    let arr = list |> List.rev |> Array.ofList    new System.String(arr)

  • Anonymous
    March 25, 2010
    I vote for Sebastian U, because:

  1. Efficient enough (if we make some assumptions).
  2. Takes a very small amount of time to read and comprehend.
  • Anonymous
    March 25, 2010
    What about string.Replace("nr", "n r");

  • Anonymous
    March 25, 2010
          private string Process(string str)        {            return                str                .Split(new string[] { Environment.NewLine }, StringSplitOptions.None)                .Select(x => x.Length == 0 ? " " : x)                .Aggregate((a, x) => a + Environment.NewLine + x);        }

  • Anonymous
    March 25, 2010
    var s = "SIGNLErnDOUBLErnrnTRIPLErnrnrnENDrn**********rn"; System.Diagnostics.Trace.Write( s ); var sa = s.Split( new string[] { Environment.NewLine }, System.StringSplitOptions.None ); s = string.Empty; foreach( string ss in sa )   s += ( ss == string.Empty ? " " : ss ) + Environment.NewLine; System.Diagnostics.Trace.Write( s );

  • Anonymous
    March 25, 2010
    ha-ha. banko placed same solution while I was testing mine! :)

  • Anonymous
    March 25, 2010
    string output = Regex.Replace(input, @"(rn)(?=rn)", "$1 ");

  • Anonymous
    March 26, 2010
    The comment has been removed

  • Anonymous
    March 26, 2010
    I'm surprised but seems like it's faster than the split/join method : public static string Method4(string input)        {            string result = input;            string tmp = string.Empty;            while (result.Length != tmp.Length)            {                tmp = result;                result = tmp.Replace("rnrn", "rn-rn");            }            return result;        } (but the fastest yet on my machine is Thomas Levesque's )

  • Anonymous
    March 26, 2010
    Whipped this up in about ten minutes.  Seems too simple compared to the other solutions presented. static String ReplaceNewlines(String s) {  String origNewlines = Environment.NewLine + Environment.NewLine;  String newNewlines = Environment.NewLine + "-" + Environment.NewLine;  int offset = Environment.NewLine.Length + 1;  int startIndex = 0;  int idx = s.IndexOf(origNewlines, startIndex);  while (idx >= 0)  {    s = s.Replace(origNewlines, newNewlines);    startIndex += offset;    idx = s.IndexOf(origNewlines, startIndex);  }  return s; }

  • Anonymous
    March 26, 2010
    The comment has been removed

  • Anonymous
    March 26, 2010
    The comment has been removed

  • Anonymous
    March 26, 2010
    Can't you simply run it twice? string.Replace("rnrn", "rn rn"); string.Replace("rnrn", "rn rn"); The first pass would leave a maximum of two consecutive rn sequences and the second pass would clear those up. Might not be the most efficient, but it's certainly easy to understand and read.

  • Anonymous
    March 26, 2010
    @SebastianU - that is some sweet declarative code, thanks!

  • Anonymous
    March 26, 2010
    My first version didn't work, but this will. Quite pragmatic, and probably also the fastest. test.Replace("rnrn", "rn rn").Replace("rnrn", "rn rn");

  • Anonymous
    March 26, 2010
    here's one: static string ReplaceNewlines (string str) { // check for null if (str == null) throw new ArgumentNullException("str"); int cch = str.Length; // simple boundary condition, helps later if (cch < 4) return str; // pre-allocate space StringBuilder sb = new StringBuilder(cch * 4 / 3 + 1); // handle boundary condtion later, instead of in loop cch -= 3; int ich = 0; while (ich < cch) { char ch = str [ich++]; sb.Append (ch); // check for double newlines, won't overflow if (ch == 'r' && str [ich] == 'n' && str [ich + 1] == 'r' && str [ich + 2] == 'n') { sb.Append ("n "); ich++; } } // copy the remaining characters sb.Append (str, ich, str.Length - ich); return sb.ToString(); }

  • Anonymous
    March 26, 2010
    oops, that should have been: // pre-allocate space StringBuilder sb = new StringBuilder(cch * 3 / 2 + 1);

  • Anonymous
    March 26, 2010
    The comment has been removed

  • Anonymous
    March 26, 2010
    My take: static string Transform(string s) {    var input = new StringReader(s);    var output = new StringBuilder();    string line = null;    while ((line = input.ReadLine()) != null)        output.AppendLine(line.Equals(string.Empty) ? " " : line);    return output.ToString(); }

  • Anonymous
    March 26, 2010
    I'm curious about your response to Tad Smith's solution, because it certainly seems to work. Starting with string s = "rnrnrnrn"; s.Replace("rnrn", "rn-rn"); // - for clarity gives: "rn-rnrn-rn" repeating the operation gives: "rn-rn-rn-rn" isn't that what's required?

  • Anonymous
    March 26, 2010
    Actually you're right, my bad, sorry. It works indeed! However it does twice as much work and twice as much allocations then text.Replace("nr", "n r")

  • Anonymous
    March 26, 2010
    text.Replace("nr", "n r") is very clever, and very efficient. You are making an assumption which wasn't stated in the original problem though: that the only time your string has the characters "nr" is when it's part of the sequence "rnrn". That's probably a reasonable assumption. If there was any doubt though, I'd probably err on the safe side - correctness must trump performance surely?

  • Anonymous
    March 26, 2010
    The problem is stated ambiguously, since "rn" is not the same as Environment.NewLine, which is platform dependent. Correctness should come first , optimization second. What if the source gets compiled under Mono and Environment.NewLine is suddenly "n" ?

  • Anonymous
    March 28, 2010
    Kirill - Just a suggestion: you may want to provide some unit tests.  Many of the answers given so far have subtle differences. The test should specify how the functionality should handle input like "rnr" or "rnn" (many of the answers would handle these differently). Note: I know this may go above and beyond an "interview question", but I think the conversation has long since passed that point.

  • Anonymous
    March 29, 2010
    I want to say this has something to do with a multi-part post? Those have some funky rules to them (had to write a method to create one once, was a pain since I had no one to ask questions to)

  • Anonymous
    March 29, 2010
    Bad performance, but elegant: while(str.Contains("rnrn"))   str = str.Replace("rnrn", "rn rn"); If it ends up being on a critical path and too slow, only then I'd try to optimize (loop and use StringBuilder to make a new string).

  • Anonymous
    March 29, 2010
    What should happens if there are not only complete "rn", but 'r' and 'n' alone, e.g. "ArBCDEnnFGrrH"?

  • Anonymous
    March 29, 2010
    What hasn't been mentioned yet is that some of these solutions (e.g. the ones using IndexOf) may end up in an infinite loop in the presence of weightless Unicode characters. "nXr".IndexOf("nr") will return 0 if X is a Unicode character that isn't present in the sorting weight table. See http://esmithy.net/2007/10/11/unicode-surprises/ for details. (However, the character used in that blog post was added to the weight tables in .NET 4) string.Replace does not use culture-aware comparisons, so the string will stay unchanged (as expected) and you've got an infinite loop. Solution: 95% of the time, you'll want to pass StringComparison.Ordinal to all string methods. Use CurrentCulture only if you really want culture-specific stuff to be relevant. Don't use InvariantCulture, ever (unless you really, really know what you are doing).

  • Anonymous
    March 30, 2010
    I've added all the implementations to a solution, with unit tests. I probably haven't thought of all the tests necessary, so if you have any more ideas, please let me know. I've also added simple benchmarking for the implementations which pass the unit tests. http://sites.google.com/site/rikkus/kirill-osenkov-s-interview-question

  • Anonymous
    March 30, 2010
    Rik - this is absolutely fantastic! Thanks so much for this!!

  • Anonymous
    April 06, 2010
    Wow - thanks Rik! Posted about this at: http://blog.jordanterrell.com/post/Never-Underestimate-A-Well-Written-Regular-Expression.aspx