I was asked the same question. I was told that it was not the efficiency of the algorithm that I should care about but the cleanliness and readability of the code. I used a naive brute force approach for the problem and the interviewer was satisfied.