For my address problem, here's a couple of things I want to see:
* You can look an address and identify the different parts
* You can come up with simple ways to split up the address. Most people start off with saying "Well, there's a comma after the street and a comma after the city, and then state and ZIP have a space in between, so if I split it up like that, I have all the parts."
* You can tackle more difficult addresses (i.e., What do you do if there are no commas? If someone leaves off a ZIP code?) Bonus points if you consider these things before you bring them up
* Actually write an algorithm to solve it. This is a little more involved, but basically, the way you write the algorithm tells me things about what you know. If you choose to use regular expressions, that tells me you're confident enough with regular expressions to use them in an interview. If you decide to explode the string and work word by word, that tells me something else. If you decide to work left to right, right to left, etc. If you make assumptions or not, that tells me things.
The great thing about addresses is that the format is pretty standard and everyone pretty much understands the nuances of it. For instance, what kind of ZIP codes are there? What are the possible values for a state? Given this knowledge, you should be able to make some assumptions and very easily figure out where State and ZIP are, or if they're even present.
You'd be surprised how many people never get that far, even with hints and prompting from me. They'll stop at the comma thing, or they'll say "I'd use machine learning" like that's a magic wand of some kind.
More importantly, when I introduce edge cases they hadn't considered, how do they change the algorithm? Is it a minor change, or do they have to go back to square one? Some edge cases dramatically change the entire situation.
And then there are some really tricky cases. For instance, if you decide to make the (perfectly valid) assumption that streets end in a suffix (e.g., "Street", "Avenue", "Boulevard" or their abbreviations) and then decide to split the string there with the street on the left and the city/state/ZIP on the right, that sounds like a good idea. But what if it's "123 Main St W"? How does that change things? And then imagine that you have "123 Main St West Palm Beach FL"... does that West belong with the street or the city? What if there's also a "123 Main St Palm Beach FL"? How does that change things?
And so on. Most of the time, people solve the simple thing. Then as I add edge cases, I want to see how they solve them. Usually this takes about 15, 20 minutes total. The best candidates wind up getting close enough to the way I did it when I first solved the problem. (I've since then solved for all of these edge cases, but that took me months.)
I don't really care about the exact solution. If you get stuck at the part without commas, that's okay, I'll skip it and give another edge case. I just want to see how you think, how you solve the problem.
I can teach you Python or Ruby or PHP. I can teach you the syntax necessary to parse a string. What I can't and don't have time to do is teach you how to solve problems. The programming bit is trainable. The problem solving bit... not so much.