Yup, my experience is that FizzBuzz level complexity is roughly what you want for interview problems. I find that and some questions about algorithms and data structures tell you all you need to know.