I applied for positions on the Google Jobs site that I seemed qualified for. After a few weeks, I received an email from a recruiter asking if I was interested in a phone interview.

The phone interviewer was nice but really wasn't interested in my background or general knowledge; they just wanted to work through a technical question in Google Docs. I did not recognize the problem as recursive and told the interviewer I would start with a simple, inefficient solution and try to think of a better one as I progressed. I was very nervous and couldn't really think clearly in such situations.

Anyway, the interviewer gave me a hint that the solution was recursive, so I reworked the function and created a recursive version. Then I was asked to provide test variations, which I seemed to think of pretty well. I was told that I provided all the ones the interviewer could think of.

Given a string of '1', '0', or '?', print out the combinations. Treat '?' as a wildcard which could be '0' or '1'.