Class challenges I found extremely easy, beat both on first try. Heroic had to try a few times and see which deck worked best.
For Anubrekhan, I used control paladin, took a few tries, needed to draw certain cards(mostly both my equalities) to stay in the game and then overpower him with larger minion and a fuckton of self healing.
For Faerlina I also used control paladin at first and almost got her on one try(she literally got perfect lethal with 2x Hellfire and she had 1hp left after, fucking whore) then I switched to rush paladin instead, basically dumped my hand in the first 3 turns and then was playing turn by turn, had some good draws like sword of justice and equality. Played Blessing of Might, Humility, the secret that reduces mobs to 1hp and the usual 2/1 secret, she basically didn't get to use her hero power for the entire game which made things a lot easier.
For Maexxna I tweaked my control druid a bit and easily beat her, key was getting both a swipe and starfall in the first few turns to clear all her fucking spiders shit then abusing keeper of the grove, farseer shaman, pyromancer and druid of the claw on charge and her hero power being played every turn. Far seer probably healed me for 30 or so and I used keeper of the grove to clear both the 4/6 since they can be targetted by battlecries, was pretty funny. Ended up losing a lot of cards due to hand too full but if you have 2keepers 1farseer and 2 druids game's pretty much over since every turn you can do 8damage or clear whatever they play then heal up, only issue is cleaning her initial board with all the spiders that's why agressively mulliganed for swipe+starfall.