Interview question doubt

[Priyanka Leo]

Guys i was asked the below question:

How to increase the performance of the following code:

String str ="";
for (int i=0;i>100000;++i)
{
str+=i;
}

Could you please help me with the solution for this ..

[Paul Clapham]

Typically to reduce the overhead caused by a lot of String concatenations, you could use a StringBuilder. Try that.

[Junilu Lacar]

Seems to me that's a trick question. That loop already performs as efficiently as it could. Maybe that's the answer. Unless you typed it in wrong, of course.

Priyanka Leo wrote:

String str ="";
for (int i=0;i>100000;++i)
{
str+=i;
}

Interview challenge: Look at that code and tell me why it doesn't need to be optimized.

[Junilu Lacar]

The point I wanted to make was that in general, I find interview questions that require you to look at code and guess at how to optimize it disappointing at best, especially if the expectation truly is to find a way to optimize.

Programmers suck at optimizing code by guessing where the bottleneck is. It's an inexact "science" at best, more like quackery really. If you're going to optimize, do it with concrete data you get from running a profiler. Nine times out of ten it will prove your guesswork wrong, just as I hope it would show that the code as you gave it in the original post didn't actually pose a performance problem.

[Campbell Ritchie]

Assuming OP copied the code correctly, you can optimise it by deleting code. I shall leave OP to work out which code to delete.

[Junilu Lacar]

A blog post inspired by this thread: https://jlacar.github.io/coding/premature-optimization-1.html

TL;DR

As posted, that code doesn't need to be optimized because the body of the loop will never be executed.

Optimization shouldn’t be done on the basis of intuition. Developers are your biggest bottleneck in software development. Save their time and you’ll save more. Seek first to reduce development time by simplifying and clarifying your code. That’s where you’ll get the most return on your time and effort.

[Tim Holloway]

It's worth noting that the performance of that code can vary widely.

