People are not generally answering interview questions based on instinct, but rather based on what they think the interviewer wants to hear to get the job. I would have interpreted this is as a leetcode style algo question and started by treating it as such, even though IRL my first instinct would be "get a lib that does it". Awful, awful strategy.