StringBuilder help

[rhkodiak]

I was in an interview question what is the most efficient way to sort
a string for example "010101", the result would then be "000111", and
write the code on how to do this. I wrote the code for the
interviewers and I was told I did ok, but a stringbuilder would have
been better to use. In this storing the string in an array and
calling the sort method is not a solution for this problem. If anyone
can help explain how using a stringbuilder is better in this way
please let me know and please show the code on how to use the
stringbuilder because I cannot figure it out. I have provided sample
code for what I did. Thanks!

public string GetString(string text)
{
string t1 = string.Empty, t2 = string.Empty;

for(int i = 0; i < text.Length; i++)
{
if(text.ToString() == "0")
{
t2 += text.ToString();
}
else
{
t2 += text.ToString();
}
}

return t1+t2;
}

 

[Scott Roberts]

I was in an interview question what is the most efficient way to sort
a string for example "010101", the result would then be "000111", and
write the code on how to do this. I wrote the code for the
interviewers and I was told I did ok, but a stringbuilder would have
been better to use. In this storing the string in an array and
calling the sort method is not a solution for this problem. If anyone
can help explain how using a stringbuilder is better in this way
please let me know and please show the code on how to use the
stringbuilder because I cannot figure it out. I have provided sample
code for what I did. Thanks!

public string GetString(string text)
{
string t1 = string.Empty, t2 = string.Empty;

for(int i = 0; i < text.Length; i++)
{
if(text.ToString() == "0")
{
t2 += text.ToString();
}
else
{
t2 += text.ToString();
}
}

return t1+t2;
}

They didn't like your string concatination because it generates an entirely
new string each time (memory intensive). Also, you never assign anything to
"t1", which is probably a problem.

public string GetString(string text)
{
StringBuilder t1 = new StringBuilder();
StringBuilder t2 = new StringBuilder();

for(int i = 0; i < text.Length; i++)
{
if(text.ToString() == "0")
{
t1.Append(text.ToString());
}
else
{
t2.Append(text.ToString());
}
}

return t1.ToString()+t2.ToString();
}


Although, I'm pretty sure that this isn't "optimal" either.

 

[Michael D. Ober]

I was in an interview question what is the most efficient way to sort
a string for example "010101", the result would then be "000111", and
write the code on how to do this. I wrote the code for the
interviewers and I was told I did ok, but a stringbuilder would have
been better to use. In this storing the string in an array and
calling the sort method is not a solution for this problem. If anyone
can help explain how using a stringbuilder is better in this way
please let me know and please show the code on how to use the
stringbuilder because I cannot figure it out. I have provided sample
code for what I did. Thanks!

public string GetString(string text)
{
string t1 = string.Empty, t2 = string.Empty;

for(int i = 0; i < text.Length; i++)
{
if(text.ToString() == "0")
{
t2 += text.ToString();
}
else
{
t2 += text.ToString();
}
}

return t1+t2;
}

I came up with a solution that uses the built in Array.Sort method.

static string SortString(string sIn)
{
char[] s = sIn.ToCharArray();
System.Array.Sort(s);
System.Text.StringBuilder sBuilder = new
StringBuilder(sIn.Length);
foreach (char c in s) {
sBuilder.Append(c);
}
return sBuilder.ToString();
}

Basically, convert the string to a char array, sort it, then create a
StringBuilder long enough to contain the entire char array without
reallocation and append the characters to it. Allocations in this method
are:

One allocation to create the char array.
One allocation to create the string builder (size is known from the size
of the input string, so no reallocations are required)
One allocation to convert the string builder to a string.

The char in the foreach loop is probably held on the stack so there are no
heap allocations required.

Mike.

 

[Peter Duniho]

I came up with a solution that uses the built in Array.Sort method.

static string SortString(string sIn)
{
char[] s = sIn.ToCharArray();
System.Array.Sort(s);
System.Text.StringBuilder sBuilder = new
StringBuilder(sIn.Length);
foreach (char c in s) {
sBuilder.Append(c);
}
return sBuilder.ToString();
}

Basically, convert the string to a char array, sort it, then create a
StringBuilder long enough to contain the entire char array without
reallocation and append the characters to it.

While I think the general approach is fine (but if I read the OP
correctly, not a valid answer for his situation, since he specifically
wrote "...calling the sort method is not a solution for this problem"),
why use the StringBuilder? Why not just "return new string(s);"? Surely
that's at least as efficient as enumerating each character and adding it
to a StringBuilder.

Pete

 

[Ignacio Machin \( .NET/ C# MVP \)]

Hi

I was in an interview question what is the most efficient way to sort
a string for example "010101", the result would then be "000111", and
write the code on how to do this

What if the string contains more than 1 and 0 ?

 

[Bill Butler]

I was in an interview question what is the most efficient way to sort
a string for example "010101", the result would then be "000111", and
write the code on how to do this. I wrote the code for the
interviewers and I was told I did ok, but a stringbuilder would have
been better to use. In this storing the string in an array and
calling the sort method is not a solution for this problem. If anyone
can help explain how using a stringbuilder is better in this way
please let me know and please show the code on how to use the
stringbuilder because I cannot figure it out. I have provided sample
code for what I did. Thanks!

I am curious.
You gave a fairly loose description of the problem statement.
Can you remember it more exactly?

Did he specify that is would only contain '0', '1'?
Did his example only have 6 characters ["010101"] , or did you simplify?
Did he really ask for the "Most efficient"?

Basically, I am wondering if your interviewer knew what he was talking
about.

I will tell you right now that using StringBuilder for the sample you
posted is actually less efficient than string concatenation. The
StringBuilder will become more far efficient on much longer strings, but
in this example the StringBuilder is slower.

Anyway, just curious.
Bill

 

[Pedro Luna Montalvo]

Hmmm...can the string only contain ones and zeroes???
Your implementation only works for that case.

If so, this is much more simple and faster:

string SortOnesAndZeros(string original)
{
int zeroes = 0;
foreach (char item in original)
{
if (item == '0')
{
zeroes++;
}
}

return new string('0', zeroes) + new string('1', original.Length -
zeroes);
}


If the string can contain any character, maybe this is a better approach:

string SortCharsInString(string original)
{
char[] chars = original.ToCharArray();
Array.Sort(chars);
return new string(chars);
}

Greetings,

 

[Lasse Vågsæther Karlsen]

I was in an interview question what is the most efficient way to sort
a string for example "010101", the result would then be "000111", and
write the code on how to do this. I wrote the code for the
interviewers and I was told I did ok, but a stringbuilder would have
been better to use. In this storing the string in an array and
calling the sort method is not a solution for this problem. If anyone
can help explain how using a stringbuilder is better in this way
please let me know and please show the code on how to use the
stringbuilder because I cannot figure it out. I have provided sample
code for what I did. Thanks!

public string GetString(string text)
{
string t1 = string.Empty, t2 = string.Empty;

for(int i = 0; i < text.Length; i++)
{
if(text.ToString() == "0")
{
t2 += text.ToString();
}
else
{
t2 += text.ToString();
}
}

return t1+t2;
}

Just out of curiosity, what was the point of this question? Did they
just want to check if you could implement a sorting algorithm? It just
seems random and hypothetical to me... Not the sort of thing I would
want to check in a particular candidate anyway.