How would you evaluate the candidates?
As sundialsvc4 wrote: by checking how the person behaves in the teams. Including how enthusiastically the candidate talks about the different aspects of that role. (And a bit by talking about algorithms.)
And I agree to that approach. In my eyes, that way gives you sufficient information if the person will be suitable for the job you have to offer.
And if you really, really fail on someone who is only great doing job interviews, you would soon discover and then fire the impostor...
So long, Rata
It's impossible to know fully how someone performs in a team without interviewing their former team(s)—which is largely impossible, against corporate policies today due to the litigious nature of the game—and knowing your own team extremely well; not every player is a match for every team. A terribly genial "interpersonal" person who exhibits all the textbook signs of "team player" can destroy a team's morale with incompetence, interference, lack of discipline, focus, memory, tool adoption…
Bad hires are extremely expensive in tech and can be disastrous for a project/team. In modern corporate, and highly regulated business, environments firing someone can take months or even a year because the only thing more expensive than a bad hire is a wrongful termination lawsuit.
Even if you could interview their former team, you might not discover the real reason they didn't get along. "Can you believe that guy wanted us to use source control?"
You are entirely correct that Human Resources departments everywhere have been Properly Lectured by their Lawyers ... and that they formally re-play those Lectures to each and every hiring manager. (I have dutifully and politely sat through a great many of those Official Lectures.) You are likely to only get “employment verification.” from any Former Employer, because that is the only thing that they are (maybe-)obliged to give. Nevertheless, I find that, if you engage a candidate in simple, human conversation, and if you can persuade the poor soul to “just relax,” then you can fairly quickly get a sixth-sense about the candidate’s personality and probable level of technical knowledge.
I would stress – and stress again – that “level of technical knowledge” is not the main thing that I personally look for! “I can teach any a*shole how to write a computer program” ... (I used to teach college courses, remember?) ... but I don’t want an a*shole on my team! :-D
Furthermore, I know that “how we do things ‘here’ is unlike any and every other place where you have hung your hat.” I know that I am going to have to teach you a lot of new things ... and I need to know that you are willing to
shut up and learn.
Now, I do not hire “newbies straight out of college.” (That is to say, I’ve never had to.) Academia unfortunately teaches you that you must do everything yourself (calling it “cheating” when you don’t), and it grades you only as an individual, for what you have stuffed into your head. (Current American practice also tells you that everything in life is a multiple-choice test, but I digress.) The real working-world is not at all like that. You work as a team, you collaborate, and you have reference sources readily at-hand. If you don’t have the answer, someone else on your team probably does ... or, can get it for you. (I always lay-down the “five minute rule,” which says, “if you’re stuck for more than five minutes, ask.”) No one is a rock-star. Good teamwork produces something that is much bigger than the sum of its parts. But, there are a lot of “good programmers™” out there who have absolutely no idea how to do it.