I need to interview a candidate with over 8 years of experience in Linux using C/C++.
What would be the best way to judge such a candidate?
Do I need to test his understanding of algorithms?
Do I need to test his programming skills by asking to write a program?
How should I test his understanding of Linux?
Maybe you should focus on what you need. Can he help you? Has he solved problems similar to yours? What are his expectations, what are yours?
It depends entirely on what you want him to do. You haven't said anything about the position that you are hiring for but if, say, you want him to write C# then you need him to prove his adaptibility.
Do you need him to write (or modify or bugfix) algorithms? If not, then it is pointless determining how good at them he is.
On the other hand, in order to understand his abilities, you may be better off talking to him about a domain that he is familiar with. You should certainly get him to describe a recent project that he has been involved in, what his contribution was, what the challenges were, what went well, what lessons he learnt.
I interview people like this all the time. The answer is that no matter how much experience he has, you must prove to yourself that he is capable of the job.
Joel Spolsky is right, hiring badly is destructive to a team and organization. It should be avoided at all costs.
The more I think about it, the more I begin to think good professional developers must be good communicators - in their code and with people. Think of the old saying - the more you know, the more you realise you don't know.
That's not to say you want somebody who isn't confident: but neither do you want someone that is cocky and unwilling to interact with others.
Recently someone asked about whether they should become a programmer in this posting. No matter how a programmer starts out they will likely learn from many mistakes they've made and as a result have an element of humility about themselves and development in general.
A good programmer continues to learn and keeps a relatively open mind.
"Over 8 years of experience in Linux using C/C++" is a fairly vague requirement without reasons for the time length. What are the specific reasons for that time length? Would you prefer more C/C++ experience if some of it were BSD or Solaris or other Unix? Would you prefer less time or a wider experience with different distributions; would you prefer 5 years experience with Red Hat or 7 years experience spanning Red Hat, Debian, SUSE, Gentoo, and others. What are you trying to get from the person you hire, that relates to the amount of time?
The best way to judge a candidate, any candidate, is on how well he can do the job, not how good the qualifications are. You mentioned Lead Developer, owning a product feature and eventually new features. What sort of feature? A highly responsive and adaptive UI? A UI-free recursive data mining calculation? Offline document scanning/indexing code? Custom device drivers?
Basic understanding of algorithms is important, but that can be tested easily in a phone interview. The ability to map out an algorithm for problem solving, and clearly state the reasons for preferring one over another is much more useful, and harder to test.
Test his programming skills by asking to write a program is a fairly useful BS indicator test; there are quite a few people who are adept at slinging manure who can't actually write a line of code. Another useful test is to give him some code with a defect and ask him what's wrong with it, and how he would fix it.
To test his understanding of Linux, I would look at a basic BS test; fire up a Linux box and ask him to perform some basic tasks, including maybe write and compile "Hello world". This will identify the BS artists. Then I would just go with some stock test, showing that he understands the basics of the Linux design; some file system knowledge, some knowledge of tools, ask about how he would add removable device permissions for a user using SE Linux, how he'd configure access to an application that needs elevated privileges so users without those privileges can use the application.
But ultimately, these are all pretty generic ideas; IMHO, it's much more useful to think in terms of "what do we want the candidate to accomplish", than "how do we test basic skills".