Here's my current constructed deck, I'm masters 2 atm and have like an 80% win rate with this.
Minions (18):
x2 Mana Wyrm (op value if you can protect them and play them smart, don't play this turn 1 ffs)
x2 Amani Berserker (Enrages are great for Mage since you can use your Hero Power to enable them)
x1 Knife Juggler (great card, counters stealth)
x2 Loot Hoarder (draw power/speed, always trades 2 for 1 pretty much)
x2 Novice Engineer (draw power/speed, always trades 2 for 1 pretty much)
x2 Raging Worgen (Enrages are great for Mage since you can use your Hero Power to enable them)
x2 Shattered Sun Cleric (strong effect)
x1 Dark Iron Dwarf (strong effect)
x2 Argent Commander (best neutral minion in the game)
x2 Azure Drake (draw power/speed, always trades 2 for 1 pretty much, spell damage owns)
Spells (12):
x2 Arcane Missiles (try to use this with Mana Wyrms on the field or Drakes)
x1 Mirror Image (use to protect Mana Wyrms, try to use when Knife Juggler is on the field for a free 2 damage, don't play this turn 1 ffs)
x2 Frostbolt (very strong card)
x2 Cone of Cold (nice AoE)
x2 Fireball (strong)
x2 Polymorph (strong, your get out of jail card, don't waste these)
x1 Pyroblast (your end condition)
Only thing I'd fix in this deck is replace 1 Azure Drake with a Bloodmage Thalnos and my Dark Iron Dwarf with a Sylvanas Windrunner if I ever get them.
Most of your games should end by turn 8.