ToString() and AddString() method without using .Net Collections

Question

I was asked to answer the following question before setting up a phone interview, but they said my code wasn't detailed enough.

Question:

Without using any of the .NET Collection or Linq libraries (i.e. without using List), implement a ListOfStrings object that contains a set of strings. This object has the following methods:
Add(string) - inserts a string to the end of the list ToString() - Returns the list as a comma separated string.

Example Usage:

ListOfStrings list = new ListOfStrings(); // set is empty
list.Add("abc"); // set is "abc"
list.Add("xyz"); // set is now "abc", "xyz"
list.Add("123"); // set is now abc", "xyz", "123"
list.ToString(); // Should return "abc,xyz,123"

Ideally, this code should be able to handle large numbers of items.

Answer:

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                ListOfStrings ls = new ListOfStrings();
                ls.Add("test1");
                ls.Add("test2");
                ls.Add("122");
                ls.Add("");
                ls.ToString();
                Console.WriteLine(ls.ToString());
            }
        }
    }

    public class ListOfStrings
    {
        private string ListOfString;

        public ListOfStrings()
        {
            ListOfString = null;
        }
        public string Add(string input)
        {
            if (input != string.Empty)
            {
                ListOfString = ListOfString == null ? input : ListOfString + "," + input;
            }
            return ListOfString;
        }        

        public string ToString()
        {
            return ListOfString;
        }
    }
}

Please let me know feedback on the code.

Answer 1

1. ListOfString = null; is useless, fields get initialized to default(T) which is null for reference types. So you can drop the constructor.

   For simple initializations you can use inline initializers. e.g.

   private string ListOfString = "";
   

2. You're hiding ToString() instead of overriding it.

3. You're ignoring empty input strings, the spec doesn't require that. Curiously you're not ignoring null input strings.

4. Using a string as accumulator leads to quadratic runtime since it has to create a new string which contains all current data for each append.

   Use StringBuilder.Append in Add instead. Don't return a string from Add, else you lose the performance advantage. Call stringBuilder.ToString() in your ToString operation. This has linear runtime.

5. You're returning null if no value has ever been added. I'd expect the empty string instead.

I don't know what they meant by calling your code "not detailed enough". You could add documentation for corner cases, possibly in the form of unit tests. For my observations 3 and 5 it's not clear if your code is behaving like you intended. Documentation and/or unit tests would have clarified your intent.

Answer 2

I don't have too much experience with C#, so just some notes about the algorithm/structure. (Maybe there are C#-related issues which I'm not aware of.)

At first I was expecting some array manipulation logic here with extending the array if it's full. They might be expected the same but your solution is quite cool, why would you complicate it? YAGNI and it's a really simple solution which could work. I have to say that I really like it. Maybe a few (selft-checking) unit tests would have helped you to get a better impression.

A few minor notes:

1. It was not a requirement to ignore empty strings.

2. Add could be void.

3. The first line seems unnecessary here:

   ls.ToString();
   Console.WriteLine(ls.ToString());
   

Answer 3

Well... I think you answered the question as simple as possible. If this was a jobinterview, and you did not get the job, you should think "Hooray" - that company does not accept the simple solution, and I am not working there! :)

That said, I would not have submitted the code with the while(true) thing. And maybe I would have initilized to "" and not null.

Answer 4

I suspect that the question is badly worded, and/or that your answer is too clever and simple for their question, and that instead they wanted a class which implements a list.

Something like:

public class ListOfStrings
{
    class Node
    {
        internal Node(string stringValue) { this.stringValue = stringValue; }
        internal readonly string stringValue;
        internal Node nextNode;
    }

    Node firstNode;

