CS test questions - part 1

I would like to share with you some experience in Computer Science test. There are a lot of sources to read of such tests but I will share some practical CS tests I met.

All serious CS tests involve good understanding of algorithms and data structures. Many of them imply university CS course and good experience. Some of the tests are relatively simple and application programmers should pass such test to be admitted true "programmers".

 

Level 1. Application Programmer

Explain Bubble sort and write numbers sort code
Explain BST
Write a function to reverse a string of characters (no API)

 

Level 2. Senior Application Programmer

Explain Bubble sort and write array numbers sort code

Explain BST data structure then write code to search for human names in the BST
(See also Level 1)

Level 3: Software Engineer

Explain 3 sort algorithms you know
Explain known way to store and search data with O(1) complexity. Explain pros and cons.
Explain an algorithm to sort 8 GB data file on 4 GB RAM system (the main idea is that the file doesn't fit into the system RAM)
Explain effective string search in large text
Write quick sort function for integers
Write effective code to reverse single linked list like A->B->C->D into D->C->B->A
Write effective code to permute a string like "abcd"
Write code to identify that the single linked list is a palindrome

Level 4: Senior Software Engineer, System Software Engineer

Explain AVL tree, write a function to insert an element into the AVL tree of numbers
Explain graph algorithms you know and their complexity
Explain all synchronization primitives and their cons and pros
Write effective code to identify that the single linked list is a palindrome
Write simple non-blocking "echo" TCP server
Write advanced search function with O(1) for human names

Right tools

Tools

Spade is OK if you dig the ground all your life laying down tubes, pipes etc... Excavator is excellent thing when you run your own business in highway construction. But if you choose software development field then your tools depend on projects. You can't dig with a spade where you have to build a wall. If the customer requires to paint that wall then that high power excavator can't do that!
But during all of my life I meet people that insist on use of they favorite spades and excavators. And it is so funny to watch someone who prises "Java (or Microsoft.Net) is suitable for any kind of task" OR somebody honoring "C++ is capable for any type of project". Stop for a minute. Think. Research the successful projects. Get experience and don't use your favorite spade for everything. You will see that some project built with PHP are still earn money (www.facebook.com). And Microsoft.Net is not in every hardware platform and OS (Java does it much better). And even Java is not in iOS!

Money

Money comes from clients. Clients almost don't care the tools you use - C++. .Net, PHP, RoR or Java. But you care! For some tool you know the best. Therefore the reason you we (programmers) run our "holy wars" is we ourselves. And these "wars" confuse clients. So I doubt you choose C++ for small dynamic Web site. Or that you choose RoR for operating system utility.

Conclusion

30 years ago programmers use C and Pascal. Internet brought us HTML, JavaScript, Java, PHP and tons of other languages and tools. C++ with STL and later Boost (www.boost.org) inspired thousands of system developers over the world. Therefore: learn the most popular tools (languages and libraries). Do what clients want and earn money. This way programmer stays programmer (but not a "perforated card dinosaur").

Software Project Management Is Extremely Important (especially in Russia)

In case of oil company (or related to that business) almost nobody cares of software project management efficiency. Even many project managers don't. Sometimes top managers care. As soon as top managers start to care of projects progress they start to kick PM's asses and finally they may fire PMs. This should be some regular process in any kind of company even in oil - related industry. And it should take place not only after shareholders meetings :-)
Otherwise shareholders have losses quarter by quarter.
The reason for that is very low top managers' competition in IT sphere and bad staff policy.
There are some steps to avoid the pitfall:
1. hire (top) managers that got excellent financial results and best reference letters; test the candidates using 3-rd party agency, no other better way; diplomas mean nothing in the country of curruption;
2. set measurable goals for the managers; check achievements every quarter using transparent data;
3. hire very good IT professional; test coming candidates (using 3-rd party agency or internal test policy); also see #1.

The truth is that best companies hire best professionals to stay the best.