The Idea here is to complete the quest while also reducing the cost of a rhino with a scarlet webweaver. Once that is done, just throw everything you have at your opponent, use the quest reward hero power and obliterate your opponent!

To achieve this, the deck runs snake trap, unleash the hounds, locust swarm and the new desert spear! the quest shouldn't take to long to complete. 

There are many forms the OTK itself can take as long as some of your minions are reduced in cost. the most common way in my opinion would be:
Tundra Rhino + Hyena Alpha + Timber Wolf + 2 lynxes and a hero power to finish. Either Rhino or Hyena has to be reduced in cost
If you do worry about having a secret up in the late game, another way would be to just use the rhino, both timberwolves and Swarm of Locusts. 

I'm sure there are many ways to end your opponent pretty consistently, it really just depends what cards you get to play for free.