Then I'd argue they need to make that more clear. The typical interview setting does not suggest it's an "exploratory" environment, it usually feels more like taking an exam.

At my last company, we would sit a candidate down at a pairing station. We'd offer them about 5 problems to choose from, and together we'd pair program on the problem for 2 hours. Using the internet, the IDE, anything they want was totally fair game. No system is perfect, but this was by far the best one I've ever experienced.