This is a Google interview question for software engineer/developer from careercup. Here is the original thread,
"
3
of 3 votes
Tom works in a warehouse. A billion (1,000,000,000) boxes are arranged in a row. They are numbered from one to one billion (from left to right). Some boxes contain a basketball (at most one basketball in each box). In total, there are N basketballs.Tom wants to organize the warehouse. He would like to see all the basketballs arranged next to each other (they should occupy a consistent interval of boxes). In one move, Tom can take one basketball and move it into an empty box. What is the minimum number of moves needed to organize the basketballs in the warehouse?
Write a function:
class Solution { public int solution(int[] A); }that, given an array A containing N integers, denotes the positions of the basketballs (the numbers of the boxes in which they are placed) and returns the minimum number of moves needed to organize the basketballs in the warehouse.
For example, given: A = [6, 4, 1, 7, 10], your function should return 2 because the minimum number of moves needed to arrange all basketballs next to each other is 2. There are several ways to do it. For example, you could move the ball from the first box to the fifth, and the ball from the tenth box to the eighth. You could also move the ball from the first box to the fifth, and the ball from the tenth box to the third instead. In any case, you need at least two moves.
To be done in O(nlogn) Time complexity and O(1) space complexity
".
2. Data Structure and Algorithm
Give an array of indices of basketball positions, P {p1, p2, ..., pn}. The question is to find the minimum move to arrange the N basketballs into a continuous row.
Pseudo code:
- Sort the array in the ascending order
- Use a window of size N to detect the maximal number of basketballs covered as M
- Then the minimum move is N - M
Use in-place heap sort to sort the array in ascending order and use to pointers to point to the beginning and end of the window. It guarantees O(nlogn) computation complexity and O(1) space complexity. The heap sort used in this blog can be found here - Data Structure and Algorithm - Sort and Binary Search.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
size_t MinimunMovement(std::vector<int> &basketBalls)
{
if (basketBalls.empty()) {
return 0;
}
const size_t NumOfBasketballs = basketBalls.size();
// use in-place heap sort to sort the array
HeapSort().Sort(basketBalls);
// two pointers to point the front and end of window
auto itSlow = basketBalls.cbegin();
auto itFast = basketBalls.cbegin();
auto itEnd = basketBalls.end();
size_t result = 0;
size_t tempResult = 0;
// std::vector<int> copy;
// apply the window to the sorted array to find the
// the maximal number basketballs the window covers
for (; itFast != itEnd; ++itFast) {
if ((*itFast - *itSlow) < NumOfBasketballs) {
++tempResult;
}
else {
if (tempResult > result) {
result = tempResult;
//copy = std::vector<int>(itSlow, itFast);
}
++tempResult;
while ((*itFast - *itSlow) >= NumOfBasketballs) {
++itSlow;
--tempResult;
}
}
}
if (tempResult > result) {
result = tempResult;
//copy = std::vector<int>(itSlow, itFast);
}
// the minimal number of move is the difference
return NumOfBasketballs - result;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestBasketBall()
{
std::vector<int> basketBalls;
assert(MinimunMovement(basketBalls) == 0);
basketBalls = { 6, 4, 1, 7, 10 };
assert(MinimunMovement(basketBalls) == 2);
basketBalls = { 8, 4, 1, 7, 10 };
assert(MinimunMovement(basketBalls) == 2);
basketBalls = { 8, 2, 1, 7, 10 };
assert(MinimunMovement(basketBalls) == 2);
}
