Hopefully I'm not breaking any rules, but posting this to offer my contribution to the community and hopefully help any aspiring Amazonians. Just took the Amazon OA a few days ago and the questions I got were VERY similar to the following:
So sliding window and greedy algorithm
Good luck!