    public string Add(string input)
    {
        Node newNode = new Node(stringValue)
        if (firstNode == null)
        {
            firstNode = newNode;
            return;
        }
        Node lastNode = firstNode;
        while (lastNode.nextNode != null)
            lastNode = lastNode.nextNode;
        lastNode.nextNode = newNode;
    }

In order to "Ideally, this code should be able to handle large numbers of items" you would want to store lastNode as well as firstNode as members (so that you don't need to recalculate lastNode every time you add a new string).

There's some ambiguity when they talk about a 'set' of strings; perhaps they want to keep the strings unique.

---

Also, I'd like to see what your ToString() would look like.

public override string ToString()
{
    StringBuilder sb = new StringBuilder();
    if (firstNode != null)
    {
        sb.Append(firstNode.stringValue);
        // next strings if any are comma-delimited
        for (Node nextNode = firstNode.nextNode; nextNode != null; nextNode = nextNode.nextNode)
        {
            sb.Append(",");
            sb.Append(nextNode.stringValue);
        }
    }
    return sb.ToString();
}

The above returns an empty string if there are no nodes/strings in the list. Alternatively you might want to return null so that the user can distinguish between an empty list, and list which contains one empty string.

OTOH this storage/display format is already sightly ambiguous, e.g. if a string contains a comma when it's stored.

Answer 5

I'm compelled to write an answer because no one has really covered the set thing yet. Sets, maps, queues, vectors, linked lists, etc are words that have meaning to programmers, and I have a hard time believing a programmer would ask a question like this without intending the elements be unique.

Overall, I agree with ChrisW and Carl Winder...it looks like they wanted some underlying data structure, not just a String that you append to. And they don't want .Net collections or Linq to be used.

Technically, you could use a String[] arr and be safe. However, adding a new item requires you to create a new array, copy all the old values in, and add in the newest value at the end. That's fairly expensive and will not work well with large sets.

Extending ChrisW's code:

class ListOfStrings
{
    class Node
    {
        internal Node(string stringValue) { this.stringValue = stringValue; }
        internal readonly string stringValue;
        internal Node nextNode;
    }
    Node firstNode;
    Node lastNode;

    public ListOfStrings() { }

    public void Add(String str)
    {
        if (str != null && !Exists(str))
        {
            if (firstNode == null)
            {
                firstNode = new Node(str);
                lastNode = firstNode;
            }
            else
            {
                Node n = new Node(str);
                lastNode.nextNode = n;
                lastNode = n;
            }
        }
    }

    private bool Exists(String str)
    {
        bool result = false;

        Node curr = firstNode;
        while (curr != null)
        {
            if(curr.stringValue.Equals(str))
            {
                result = true;
                break;
            }
            curr = curr.nextNode;
        }

        return result;
    }

    public override String ToString()
    {
        StringBuilder result = new StringBuilder("");

        Node curr = firstNode;
        while (curr != null)
        {
            if (result.ToString().Equals(""))
                result.Append(curr.stringValue);
            else
                result.Append(String.Format(",{0}", curr.stringValue));
            curr = curr.nextNode;
        }

        return result.ToString();
    }
}

As you see, I used his Node verbatim, and added the lastNode like he recommended. Most importantly, I added Exists, which is scoped as private, and put in the ToString as well.

Some important notes:

• I added the override keyword to ToString. Without doing so, you should get a compiler warning saying you're hiding object.ToString(). Heed these kinds of warnings, regardless of language! My rule of thumb is to eliminate most, if not all, warnings.

• ToString uses a StringBuilder as well as String.Format. I did this because String is immutable, and doing assignments to String essentially destroys the String and remakes it - just like the String[] arr explanation above.

• Add returns nothing. Typically, setter-type functions don't return a value. If they do, it's almost always a boolean which states whether the operation was a success or not.

• Exists guarantees uniqueness. It is case sensitive, so elements "XYZ" and "xyz" can exist at the same time. Making new functions that aren't specified in the question can be beneficial: it shows the interviewer that you can break new functionality out into a separate method, which makes the code easier to read and maintain. It also shows you can scope new functions properly. The outside world, according to the problem, doesn't use Exists, so there's no reason to make it public or protected. This is a very minor detail, but sometimes it's the little things which make the biggest difference.

• Add protects against adding null values, but it does not protect against adding the empty string: "", since the spec didn't cover whether to ignore that or not.