input/output operator overloading in C++

1) operator<< and operator>> should not be member functions, otherwise you would need to use something like s << cout or s >> cin instead of cout << s and cin >> s

2) You will need to make them "friends" since they need to access private members.

3) Their return type needs to be Objects of type ostream& and istream&. To see the reason, think about the following case:

cout<< s << "is the sparse matrix!" << endl;

Since the value of cout << s is cout (which is of type ostream), both "is the sparse matrix!" and endl can be subsequently inserted into cout.

Thus there is the signature:
class SparseMatrix
{
public:
...
friend ostream& operator<< (ostream& out, const SparseMatrix& s);
...

private:
...
};

Search tree vs. Hashing

There is always this question that I had in mind. For instance if hashing support queries and inserts in amortized constant time, why the hell do we need AVL trees, red-black trees and so on?

Obviously search trees can do some stuff more efficiently than hashing, for instance:
1) Range queries
2) Prefix searching (for instance with Tries)
3) Error tolerant searching.

For hashing, there is the extra storage (usually we need storage of size 2*n) problem but this also exists in search tree with the pointers.

Puzzles and Algorithms

This time, I would like to talk about a clever way of general algorithmic puzzle solving technique.

My first example is the celebrity problem: A celebrity is someone who knows nobody but is known by everybody. In a group of n people with 1 celebrity among them, what is the minimum number of questions that you should ask to find the celebrity for sure. The questions are of the form: "Do you know THAT guy?"

The second example is the managers-engineers puzzle: There are
n people in the building, each either an engineer or a manager. The problem facing the FBI is to separate engineers from managers. Each of the n people knows the status of all the others. The questions are of the form: "Is this person an engineer or a manager?" The engineers always tell the truth. What makes it hard is that the managers may not tell the truth. In fact, the managers are evil geniuses who are conspiring to confuse the interrogators. Under the assumption that more than half of the people are engineers, can you suggest a strategy for the FBI to find one engineer with at most n-1 questions?

Answers are to be posted... The way will be to eliminate as much people as possible with a single question while still maintaining the problem invariant.
Hint: Think it backwards ! Spotting an engineer or a celebrity may be hard. But it may be easier to spot a manager or a noncelebrity (respectively). Then we will have a subproblem...