4
\$\begingroup\$

Problem Statement:

Implement a sentence scanning functionality to parse the sentence and return a string to concatenate each word with its number of occurrences, sorted by the number of occurrences in descending order.

For example, with the sentence "code review connects the world! share the code" , the function returns the string: {code: 2, the: 2, review: 1, connects: 1, world: 1, share: 1}. The delimiters are customized as function input argument, for the above test case, the delimiters are " ,!".

Introduction of algorithm

I spent over an hour to write the algorithm first with time complexity \$O(nm)\$, where \$n\$ is the sentence's length and \$m\$ is delimiters length. I practiced using C#, tried to write a string.Split(string) by myself, and also learn to write LINQ for correct syntax by looking up the stackoverflow question to make the code more succinct.

I am still learning to write readable and clean code. The code passes two test case function calls in the main function. Please help me to improve.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

class ScanArticle
{
    static void Main(string[] args)
    {       
        RunTestcaseOnSplit();
        RunTestcase();
    }

    public static void RunTestcase()
    {
        var result = WordCountPractice(" code review connects the world! share the code", " ,?!");
        Debug.Assert(result.CompareTo("{code: 2, the: 2, review: 1, connects: 1, world: 1, share: 1}") == 0);
    }

    /// <summary>
    /// test do it yourself string.Split(string)
    /// Test case: " a,b,c", splitted words: new string[]{"a","b","c"}
    /// Test case: " a,b,c,", splitted words: new string[]{"a","b","c"} 
    /// </summary>
    public static void RunTestcaseOnSplit()
    {
        var words = stringSplitDoItYourSelf("  a,b,c", " ,");
        Debug.Assert(words[0].CompareTo("a") == 0);

        var words2 = stringSplitDoItYourSelf("  a,b,c,", " ,");
        Debug.Assert(words[2].CompareTo("c") == 0);
    }


    /// <summary>    
    /// words: " code review connects the world! share the code"
    /// the function returns the string: {code: 2, the: 2, review: 1, connects: 1, world: 1, share: 1}.
    /// Ignore punctuation and white-space. 
    /// 
    /// minimum run time O(N) + O(NM), N is words' length, and M is delimiters' length 
    /// </summary>
    /// <param name="words"></param>
    /// <param name="delimiters"></param>
    /// <returns></returns>
    public static string WordCountPractice(string words, string delimiters)
    {
        IList<string> sortedWords = new List<string>();

        if (words == null || words.Length == 0)
        {
            return string.Empty;
        }

        var split = stringSplitDoItYourSelf(words, delimiters);

        var original = new Dictionary<string, int>();

        foreach (var s in split)
        {
            if (original.ContainsKey(s))
            {
                original[s]++;
            }
            else
            {
                original.Add(s, 1);
            }
        }

        // time O(NlogN)      
        var sorted = from entry in original orderby entry.Value descending select entry;

        concatenateContent(sortedWords, sorted);         

        return string.Join("", sortedWords.ToArray());
    }

    /// <summary>
    /// wordCount: code, 2; the, 2
    /// the output: {code: 2, the: 2}
    /// </summary>
    /// <param name="words"></param>
    /// <param name="wordCount"></param>
    private static void concatenateContent(IList<string> words, IEnumerable<KeyValuePair<string, int>> wordCount)
    {
        const string openParenthese = "{";
        const string closeParenthese = "}";
        const string colon = ": ";
        const string comma = ", ";

        words.Add(openParenthese);

        int length = wordCount.Count();
        int index = 0;

        foreach (var item in wordCount)
        {
            StringBuilder current = new StringBuilder();

            current.Append(item.Key + colon + item.Value);

            if (index < length - 1)
            {
                current.Append(comma);
            }

            words.Add(current.ToString());

            index++;
        }

        words.Add(closeParenthese);
    }

    /// <summary>
    /// delimter =" ;-/"
    /// delimiter string length is m
    /// n is string s's length
    /// algorithm time complexity is O(nm) 
    /// 
    /// Do it yourself version of string.Split(char[])
    /// </summary>
    /// <param name="sentence"></param>
    /// <param name="delimiters"></param>
    /// <returns></returns>
    private static string[] stringSplitDoItYourSelf(string sentence, string delimiters)
    {
        IList<string> words = new List<string>();

        if (sentence == null || sentence.Length == 0)
        {
            return new string[0];
        }

        int length = sentence.Length;
        int start = 0;
        int end = 0;

        for (int i = 0; i < length; i++)
        {
            var current = sentence[i];

            var startChar = sentence[start];

            // continue to skip delimiter char if need
            if (delimiters.IndexOf(startChar) >= 0)
            {
                start = i;
                if (end < start)
                {
                    end = start;
                }
            }

            if (delimiters.IndexOf(current) >= 0)
            {
                end = i;

                // output the word, s[end] is delimiter 
                if (end - start > 0)
                {
                    words.Add(sentence.Substring(start, end - start));               
                    start = end + 1;
                }
            }
        }

        // edge case
        if (start < length && delimiters.IndexOf(sentence[start]) < 0)
        {
            words.Add(sentence.Substring(start, length - start));
        }

        return words.ToArray();
    }
}
\$\endgroup\$
7
\$\begingroup\$

There is not much LINQ in your code and this is a really long solution for such a simple task but let's try to change it.

You want to split a sentence like this one:

