Recently I was asked this question on interview and I didn't know how to answer it.
Can anyone answer this question and describe it?
Add a comment
|
2 Answers
O(1) since the length is stored as an attribute: source
However, this trivia is worth countering with a discussion about micro-optimising theatre, as kindly provided by our hosts here and here; read those two links and you'll find a good talking point to change the momentum of the conversation next time similar questions come up, regardless of whether you know the particular answer!
How the interviewer reacts to your tangent will tell you a lot about how much you want to work with them..
8 Comments
Chvanikoff
Thank you. Could you give some more similar articles to read? What about interviewer - he was looking for developer with much stronger qualification than I have and this question was not "just for fun". But it gave me better knowledge about my skill weaknesses.
Will
The interviewer was likely reading a prepared list of questions? Even at Google. The sooner you take them off the track the better.
Nikolai
I don't see where your source mentions that string length is stored as an attribute.
jamesdlin
Comparing one O(n) string concatenation implementation vs. some other O(n) string concatenation implementation is probably micro-optimization theater. Knowing whether
strlen is O(1) or O(n) can have a huge impact; just look at how sscanf's unexpected O(n) implementation led to O(n^2) parsing. |
I would assume that function is O(n) because it would need to iterate through the string once.
