Visa question

I plan to go back to China in December when I graduate, and hope to work. I already have a company that wants me, but when they called the Beijing work bureau, it said I needed to have two years work experience before getting a permit (prerequisite for a Z visa). So, that kind of visa is out of the picture, I think. Could I go job searching with a tourist visa and then switch once I got hired? Or should I do a business visit visa? I want to be legit, since I plan to stay for some time. What are your guys' suggestions, experiences?