Sniff
What’s wrong with this line of code?
I got this story form Google China’s official blog. The original post was written by an engineer working at Google China (Mr. Fang Kun) and it was written in Chinese. I’m summarizing it in English.
Mr. Fang Kun was recruiting students for Google China. The recruit was highly interested in students’ capability/experience of programming and their algorithmic sense. It was disappointing to see many students of Computer Science/Software Engineering never realized the problem in this line:
for (int i = 0; i < strlen(s); ++i)
Mr. Fang Kun said, there was not anything fancy/profound/mysterious of this problem, the students really need to code, code and yet again code to get fluent and get familiar with all kinds of potential problems in the code. He quoted Dr. Kai Fu Lee’s words for the minimum amount of 100K lines of code practicing during the 4 years of college, if the student wants to join Google.
Things got more grievous when Mr. Fang asked a straight-A student from one of the best Chinese universities about this question: “What is the complexity of traversing a linked list?” The straight-A student said O(Log N). Fang was shocked and tried to help the student “What do you think traversing a linked list is all about?”. The student made a big “I-got-it” face and said immediately “Ah, it should be O(N Log N)”. Fang almost fainted away. There were many similar cases during their recruit. Many students were out because of failure on such most basic questions.
At the end Fang said you students really have got to get rock solid on the basic science. Uh.
The world changes fast but I believe there are some values that stay stable. Greatness is always built upon solid and hard work. Stepping on shortcut and make a good-looking superficial thing does not work. Franz Liszt was able to create and play pieces like La Campanella only after many years of hard finger practicing, no matter how talented he actually was, hard practicing cannot be omitted. No matter how smart a programmer is, without hard practice on coding, his smartness cannot be expressed in correct and efficient code. Let’s code more and understand better about the math in the algorithms.
Sneeze:
I did not really program in C/C++ except for some very short homework assignments. So I did not get the problem in ” for (int i = 0; i < strlen(s); ++i)", the only thing I know is that strlen(s) returns the length of the string s. The java equivalent is for (int i=0; i < s.length(); ++i). So I sent an email asking my boyfriend what the problem on earth was. He replied in 2 minutes:
Probably it's about efficiency. strlen() has to go through the string to search for the 0-byte at the end each time. So you get O(n^2) for a simple scan through a string. A more efficient version would be
for (int i=0; s[i] ; i++)And for the java-version, we know that java-programmers never think about efficiency. That's why the programs are so slow. Maybe the just-in-time compilers are almost as good as plain C, but the programmer does not see the performance consequences of the programming style.
This is already much better:
int len = aString.length();
for (int i=0;i < len ;i++)
I know when he was talking about Java-programmers, he only referred to me. He does not use Java, nobody in his research group does. This is no offense to any other Java programmers. 
It is a little bit unfair to say I never think about efficiency. Years ago I got the book Effective Java and it is already dogeared. I never do things like String s = new String("string"); I always implement hashCode() and equals() correctly. (Now the eclipse can generate these two methods automatically, given the relevant fields). I watched out for orphan object islands in my code. I always think about how many database hits my mapping configuration + query generates, and optimize wherever possible. I do think about efficiency, but at a higher level. How the java vm fetching the length of a string is kinda out of my mind. 
As for the complexity of traversing a linked list thing, I first thought Fang must be joking. Yah I can answer this question correctly. Maybe I could file a job application at Google. 
