From afar, it sounds like a translation of your posts are "I'm not familiar with BST, that's unfair. I'd rather a real world problem like the one I'm familiar with". As someone who never works with addresses, while reading over your various descriptions of the sub-problems I think your familiarity with the problem is clouding your judgement on the "very easily" parts, at least as compared to the original BST problem space (i.e. "someone can figure out what's necessary in ~10 mins in a high pressure situation).
Perhaps that's unfair of me but I don't see how your arbitrary problem which is fairly simple in the standard case but with a variety of interesting edge cases is any different than his problem of a similar description.
Sorry for the rant. I just hate addresses.
Don't even get me started on the Virgin Islands or Puerto Rico...
But for the purposes of the interview question, there are "perfectly valid" assumptions that you can make to solve the task before you. I'm not asking you to solve the entire scope of the problem -- I've been working on this for over a year with varying degrees of commitment, and I assure you I have not solved the entire scope of the problem. I don't expect you to figure it out in 15 minutes.
You can assume that there are 50 states (but that leaves out the Virgin Islands and Puerto Rico). You can assume that ZIP codes have 5 digits (but maybe someone provided all 9 digits, or maybe they left it off completely). You can assume that all streets end in a reasonable suffix (but that ignores post-directional suffixes or the examples you provided).
However, by making assumptions, you can more quickly solve the problem in an interview context. As long as I understand the assumptions you're making, I can judge the quality of your output. It won't solve everything, but maybe it's better to parse 99% of addresses using one simpler algorithm and then handle the edge cases using a second (or third, or fourth, or fifth) algorithm.
More importantly: street addressing was added to support the crude technology of the time (paper maps & phone books) -- with computers we should become MORE amenable to the vagaries and desires of humans rather than changing humans to fit the machines.
But yes, you're right. :)
* 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.