How to rotate an array by a particular amount, require best time and space complexity.

Question

vs · Accepted Answer

Working solution in C++:

/*
	Rotate vector x [n] left by d positions.
	For n=8 and d=3, change abcdefgh to defghabc (123456789 to 456789123)
	Constraints: O(n) time, O( 1 ) extra space.
*/

#include 

using namespace std;

void reverse(int arr[], int start, int end)
{
	const int mid = (start + end)/2;
	for (int i = start, offset = 0; i <= mid; ++i, ++offset)
	{
		const int temp = arr[i];
		arr[i] = arr[end-offset];
		arr[end-offset] = temp;
	}
}

void rotateArr(int arr[], int n, int d)
{
	// 1. Rotate the entire array
	reverse(arr, 0, n-1);

	// 2. Rotate 0 to k-1
	const int k = (n-d);
	reverse(arr, 0, k-1);

	// 3. Rotate k to n-1
	reverse(arr, k, n-1);
}

int main()
{
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	const int size = sizeof(arr)/sizeof(int);

	cout << "before:
";
	for (int i = 0; i < size; ++i)
		cout << arr[i] << " ";
	cout << endl << endl;

	// rotate
	int d = 3;
	rotateArr(arr, size, d);
	
	cout << "after:
";
	for (int i = 0; i < size; ++i)
		cout << arr[i] << " ";
	cout << endl << endl;
}

Anon · Answer

This is a very common question in interviews.  It's from Programming Pearls, and the idea is to rotate the entire array first, then rotate from 0 to k-1 (where k is the number of rotations that you want to do) then rotate from k to n-1 (i.e., the rest of the array).

It almost works like magic; try it out on a sheet of paper and it's much easier to grasp.

Google

Pregunta de entrevista de Google

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo