[Interview Question] Police and Thief

I came across this question today and found it interesting (it was mentioned somewhere that this question was asked in a Microsoft interview). You are given an array of size n...