Русская версия этого поста здесь.
As you may already know, our company is running internship programs for young developers in Ukraine (as well as in Russia and Armenia). This is a second year in a row we do it in Kiev, and we are quite happy with the results we achieved in 2009.
From time to time, to keep students low-fat and for pure entertainment, we replace random lecture with coding exercises. Hack hours.
Last time we decided that it’s time to ask our students to create a small program, that will
- read text from stdin
- split it into words (word is defined as a sequence of [A-Za-z0-9] characters)
- .. and print out A-Z sorted list ow lowercased words along with lines these words were met on
Pretty and simple, huh? Since I want to be sure that this task has no hidden pitfalls and that I can answer common questions that may arise, I also solved this problem in pure C++ style. Took 25 minutes or so. Thus, we expected to see most students do this assignment in a hour, so we can get back to the lecture for the second hour.
Well, life brings surprises.
It appeared that only 1 out of 10 students was able to finish task while in class. Yes, I know that programmers can’t program, but this was a bit of a disappointment for us.
To be honest, several of them were able to come up with code, but all other submitted assignments failed to process 40 Mb file in a reasonable time (my initial program did it in 22 sec on my Core i5-750 PC). All others presumably used linear lookups, which gave O(n2) complexity, simply inadequate for large inputs.
No morale here, except of – “know basic data structures and algorithms”. Take you time reading about them, spend some time practicing, and most simple programming challenges you will have in your life will be far less challenging (so you can spend your precious time working on what is really interesting).
This was only the first part of my story. To be continued.
Tags: algorithms, cqg, education