> If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes

Not with that attitude.