Because the effects of the loop are not transported out of the loop (assuming we haven't a wider context), a compiler might completely discard the processing inside the loop, making for extremely "efficient" execution (zero run-time).

But if debugging is turned on, then loop optimisation will probably be turned off, causing the execution time to balloon.

This is also a bit of a trick exercise in that at first blush it looks like it's doing things with numbers, but actually it's converting the numbers to strings and concatenating the strings.

So a good first entry would be to use a StringBuilder and not concatenation.

I could think of some other, less obvious tricks that might further accelerate things, but only measurement would tell.

[fred rosenberger]

"optimization" can mean different things:

execution time
memory usage
simplicity to read

and how you'd optimize for each differs.  

[Tim Holloway]

fred rosenberger wrote:"optimization" can mean different things:

execution time
memory usage
simplicity to read

and how you'd optimize for each differs.  

Could, but optimization for memory pretty much went out with the mainframe (I exclude tuning, because any idiot can make a program that require 16.5 Terabytes of RAM).

And optimization for simplicity (refactoring) is not popular because if any idiot can understand the code, there goes your job security.

About the only one of the three that gets any serious consideration these days is optimization for wall-clock time (not CPU time - only mainframes billed for that).

[Jesse Silverman]

Junilu Lacar wrote:A blog post inspired by this thread: https://jlacar.github.io/coding/premature-optimization-1.html

...

Optimization shouldn’t be done on the basis of intuition. Developers are your biggest bottleneck in software development. Save their time and you’ll save more. Seek first to reduce development time by simplifying and clarifying your code. That’s where you’ll get the most return on your time and effort.

Beautiful post, and quite short too!

This is Beginning Java, so the stuff you warned me about where I (like other responders in this thread) were presuming performance differences in + versus StringBuilder, don't even apply, because Less Is More.

But old assumptions about the relative performance of + versus StringBuilder no longer apply the same way anymore, details for anyone interested in another thread...

OP, ignore this, responders who still believe that we need to jump for StringBuilder over +, maybe look here?
https://coderanch.com/t/744707/java/String-concatenate-String-immutable

[Junilu Lacar]

fred rosenberger wrote:"optimization" can mean different things:
...
simplicity to read

and how you'd optimize for each differs.

Kind of a slippery slope there if you include "simplicity to read" as an optimization, in my opinion.

For me, optimization is purely about efficient use of computing resources. Developer time doesn't fall into that bucket, even though I agree with the notion that we developers are in a sense part of the software; those are our thoughts and ideas in electronic form after all.

What I was getting at with "Seek first to clarify and simplify" is to refactor first, optimize later if you really need to.

That is based on the following definitions:
refactoring - making code easier to understand and easier to work with.
optimization - making more efficient use of computing resources (network bandwidth, memory, compute power, disk space, database, etc.)

[Junilu Lacar]

Jesse Silverman wrote:Beautiful post, and quite short too!

Thanks! Glad you liked it.

Yeah, I'm working on writing short and to-the-point. I need a lot more practice though.

[Campbell Ritchie]

Jesse Silverman wrote:. . . old assumptions about the relative performance of + versus StringBuilder no longer apply . . .

The optimisation in Java9 improved the performance of += greatly, but for large loops like in this thread (if you correct the operator), the difference is still significant.

[fred rosenberger]

Junilu Lacar wrote:

Jesse Silverman wrote:Beautiful post, and quite short too!

Thanks! Glad you liked it.

Yeah, I'm working on writing short and to-the-point. I need a lot more practice though.

I would have written a shorter letter, but I did not have the time. - Blaise Pascal

[Jesse Silverman]

Campbell Ritchie wrote:

Jesse Silverman wrote:. . . old assumptions about the relative performance of + versus StringBuilder no longer apply . . .

The optimisation in Java9 improved the performance of += greatly, but for large loops like in this thread (if you correct the operator), the difference is still significant.

Cool.  The actual quantitative nature of the performance difference has been flagged for "come back to later" for me.

It is certainly much less than it was 12 years ago, and in this case, += is pretty darn convenient and easy to read.

[Tim Holloway]

As I recall, in the earliest Java compilers, using "+" in string declarations caused runtime concatenation logic to be generated. Later, optimizations were added to pre-concatenate at compile time where possible (this class of optimisation is known as constant folding.) Don't know what specifically Java 9 added, but compilers continue to get smarter.

[Campbell Ritchie]

Tim Holloway wrote:. . . "+" in string declarations caused . . . constant folding.) . . .

Multiple +s in the same statement have never caused a performance issue. It is only in loops that they are a problem.

[Junilu Lacar]

fred rosenberger wrote:I would have written a shorter letter, but I did not have the time. - Blaise Pascal

I think I've seen that attributed to Mark Twain. I may be wrong. But yes, exactly.

[Campbell Ritchie]

This link is too long, so I didn't have time to read it all. I don't know whether it comes to any decisions about whom to attribute that quote to.

[Paul Clapham]

Campbell Ritchie wrote:This link is too long, so I didn't have time to read it all. I don't know whether it comes to any decisions about whom to attribute that quote to.

If you see a quote attributed to Mark Twain or to Einstein, that's almost certainly wrong.

[Jesse Silverman]

Campbell Ritchie wrote:This link is too long, so I didn't have time to read it all. I don't know whether it comes to any decisions about whom to attribute that quote to.

Although there are translation issues that could cause reasonable people to disagree, I am going with Blaise Pascal FTW.  John Locke was close.

Quite a popular quote already in the 17th Century.

[salvin francis]

I'll take an opinionated approach here....
Here's my answer:

String str ="";

Is it just me or ... No one read the loop statement !!??!
Edit: Campbell spotted it first !

[Junilu Lacar]

salvin francis wrote:Is it just me or ... No one read the loop statement !!??!
Edit: Campbell spotted it first !

Oh, really. So what am I, cabbage soup? ;)

[Campbell Ritchie]

I thought I was the sort of soup

