Not to mention in a short window like 30min or less in interview?
I highly doubt that.
This is the kind of problem that if you haven't seen it before, you won't be able to answer it in interview anyway.
So basically there is no point to have a problem like this in interview.
@ayuanx Agree! The idea to compress search space is easy to get, but the stack based method is very hard to buildup. I can only find O(n^2) solution for this problem in an interview time window. :(