Question 1

Hint: sort the array in linear time.



Question 2

Hint: first compute the frequency counts, which tells you where the keys need to go. Then cyclically permute the keys into their proper places.



Question 3

Hint: define a fingerprint of a string in such a way that two strings are cyclic rotations of one another if and only if they have the same fingerprint.

Signing bonus: design an algorithm to find the fingerprint of a string of length L in time proportional to L in the worst case.