This is the 2nd in a series of 3 posts covering 15 exercises that provide a sense of a programming language's idioms and "feel." For newcomers, if you can't "jump in" and tackle these exercises in a particular programming language, don't embarrass yourself by claiming to know that language. For more experienced developers, these programs should be tough enough to require problem-solving: try to embrace the language's idioms.
The first series of exercises dealt with calculations. Now let's move on to structures: both data structures and trying to get a sense of how programs are structured.
Data Structures
- Write a class (or module or what-have-you: please map OOP terminology into whatever paradigm appropriate) that only stores objects of the same type as the first object placed in it and raises an exception if a non-compatible type is added. Write a program that uses this class, outputting "Store 1 contains n instances of type t and then iterating over the stored objects," and handles the exception. Now refactor the application so that the exception results in the creation of a new instance of your storage class and continues, so that the output would be "Store 1 contains n instance of type t, etc., Store 2 contains 1 instance of type u, etc."
Educational goals of exercise 6:
class creation, component structure, type behavior, memory allocation, exception/resumption, environment support for refactoring.
- Using the language's idioms, implement a tree-based datastructure (splay, AVL, or red-black).
Educational goals of exercise 7:
In-memory data structures. Algorithm expression. Idioms. Memory and type issues.
- Create a new type that uses a custom comparator (i.e., overrides "Equals"). Place more of these objects than can fit in memory into the datastructure created above as well as into standard libraries, put more objects into it than can fit in memory. Compare performance of the standard libraries with your own implementation.
Educational goals of exercise 8:
You should really have a "sense" of the program's memory management by this point. Not complete knowledge, but enough sense to begin work.
- Implement an iterator for your datastructure. Consider multithreading issues.
Educational goals of exercise 9:
Refactoring, expressiveness, design patterns, concurrency model.
- Write a multithreaded application that uses your data structure, comparable types, and iterators to implement the type-specific storage functionality as described in Exercise 6. How do you deal with concurrent inserts and traversals?
Educational goals of exercise 10:
Understanding of data structures, Concurrency issues (locking, races, etc.).
Discussion
Exercise 10 is the sort of problem that I would expect any job applicant or intern to speak to in their interview process and be able to work on productively. Note that I'm not talking about having memorized the tree-balancing algorithms -- I don't give a rat's ass if someone remembers how red-black trees work or even if they remember its Big O characteristics. But they must know how datastructures in language x work -- that's fundamental.
Language-wise, in my opinion, this is a set of exercises where C and C++ shine -- at least until the multithreading stuff. Languages with list-processing idioms will also do well initially, but may have memory-consumption issues (especially functional languages). Ultimately, I think that the managed C-derived language (Java and C#) have the easiest route to Exercise 9 and then face serious shortcomings with Exercise 10, where concurrency issues play the major role. In my opinion, concurrency is going to become the central issue in professional development in the next half-decade, so these shortcomings are very significant.
Part 1. Part 3