I know its a bit old problem but still very popular among interviewers. I solved this for one of my interviews and then created a video of the solution I created. Sharing here hoping that it will help other people who are also preparing for the interviews.

There is link to the code of the solution too in the video description.