var sentence = " code review connects the world! share the code";

so why not use regex for this and split on every occurance of ,?!.. You then trim each word and filter the empty results out. Then you group each word igrnoring its case, sort the groups by count in a descending order and create strings.

var words = 
    Regex.Split(sentence, "[ ,?!.]")
    .Select(x => x.Trim())
    .Where(x => !string.IsNullOrEmpty(x))
    .GroupBy(x => x, StringComparer.OrdinalIgnoreCase)
    .OrderByDescending(g => g.Count());

var summary = $"{{{string.Join(", ", words.Select(g => $"{g.Key}: {g.Count()}"))}}}";

result

{code: 2, the: 2, review: 1, connects: 1, world: 1, share: 1}

Review

private static void concatenateContent(IList<string> words, IEnumerable<KeyValuePair<string, int>> wordCount)
{
    const string openParenthese = "{";
    const string closeParenthese = "}";
    const string colon = ": ";
    const string comma = ", ";

    words.Add(openParenthese);

    int length = wordCount.Count();
    int index = 0;

    foreach (var item in wordCount)
    {
        StringBuilder current = new StringBuilder();

        current.Append(item.Key + colon + item.Value);

        if (index < length - 1)
        {
            current.Append(comma);
        }

        words.Add(current.ToString());

        index++;
    }

    words.Add(closeParenthese);
}

You should not return a result via a parameter that is not a ref or out one because I'd be really shocked if you modified my list without giving me any hint that it will happen.

The IList<string> words should be a return value not a parameter.

Using the StringBuilder current = new StringBuilder(); inside a loop does not make much sense and you use the + concatenation anyway item.Key + colon + item.Value. You might as well concatenate the string in the normal way because the comptiler will optimize it. The StringBuilder will become useful when you define it outside the loop and then build the string.

You don't need the index++; because you can just check the words.Count property.

Ideally this method could look like this:

private static string concatenateContent(IEnumerable<KeyValuePair<string, int>> wordCount)
{
    const string openParenthese = "{";
    const string closeParenthese = "}";
    const string colon = ": ";
    const string comma = ", ";

    var result = new StringBuilder();
    result.Append(openParenthese);

    foreach (var x in wordCount.Select((item, index) => new { item, index }))
    {
        result
            .Append(x.index > 0 ? colon : string.Empty)
            .Append(x.item.Key)
            .Append(colon)
            .Append(x.item.Value);
    }

    result.Append(closeParenthese);

    return result.ToString();
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. What will happen when you wan't the delimiter to contain a character that is reserved in a regular expression, fx. "^ ,!"? input.Split(delimiters.ToCharArray(), StringSplitOptions.RemoveEmptyEntries) is simple and less error prone. \$\endgroup\$ – Johnbot Apr 4 '17 at 11:58
  • 2
    \$\begingroup\$ @Johnbot regex is there to be used and if I know how to use it why shouldn't I? What will happen when you wan't the delimiter to contain a character that is reserved in a regular expression, fx. "^ ,!"? well, you escape it or you put it inside [] that treat everything as literals [Positive Character Group: [ ]](msdn.microsoft.com/en-us/library/… Character Group: [ ]) and if you don't know what ^ or [] or . mean then yes, you have a problem. \$\endgroup\$ – t3chb0t Apr 4 '17 at 12:36
  • 1
    \$\begingroup\$ @Johnbot I could say the same about generics, linq, databases, registry and everything else what is scarry to someone who doesn't know how to use it. It's the same nonsense as if I said what if I made all parameters ref or out or made all methods static :-| \$\endgroup\$ – t3chb0t Apr 4 '17 at 12:37
  • 1
    \$\begingroup\$ My point was that just slapping the delimiters in a character group is not enough. If delimiters is "^ ,!" then "[" + delimiters + "]" won't work. "[" + Regex.Escape(delimiters) + "]" won't work either. \$\endgroup\$ – Johnbot Apr 4 '17 at 12:47
  • 1
    \$\begingroup\$ @JianminChen it would be this page and all extensions are listed here. Oops, you're right, there should be the comma inside the loop ;-] \$\endgroup\$ – t3chb0t Apr 5 '17 at 4:12
4
\$\begingroup\$
public static void RunTestcase()
{
    var result = WordCountPractice(" code review connects the world! share the code", " ,?!");
    Debug.Assert(result.CompareTo("{code: 2, the: 2, review: 1, connects: 1, world: 1, share: 1}") == 0);
}

There are tests!!! +1000

I'm very excited to see you using tests, but do yourself a favor and learn to use a unit testing framework (MSTest is built into Visual Studio.) Some would say keeping the tests in the same class as the code gives the class 2 responsibilities.

\$\endgroup\$
  • \$\begingroup\$ @EhsanSajjad we usually quote OP's code to better distinguish it from the review. There's no need to remove the quote formatting. \$\endgroup\$ – t3chb0t Apr 4 '17 at 11:33
  • 1
    \$\begingroup\$ @rubberDuck, excellent review. Next time I post the question, test case will be written using Microsoft unit testing framework. I did find that it is very easy to setup. \$\endgroup\$ – Jianmin Chen Apr 5 '17 at 2:33
  • 1
    \$\begingroup\$ Good luck on your journey @JianminChen. \$\endgroup\$ – RubberDuck Apr 5 '17 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.