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

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("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.

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

public class ListOfStrings
{
private string ListOfString;

public ListOfStrings()
{
ListOfString = null;
}
{
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.

• What did they mean by "not detailed enough"? They were expecting comments or something? – George Howarth Apr 2 '14 at 8:17
• @CarlWinder The specification is not clear enough to determine that. As long as only Add and ToString are required using StringBuilder is simple and efficient. If we really need a collection, the simplest approach would be a doubly linked list. If random access is required we'd need a tree. – CodesInChaos Apr 2 '14 at 10:59
• @CodesInChaos They specifically ask for a list. Look at the comments // set is now “abc”, “xyz” NOT set is now “abc,xyz”. I don't think we will ever see eye to eye on this, I think the spec is quite clear. – Carl Winder Apr 2 '14 at 11:13
• @GavinCoates I'd consider an array a built in .NET Collection, thus violating the requirement. Without that requirement I'd prefer an array or the array based List<T> over a linked list as wll. – CodesInChaos Apr 2 '14 at 11:46
• @tinstaafl An array implements IEnumerable<T>, ICollection<T> and IList<T>, so claiming it's not a collection is dubious IMO. There are also various immutable and readonly collections. The .net parts of MSDN are generally pretty low quality and contain a number of dubious claims like this. – CodesInChaos Apr 2 '14 at 13:26

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.

• +1 for StringBuilder... and everything else - nice answer you've got here. – Mathieu Guindon Apr 2 '14 at 16:13

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

• I would take the fact that they actively said to not use any of the .NET Collections to mean that I wouldn't be allowed to use an array either, as that has been appended with extension methods with LINQ. Although, if you remove that reference, I could possibly see using the purest form of array. Though I wouldn't want to risk that. – krillgar Apr 2 '14 at 16:52

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.

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

Node firstNode;

{
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.

• Good Answer. I suspect from the interview question that they want to have the programmer create a linked list, which is IMO is a good interview question – PhillyNJ Apr 2 '14 at 21:01
• If you're not going to have a lastNode field, there's no need to even have a Node class -- just store your stringValue directly in ListOfStrings. Also, Id like to see what your ToString() would look like. – Gabe Apr 3 '14 at 5:25
• @Gabe I updated my answer per your comment. – ChrisW Apr 3 '14 at 9:08
• @PhilVallone I think it's a really bad question if they actually expect that, but don't have anything in the requirements that forces you to use it. – svick Apr 3 '14 at 12:10

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 Node nextNode;
}
Node firstNode;
Node lastNode;

public ListOfStrings() { }

{
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.

• +1 but unfortunately that implementation of Exists is expensive i.e. O(n) instead of O(1). – ChrisW Apr 2 '14 at 20:58
• @ChrisW That's true, but without using some form of well-balanced tree structure you're essentially choosing which operations are O(n) and which are O(1). For an interview question, I don't think I would start with that kind of answer. It takes longer, and it's a good talking point if they proceed further with interviewing. Ie, "How would you improve this?" "I would ...." – Shaz Apr 2 '14 at 21:40
• If the type was really meant to be a set, why would they call it ListOfStrings and not SetOfStrings? – svick Apr 3 '14 at 12:08
• @svick Well, the two aren't mutually exclusive. You could have a vector set, a queue set, a circular buffer set, etc. – Shaz Apr 3 '14 at 14:01