[Damon McNeill]

Priyanka Leo wrote:Guys i was asked the below question:

How to increase the performance of the following code:

String str ="";
for (int i=0;i>100000;++i)
{
str+=i;
}

Could you please help me with the solution for this ..

Assuming the code is copied verbatim, it's a trick question: this code can be optimized by never being written in the first place.
Since 0 is not greater than 100000. the loop never executes. Furthermore, since the value of str is never used this code is a no-op.
Perhaps this code segment is missing some additional context. For sure the loop can be deleted in any case.

[Campbell Ritchie]

Damon McNeill wrote:. . . Assuming the code is copied verbatim . . .

I still think the > is copied wrongly, in which case the answer should discuss +=, multiple +s in the same statement, StringBuilder, and the enhancements introduced in Java9.

. . .  the loop can be deleted in any case.

Which an optimising JIT compiler might do at runtime anyway.
We don't know that the str variable won't be needed by later code, so we might want to retain its declaration.

[salvin francis]

Junilu Lacar wrote:...Oh, really. So what am I, cabbage soup? ;)

That is a very tricky question !!
My answer is Yes, only if you're a person who really cherishes drinking that.

[salvin francis]

Back to the question at hand. If the loop was indeed valid from 0 to 100000, my answer would vary depending on my mood. If I was in a good mood, I would divulge into StringBuilder.
If not, I would question the interview about why the said requirement was valid from a business stand point.
I don't see any usecase where a program would require a string of numbers like "...50005001500250035004..." without any delimiter.

[Campbell Ritchie]

Which approach will make you more likely to get the job, Salvin?

[Liutauras Vilda]

It's bad that OP doesn't come and clarify whether question is indeed correctly copied over. But anyway, discussion is still interesting.

For what kind of business sector this interview was conducted for?

[Jesse Silverman]

