Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was asked about immutable strings in Java. I was tasked with writing a function that concatenated a number of "a"s to a string.

What I wrote:

public String foo(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a"
    }
    return s;
}

I was then asked how many strings this program would generate, assuming garbage collection does not happen. My thoughts for n=3 was

  1. ""
  2. "a"
  3. "a"
  4. "aa"
  5. "a"
  6. "aaa"
  7. "a"

Essentially 2 strings are created in each iteration of the loop. However, the answer was n2. What strings will be created in memory by this function and why is that way?

share|improve this question
12  
If you get offered this job, run away, run very fast....... –  mattnz Nov 27 '13 at 2:57
    
@mattnz for multiple reasons (and not just because of the written code). –  MichaelT Nov 27 '13 at 3:20
3  
This takes O(n^2) runtime unless the JIT optimizes the loop, but it does not create n^2 strings. –  user2357112 Nov 27 '13 at 7:45

3 Answers 3

up vote 19 down vote accepted

I was then asked how many strings this program would generate, assuming garbage collection does not happen. My thoughts for n=3 was (7)

Strings 1 ("") and 2 ("a") are the constants in the program, these are not created as part of things but are 'interned' because they are constants the compiler knows about. Read more about this at String interning on Wikipedia.

This also removes strings 5 and 7 from the count as they are the same "a" as String #2. This leaves strings #3, #4, and #6. The answer is "3 strings are created for n = 3" using your code.

The count of n2 is obviously wrong because at n=3, this would be 9 and even by your worst case answer, that was only 7. If your non-interned strings was correct, the answer should have been 2n + 1.

So, the question of how should you do this?

Since the String is immutable, you want a mutable thing - something you can change without creating new objects. That is the StringBuilder.

The first thing to look at is the constructors. In this case we know how long the string will be, and there is a constructor StringBuilder(int capacity) which means we allocate exactly as much as we need.

Next, "a" doesn't need to be a String, but rather it can be a character 'a'. This has some minor performance boosting when calling append(String) vs append(char) - with the append(String), the method needs to find out how long the String is and do some work on that. On the other hand, char is always exactly one character long.

The code differences can be seen at StringBuilder.append(String) vs StringBuilder.append(char). Its not something to be too concerned with, but if you're trying to impress the employer it is best to use the best possible practices.

So, how does this look when you put it together?

public String foo(int n) {
    StringBuilder sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) {
        sb.append('a');
    }
    return sb.toString();
}

One StringBuilder and one String have been created. No extra strings needed to be interned.


Write some other simple programs in Eclipse. Install pmd and run it on the code you write. Note what it complains about and fix those things. It would have found the modification of a String with + in a loop, and if you changed that to StringBuilder, it would have maybe found the initial capacity, but it would certainly catch the difference between .append("a") and .append('a')

share|improve this answer

On each iteration, a new String is created by the + operator and assigned to s. After return, all of them but the last are garbage-collected.

String constants like "" and "a" are not created every time, these are interned strings. Since strings are immutable, they can freely be shared; this happens to string constants.

To efficiently concatenate strings, use StringBuilder.

share|improve this answer
    
The people at the interview actually debated over whether or not the literal was, and decided that the literals were created every time. But this makes more sense. –  ahalbert Nov 27 '13 at 3:07
4  
How do you "debate" what a language does, surely you read the specification and know for sure, or its not defined and therefore, there is no correct answer..... –  mattnz Nov 27 '13 at 8:00
    
@mattnz It might be interesting to know what the compiler/runtime you're using does, even when it comes to implementation details. This applies especially to performance. –  svick Nov 28 '13 at 20:32
1  
@svick: You can gain a great deal by making assumptions, then the compiler is upgraded, an optimization changed etc. The behavior changes causing bugs because you relied on unspecified behavior rather the defined behavior. You know what they say about optimization - a) leave it to experts and b) your not an expert yet. :) If the reliance is performance based only, but still to language specification, then you only loose performance. Many times I have seen code that relied on unspecified or compiler specific behavior break in unexpected ways (mostly C and C++). –  mattnz Nov 28 '13 at 21:08
    
@mattnz So how do you propose to make decisions related to performance? Usually, the best you can get from the specification/documentation are big-O complexities, but that's not enough. In any case, performance will always depend on the implementation, so I think it's okay to rely on implementation details when it comes to performance. –  svick Nov 28 '13 at 21:17

As MichaelT explains in his answer, your code allocates O(n) strings. But it also allocates O(n2) bytes of memory and runs in O(n2) time.

It allocates O(n2) bytes, because the strings you're allocating have lengths 0, 1, 2, …, n-1, n, which sums to (n2 - n) / 2 = O(n2).

The time is also O(n2), because allocating i-th string requires copying of (i-1)-th string, which has length i-1. This means each allocated byte has to be copied, which will take O(n2) time.

Maybe this is what the interviewers meant?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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