I can tell within 10 minutes if someone is genuine or not just by talking through real, representative scenarios. If the job really involved implementing red-black trees from scratch, then and only then bring it up!