I remember an interview I had (which I didn't get the job for   ) where two relatively junior programmers came in with a print-out of a program.

They said "Find all the errors in this program and tell how you would correct them."

I did my best for five or six minutes (I think two or three pages of code) while they frantically took down notes on what I said, and then asked "How did I do?  Did I get them all?  Were there any mistakes in what I said?"

"We don't know," they replied.  "It's the code we were working on when they asked us to come in and interview you."  * * * Sheepish Grin * * *

[Jesse Silverman]

This is relevant to both of the topics of Interview Questions and Premature Optimization and the Starkist Question - *

In the cross-topic-cutting discussion we have had recently on Premature Optimization, Interviews and Jobs...

I am still submitting resumes for and going on interviews (and second interviews and some third interviews) for both positions where they just care that you can write (reasonably correct, reasonably okay performance one hopes, not always emphasized) code *FAST*, and others where you need to write VERY CORRECT, VERY ROBUST code that runs VERY FAST, which may take you a little more time to complete.

Lines like this are essentially impossible to interpret out of context:

You will be able to deliver high quality results in a rapidly changing environment that requires flexibility and adaptability with razor focus on speed to execute.

My guess is that this team wants to hire whoever can check-in code the fastest, based on clues found in other lines, but I have found many job descriptions are terribly written in that once you speak to the hiring manager, what they actually care about differs wildly from the original description you had read.  I mean WILDLY, like "Were they even involved in writing the posted description?" wildly.

Once you start talking to them, you may find out what is keeping them up at night is too many sporadic failures, or bad worst-case performance, or fragility in the face of minor changes to external data formats not in their control, or whatever.  I think it is good to identify those kinds of things and then explain how you have successfully dealt with similar problems in the past (Well, it sure gets lots of second and third interviews)...but the last few have gone quite far in the process only to terminate with "Sorry, Charlie!"

* ( https://en.wikipedia.org/wiki/Charlie_the_Tuna ) Charlie wants to work for the tuna company and says he should be hired because he has eminently Good Taste, but the company is only interested in tuna that Tastes Good.  Painfully mirroring the current job market.

[salvin francis]

Campbell Ritchie wrote:Which approach will make you more likely to get the job, Salvin?

depends on how interesting the conversation goes post that question  

[Jesse Silverman]

This was an Interview question, with three !!!'s, no less.

My approach is to try to quickly fire off the normal things I would be concerned about in Real Life, saying "stop me if any of these should be considered in my answer", then saying "Just taking the request at hand at face value, we could..."

A fair amount of times they will fix on one or more of the "Yeah, but in real life" things I brought up and add that in to the question.

A fair amount of times they will say, "Well, you just answered what were supposed to be next two questions as well" (this is either great or not so great depending on the temperament of the interviewer.  I have had some break out laughing because I kept anticipating their next questions and already answered them, if they like to feel totally in charge of the process they could find it annoying.  "Reading the room" is a skill we can pick up from comedians.)

[Campbell Ritchie]

Jesse Silverman wrote:. . . a skill we can pick up from comedians.)

That's a good point.

[Damon McNeill]

Campbell Ritchie wrote:

Damon McNeill wrote:. . . Assuming the code is copied verbatim . . .

I still think the > is copied wrongly, in which case the answer should discuss +=, multiple +s in the same statement, StringBuilder, and the enhancements introduced in Java9.

. . .  the loop can be deleted in any case.

Which an optimising JIT compiler might do at runtime anyway.
We don't know that the str variable won't be needed by later code, so we might want to retain its declaration.

This raises additional questions such as why the absolute value 100000 (or whatever it was). Yes perhaps the compiler or JIT would notice this useless loop and simply remove  it. But why even write this? Would the output even be meaningful? Lol, oh well.

[Junilu Lacar]

Don't lose sight of the fact that this came up in an interview. The point is to find out what the candidate knows, not to show exemplars of how to write code.

[Jesse Silverman]

Junilu Lacar wrote:Don't lose sight of the fact that this came up in an interview. The point is to find out what the candidate knows, not to show exemplars of how to write code.

Thank you Junilu.
There's at least two reasons that someone might show you bad code on an interview or on a mock exam.

1. To find out if you even see anything wrong with it (more likely on more Junior positions).
2. To find out if when seeing it on a code review or working with someone else's code, if you can politely but clearly explain why it is bad, and how we should fix it (very likely if you have already said that you love doing code reviews and mentoring junior developers).  Interviewing for a position (or set of positions) I eventually kept for 11+ years, a pivotal question was "Some Big Senior Developer/Team Leader just broke everything.  Can you go explain it to them in a way so it gets fixed quickly, without insulting the person who did it and annoying them?"  I answered "Yes" and the fact that I stayed there for 11 years and countless rounds of RIFs suggested I wasn't lying.

"We have compilers to tell us our code won't compile, because we are in Java!"
Sure, which is why the focus would be on bad code that compiles fine, and may appear to run okay, at least for some values of data, but has Lurking Problems that I used to describe as "An accident that can't wait to happen!"  I get a lot of these on interviews.

[L Foster]

I see some great posts pointing out interesting things about the example code.

Interesting question in some ways.  If I were asked "how I would optimize it", and I don't guarantee this would win points, I think I would reply that I would paste the code into an IDE, run it a million times, and see how long it actually takes.  Then I would possibly profile it (although this is pretty small) to see where the time is going, and one fix I would consider changing would be the concatenation argument (+) to using of StringBuilder.append().  I say "consider" because there may be some JVM optimizations by this point that handle underlying use of String Builder.  After any such change, run it a million times again and time it.  Multiplying runs like that is a good way to force differences to emerge even if they were fairly small to begin with.  As has been pointed out, this code will not do anything.  As such it will run pretty fast.

[Damon McNeill]

As a simple test for a deceptive candidate, sure this would be a good interview question. And it can lead to some pretty interesting conversations. But to be frank, it feels like scraping the bottom of the barrel a tad bit. Is there really that many charlatans posing as Java developers who cannot see these problems?