This is an Amazon Interview Question for Software Engineer/Developer from careercup.
"Given an array of positive and negative numbers(no zeroes),i have to arrange them in such a way that the positive and negative numbers should be arranged consecutively.The number of positive and negative numbers may not be equal i.e. if there is no positive number(or negative) left,then all the remaining negative numbers(or positive) are appended to the end of the array.The order is important i.e.if input array is { 2,-1,-3,-7,-8,9,5,-5,-7},then the output array should be {2,-1,9,-3,5,-7,-8,-5,-7}.The code is done in O(n) without using another array.I came up with a solution in which i chose 0 as pivot element and separate the numbers (using quicksort) but in this case the order is not preserved."
2. Solution
As the interview requested, the solution has computation complexity of O(N) and space complexity of O(1). The idea is to have two trackers and one indicator. The two trackers, one is to track the next to the position that is in the order so far, and the other is track the current value to explore. Call the two trackers "OutOfPlaceTracker" and "CurrentPlaceTracker". The indicator is to indicate what value is to find, negative or positive, or what value is needed in the position of OutOfPlaceTracker. Call this indicate as "IsPostiveValueToFind".
When the size of the array is less than 3, then no need any work because all the elements are already in right place. When the array has more than 2 elements, then there are two scenarios in this cease.
Scenarios 1: both trackers points to the same position
This scenario is always the starting point, because the first element is always in the right place. Both trackers are pointing to the second elements. Set the indicator "IsPositiveValueToFind", true/false, if the first element is negative/positive.
- If the CurrentPlaceTracker points a value that the indicator wants, then both trackers moves one step ahead. Flip the indicator and go into Scenario 1 again.
- If the CurrentPlaceTracker points a value that the indicator does NOT want, then OutOfPlaceTracker stays still and the CurrentPlaceTracker moves one step ahead. Then go into Scenario 2.
Scenario 2: CurrentPlaceTracker is ahead of OutOfPlaceTracker
This scenario happens when negative/positive values appears in row.
- CurrentPlaceTracker moves ahead and OutOfPlaceTracker stays still until CurrentPlaceTracker points to a value that the indicator likes.
- Save the element that CurrentPlaceTracker points to into a temporary variable. Shift the memory from position [OutOfPlaceTracker, CurrentPlaceTracker - 1] to [OutOfPlaceTracker + 1, CurrentPlaceTracker] in the right direction by one step.
- Save the temporary variable into where OutOfPlaceTracker points to
- OutOfPlaceTracker moves ahead 2 steps and CurrentPlaceTracker moves ahead 1 step
- If both trackers point to the same location, go to Scenario 1
- If CurrentPlaceTracker is ahead, then go to Scenario 2
- (CurrentPlaceTracker can NOT be behind)
Continue Scenario 1 or Scenario 2 until CurrentPlaceTracker reaches the end of the array.
The above picture shows how the two trackers and indicator update as this solution works on the example shown on an Amazon Interview Question for Software Engineer/Developer from careercup
3. C++ Implementation
// Implementation
//********************************************************************************
#include <vector>
#include <cassert>
template<typename type>
void OrderArrayIntoNegativePositiveSeries(std::vector<type>& arr)
{
if (arr.empty()){
return;
}
const size_t SizeOfArr = arr.size();
if (SizeOfArr < 3) {
return;
}
// if first value is negative, then find a positive value next
bool positiveValToFind = arr[0] < 0;
type nextValue;
for (size_t outOfOrderPos = 1, curIndex = 1; curIndex < SizeOfArr; ++curIndex) {
if ((arr[curIndex] > 0 && positiveValToFind) ||
(arr[curIndex] < 0 && !positiveValToFind)) {
if (outOfOrderPos == curIndex) {
// Scenario 1: curIndex is increment by the for loop
positiveValToFind = !positiveValToFind;
++outOfOrderPos;
}
else {
// Scenario 2: curIndex is increment by the for loop
nextValue = arr[curIndex];
memcpy(&arr[outOfOrderPos + 1],
&arr[outOfOrderPos],
(curIndex - outOfOrderPos) * sizeof(type));
arr[outOfOrderPos] = nextValue;
outOfOrderPos += 2;
}
}
}
}
//********************************************************************************
// Test
//********************************************************************************
void TestCornerCases()
{
std::vector<int> testArr;
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr.empty());
testArr = { 1 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr.size() == 1);
assert(testArr[0] = 1);
testArr = { 1, -1 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr.size() == 2);
assert(testArr[0] == 1);
assert(testArr[1] == -1);
}
void TestCase1()
{
std::vector<int> testArr = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, -8, -5, -7 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr == result);
}
void TestCase2()
{
std::vector<int> testArr = { 2, 9, 5, 3, 2, 1, -1, -3, -7, -8, -5, -7 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, 3, -8, 2, -5, 1, -7 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr == result);
}
void TestCase3()
{
std::vector<int> testArr = { 2, -1, -3, - 7, -8, -5, -7, 9, 5, 3, 2, 1 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, 3, -8, 2, -5, 1, -7 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr == result);
}
void TestCase4()
{
std::vector<int> testArr = { 2, -1, -3, - 7, 9, 5, 3, 2, 1, -8, -5, -7 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, 3, -8, 2, -5, 1, -7 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr == result);
}
void TestCase5()
{
std::vector<int> testArr = { -1, -3, - 7, 2, 9, 5, 3, 2, 1, -8, -5, -7 };
const std::vector<int> result = { -1, 2, -3, 9, -7, 5, -8, 3, -5, 2, -7, 1};
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr == result);
}
void TestCase6()
{
std::vector<int> testArr = { -1, -3, - 7, -8, -5, -7, 2, 9, 5, 3, 2, 1 };
const std::vector<int> result = { -1, 2, -3, 9, -7, 5, -8, 3, -5, 2, -7, 1 };
OrderArrayIntoNegativePositiveSeries(testArr);
assert(testArr == result);
}
//********************************************************************************
No comments:
Post a Comment