Re: How many bytes per Italian character?
Doug Harrison [MVP] wrote:
This what I came up with
template<class T> void Rotate(std::vector<T>& a, int n)
{
size_t M = a.size();
if(M <= 1) return;
size_t N = ( n >= 0 ? n%M : M - 1 - (-1 - n)%M );
size_t m = 0; // running number of correct entries
for(size_t i = 0; m < M; i++, m++)
for(size_t j = (i + N)%M; j != i; j = (j + N)%M, m++)
std::swap(a[i], a[j]);
}
GCD is maybe lurking in there somewhere, but not explicitly.
Good job. Here's the trick answer:
template<class T> void Rotate2(std::vector<T>& a, int n)
{
// Parameter validation omitted.
if (n < 0)
n = -n;
else
n = a.size()-n;
std::reverse(a.begin(), a.begin()+n);
std::reverse(a.begin()+n, a.end());
std::reverse(a.begin(), a.end());
}
And I was worried that using std::swap() was cheating...
The trick answer is cute, but being forced to come up with that could
lead to a very long interview...
Given that any method must reduce to a sequence of swaps (true I think),
I believe my brute force method uses the minimum possible number of
swaps. Each swap places one entry in the correct position, except for
the last swap in each cycle, which places two entries. (this is why m++
appears in both loops).
--
David Wilkinson
Visual C++ MVP