Amazon Interview Question Software Engineer / Developers
Country: India
check this one: careercup.com/question?id=5714091033231360
looks like O(1) space + O(n) is impossible. You can't get both.
#include <iostream>
using namespace std;
void swap(int *arr, int i, int pos){
int temp = arr[pos];
arr[pos] = arr[i];
arr[i] = temp;
}
void posAndNegOrdering(int* arr, int size)
{
int posIter = 0;
int negIter = 0;
bool isPos = true;
for (int i = 0; i < size; i++) {
if (posIter < size && negIter < size){
while (arr[posIter] < 0 && posIter < size)
posIter++;
while (arr[negIter] > 0 && negIter < size)
negIter++;
if (isPos){
if (arr[i] < 0)
swap(arr, i, posIter);
isPos = false;
}
else {
if (arr[i] > 0)
swap(arr, i, posIter);
isPos = true;
}
if (posIter <= i + 1)
posIter = i + 1;
if (negIter <= i + 1)
negIter = i + 1;
}
cout << arr[i] << "\t";
}
}
int main()
{
//int arr[] = { 2, -1, 9, -3, 5, -7, -8, -5, -7 };
int arr[] = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
for (int i = 0; i < 9; i++)
cout << arr[i] << "\t";
cout << endl;
posAndNegOrdering(arr, 9);
//for (int i = 0; i < 9; i++)
// cout << arr[i] << "\t";
//cout << endl;
return 0;
}
This program arranges the numbers as mentioned in the order in the o(n) time with out using any space.
Thanks for the code :).The code is working in the above given example that u take but if u change the input array slightly i.e. { 2, -1, -9, -3, -5, 7, 8, 5, -7 },then the output array that comes out after running this code is {2,-1,7,-3,8,-9,5,-5,-7},the order is not preserved because -3 comes before -9 in the output array which is violating the condition.
public class NegativePositive {
public static void main(String[] args) {
int a[]={10,20,30,-5,60,-5,-9,-8,14};
int i=0,j=0;
while(a[j]>0)
j++;
while(a[i]<0)
i++;
for(int k=0;k<a.length;k++)
{
if(i<a.length)
System.out.print(a[i++]+" ");
if(j<a.length)
System.out.print(a[j++]+" ");
while(i<a.length&&a[i]<0)
i++;
while(j<a.length&&a[j]>0)
j++;
}
}
}
In Java
public class RearrangePostivieAndNegative {
public static void main(String[] args) {
int[] arr = {-5, -2, -5, -2, 4, 7, 1, 8, 0, -8};
reArrange(arr);
for(int i:arr)
System.out.print(i+" ");
}
static void reArrange(int[] arr) {
int outOfPlace = -1;
for(int i=0;i<arr.length;i++) {
if(outOfPlace>=0) {
if((arr[i]>=0 && arr[outOfPlace]<0) || (arr[i]<0 && arr[outOfPlace]>=0)) {
rightRotate(arr, outOfPlace, i);
if(i > outOfPlace + 2)
outOfPlace+=2;
else
outOfPlace = -1;
}
}
if(outOfPlace == -1) {
/*Find Out the out of place element.... :) */
if((arr[i]<0 && (i & 0x01)==1) || (arr[i]>0 && (i & 0x01)==0)) {
outOfPlace = i;
}
}
}
}
static void rightRotate(int[] arr , int outOfPlace , int curr) {
int temp = arr[curr];
for(int i=curr;i>outOfPlace;i--)
arr[i] = arr[i-1];
arr[outOfPlace] = temp;
}
}
I plugged it in into my unit tests that I've created to test my solution, and it seem to fail in half the cases.
I am sure that is due to some corner cases, because solution is similar to mine and uses rotate, shift or bubble down (whatever you want to call it).
I would like to know what is order of complexity of all of those solutions? To me they all look like O(N**2), am I missing something?
We iterate 1..N and on each iteration we potentially swapping N/2 elements, that IMHO gives O(n**2).
Here is a silly solution. I don't think I got O(N), feels more like O(N**2). I am not posting utility class, just reorder function.
@Override
public void reorder(int[] input) {
//index to start search for opposite sign
//0 - last positive element index
//1 - last negative element index
int nextIndexStart [] = {0,0};
for(int i=0; i < input.length; i++)
{
if(ReorderUtils.inPlace(input, i))
{
logger.debug("In order i = {} ", i);
continue;
}
logger.debug("Out Of order i = {} ", i);
//adjust start of the search index
//use last cached index or current, whichever is greater
int iModTwo = i%2;
int start = Math.max(nextIndexStart[iModTwo],i);
int signToFind = (iModTwo==0)?1:-1;
logger.debug("Looking for sign = {} starting from {} index {}", signToFind, start, i);
//find number with the desired sign
while(start < input.length)
{
//if we did find right signed number - we are done with the loop
if(ReorderUtils.isSameSign(input[start], signToFind))
break;
start++;
}
//save last index of found number of the desired sign.
//optimization for search
nextIndexStart[iModTwo] = start+1;
//bubble down desired number - preserves order
if(start < input.length)
{
logger.debug("Found swap index = {} value = {}", start, input[start]);
while(start > i)
{
logger.debug("Swap index {} with {} v {} with {}", start-1, start, input[start-1], input[start]);
ReorderUtils.swap(input, start, start-1);
start--;
}
}
else
{
//if we did not find desired signed number - exit. Array is inorder at this time!
logger.debug("DID NOT FIND TO SWAP index={}",i);
break;
}
}
}
O(1)-space but not sure O(N) time-complexity solution:
void sortNumbers(vector<long> &data)
{
size_t j;
long tmp;
for (size_t i = 0; i < data.size(); i++) {
if (data[i] < 0 && data[i + 1] < 0) {// Look for positive number
for (j = i + 1; j < data.size() && data[j] < 0; j++);
if (j == data.size())
break;
// Shift i+1 to j-1
tmp = data[j];
for (size_t k = j; k > i; k--)
data[k] = data[k - 1];
data[i + 1] = tmp;
} else if (data[i] > 0 && data[i + 1] > 0) {// Look for positive number
for (j = i + 1; j < data.size() && data[j] > 0; j++);
if (j == data.size())
break;
// Shift i+1 to j-1
tmp = data[j];
for (size_t k = j; k > i; k--)
data[k] = data[k - 1];
data[i + 1] = tmp;
}
}
}
Can you explain how this is O(N)?
For every element in the array, you might run to the end of the array trying to find a negative/positive value. That's O(N^2).
Think about an array that contains only positive values.
public static void arrangePositiveNegative(int[] num){
Queue<Integer> negativePtr = new LinkedList<Integer>();
Queue<Integer> positivePtr = new LinkedList<Integer>();
int ptr = 0, i = 0;
while(i<num.length){
if(i<num.length){
if(num[i] > 0){
positivePtr.offer(num[i]);
}else{
negativePtr.offer(num[i]);
}
i++;
}
if(ptr%2 == 0 && !positivePtr.isEmpty()){
num[ptr] = positivePtr.poll();
System.out.println(num[ptr]);
ptr++;
}else if(ptr%2 != 0 && !negativePtr.isEmpty()){
num[ptr] = negativePtr.poll();
System.out.println(num[ptr]);
ptr++;
}
}
while(!negativePtr.isEmpty()){
num[ptr] = negativePtr.poll();
System.out.println(num[ptr]);
ptr++;
}while(!positivePtr.isEmpty()){
num[ptr] = positivePtr.poll();
System.out.println(num[ptr]);
ptr++;
}
}
complexity O(n)
import sys
def main():
list=[2,-1,-3,7,-8,9,5,5,7]
list1=filter(lambda x:(x>0),list)
list2=filter(lambda x:(x<0),list)
list3=[]
j=0
k=0
for i in range(0,len(list)):
if(i%2==0 and j<len(list1)):
list3=list3+[list1[j]]
j=j+1
elif(i%2==1 and k<len(list2)):
list3=list3+[list2[k]]
k=k+1
else:
if(len(list2)>len(list3)):
list3=list3+[list2[k]]
k=k+1
else:
list3=list3+[list1[j]]
j=j+1
print list
print list1
print list2
print list3
main()
public class PositiveNegativeArranger
{
public void OrganiseConsecutively(int[] toSort)
{
int positiveOutOfPosition = GetFirstPositiveOutOfPosition(toSort, 1);
int negativeOutOfPosition = GetFirstPositiveOutOfPosition(toSort, 0);
while (positiveOutOfPosition != -1 && negativeOutOfPosition != -1)
{
swap(toSort, positiveOutOfPosition, negativeOutOfPosition);
positiveOutOfPosition = GetFirstPositiveOutOfPosition(toSort, positiveOutOfPosition + 2);
negativeOutOfPosition = GetFirstPositiveOutOfPosition(toSort, negativeOutOfPosition + 2);
}
}
private void swap(int[] toSort, int first, int second)
{
var temp = toSort[first];
toSort[first] = toSort[second];
toSort[second] = temp;
}
private int GetFirstPositiveOutOfPosition(int[] toSort, int startPosition)
{
for (int i = startPosition; i < toSort.Length; i += 2)
{
if (toSort[startPosition] > 0) return startPosition;
}
return -1;
}
}
int a[] = { 5, 3, 8, -1, -2, 23, 1, -9, 98, -30 };
#define CHKRET \
if (i >= N) { \
break; \
}
void
putinorder (int val, int i, int m)
{
int oldv;
if (i == m) {
a[i] = val;
printf(" ( %d ) ", a[i]);
return;
}
oldv = a[i];
a[i] = val;
printf(" ( %d ) ", a[i]);
i++;
putinorder(oldv, i, m);
}
int
main (int argc, char *argv[])
{
int i, j, m, pos, N, curpos, oldv, neg;
N = sizeof(a)/sizeof(int);
printf("( %d )", a[0]);;
pos = (a[0] > 0);
i = 0;
while (i < N) {
switch (pos) {
case 1:
i++;
CHKRET
pos = (a[i] > 0);
curpos = i;
if (!pos) {
/* Neg is good here */
pos = (a[i] > 0);
} else {
/* Another pos */
m = i;
while ((m < N) && (a[m] > 0)) {
m++;
}
if (m == N) {
printf("Done m %d\n", N);
break;
}
oldv = a[curpos];
a[curpos] = a[m];
printf(" (%d) ", a[curpos]);
curpos++;
putinorder(oldv, curpos, m);
if (i < N) {
pos = (a[i] > 0);
}
}
break;
case 0:
i++;
CHKRET;
neg = (a[i] < 0);
curpos = i;
if (!neg) {
/* Pos is good here */
pos = (a[i] > 0);
} else {
/* Another neg */
m = i;
while ((m < N) && (a[m] < 0)) {
m++;
}
if (m == N) {
printf("Done m %d neg\n", N);
break;
}
oldv = a[curpos];
a[curpos] = a[m];
printf(" <%d> ", a[curpos]);
curpos++;
putinorder(oldv, curpos, m);
if (i < N) {
pos = (a[i] > 0);
}
}
break;
default:
break;
}
}
i = 0;
printf("\n\n\n\n\n");
while (i < N) {
printf(" <<< %d >>> ", a[i]);
i++;
}
}
package gao.zone.study;
import java.util.Arrays;
public class PosNegSortArray {
public static void main(String[] args) {
int[] input = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
int[] expected = { 2, -1, 9, -3, 5, -7, -8, -5, -7 };
sort(input);
System.out.println(Arrays.toString(input));
System.out.println(Arrays.equals(input, expected));
}
private static void sort(int[] arr) {
next_i: for (int i = 0; i < arr.length; i++) {
boolean shouldBeNegative = (i & 1) != 0;
if (arr[i] > 0 ^ shouldBeNegative) {
// 0,2,4,...-> positive. 1,3,5,...->negative.
// condition satisfied.
continue;
}
// arr[i] not correct.
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > 0 ^ shouldBeNegative) {
// first index j satisfied position for index i.
reInsert(arr, i, j);
continue next_i;
}
}
// not found suitable index j.
return;
}
}
private static void reInsert(int[] arr, int target, int pos) {
int t = arr[pos];
System.arraycopy(arr, target, arr, target+1, pos-target);
arr[target] = t;
}
}
public class ArrangArrayPositiveNegative {
public ArrangArrayPositiveNegative() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {2,-1,-3,-7,-8,9,5,-5,-7};
int repIndex=0,temp=0,movIndex=0;
try {
for(movIndex=1;movIndex < a.length;movIndex++)
{
if(( a[movIndex] > 0 && a[movIndex-1] <0) ||
( a[movIndex] < 0 && a[movIndex-1] >0)){
continue;
}
else if((movIndex+1 <a.length)&& ( a[movIndex] > 0 && a[movIndex+1] >0) ){
repIndex=movIndex+1;
while(repIndex < a.length){
if(a[repIndex] <0){
temp=a[movIndex];
a[movIndex]=a[repIndex];
a[repIndex]=temp;
break;
}
else {
repIndex++;
}
}
}
else{
System.out.println("Value of movIndex"+movIndex);
if((movIndex+1 <a.length)&&( a[movIndex] < 0 && a[movIndex+1] <0) ){
repIndex=movIndex+1;
while(repIndex < a.length){
if(a[repIndex] >0){
temp=a[movIndex];
a[movIndex]=a[repIndex];
a[repIndex]=temp;
break;
}
else {
repIndex++;
}
}
}
}
}
//print new string
for(repIndex=0;repIndex<a.length;repIndex++){
System.out.print(""+a[repIndex]);
}
}
catch(ArrayIndexOutOfBoundsException e){
e.printStackTrace();
}
}
}
C# Code below to achieve the result without using additional space
class Program
{
static void Main(string[] args)
{
int[] numbers = new int[] { 2,-1,-3,-7,-8,9,5,-5,-7,12,-15,11,6};
int i=0;
int t = 0;
int temp=0;
Console.WriteLine("Before Processing : ");
for(int j=0;j<numbers.Length;j++)
{
Console.Write(numbers[j]+", ");
}
Console.WriteLine("");
for (i = 0; i < numbers.Length-2; i++)
{
if((Math.Sign(numbers[i])>0) && isEven(i) ||(Math.Sign(numbers[i])<0) && !isEven(i))
{
continue;
}
else if((Math.Sign(numbers[i])<0) && isEven(i))
{
int t1=0; int p1=0;
for(int j=i+1; j<numbers.Length; j++)
{
if(Math.Sign(numbers[j])>0)
{
t1=numbers[j];
p1=j;
break;
}
}
if (p1 > 0)
{
temp = numbers[i];
numbers[i] = t1;
for (int j = p1; j > i + 1; j--)
{
numbers[j] = numbers[j - 1];
}
numbers[i + 1] = temp;
}
}
}
Console.WriteLine("After Processing : ");
for(int j=0;j<numbers.Length;j++)
{
Console.Write(numbers[j]+", ");
}
Console.ReadLine();
}
private static bool isEven(int a)
{
if(a==0)
return true;
else
return ((a%2)==0);
}
}
I am not sure how you achieve this in O(N) O(1) but for those who want to use an extra buffer - the most efficient way I think is to use another array of same size (VS 2 arrays for negative and positive each etc.). In this array, fill the positive indices from start of the array and negative indices from the end. Alternate values can then be retrieved from this array (idxArray) using:
for(int i = 0, j = arr.length - 1, n = 0; n < arr.length; n++) {
int nextIdx = idxArr[n % 2 == 0 ? (i < pc ? i++ : j--) : (j > nc ? j-- : i++)];
...
}
where pc is positive count and nc is negative count
I have an alternate solution different from the ones mentioned above.
Have two index vars i.e one for positive nos and another for negative nos. Both pointing to start of the array. Have a for loop till any one of the counters reaches end of array.
Print the nos in alternate orders[+/- sign] starting with the first element. Increment the counters until you find the one with same sign.
Once any one of the counters reaches deadend of array, there will be only one more index which will still be lagging behind. Now keep on incrementing that particular index and print the sign of numbers that counter points to .
Let me know.
Ask follow up questions to interviewer like can I use another data structure like Queues. If they just wanted to avoid using arrays, then it can be possible by below solutions. Need to be sure before you approach further, since nothing mentioned of doing in O(1) space
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class RearrangeNumbers {
public static void main(String[] args) {
int[] num = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
System.out.println("Initial num is: \n"
+ Arrays.toString(num));
System.out.println("\nAfter Rarranging num is: \n"
+ Arrays.toString(rearrangeNum(num)));
}
public static int[] rearrangeNum(int[] num){
/* Check corner conditions.
* can't rearrange anything with size 1 */
if(num == null || num.length < 2){
return num;
}
// Use Queues, so that we have first in first out (FIFO)
Queue<Integer> posNumQ = new LinkedList<Integer>();
Queue<Integer> negNumQ = new LinkedList<Integer>();
/* Scan through all the num in array and
* store in respective queues. Runs in O(n) time*/
for(int i=0; i<num.length; i++){
if(num[i] >= 0)
posNumQ.add(num[i]);
else
negNumQ.add(num[i]);
}
int index = 0; // use this index to rearrange the values
/* Scan through all the num in array and
* rearrange in respective position. Runs in O(n) time*/
for(int i=0; i<num.length; i++){
if(index % 2 == 0 && !posNumQ.isEmpty()){
num[index] = posNumQ.poll();
index++;
}else if(index % 2 != 0 && !negNumQ.isEmpty()){
num[index] = negNumQ.poll();
index++;
}
}
/* 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. */
while(!negNumQ.isEmpty()){
num[index] = negNumQ.poll();
index++;
}
while(!posNumQ.isEmpty()){
num[index] = posNumQ.poll();
index++;
}
return num;
}
}
private static void consecutiveNumbers(int[] a) {
int i=0;
int currentFlag = 2;
while(i<a.length) {
if(currentFlag == 2) {
if(a[i] > 0) {
currentFlag = 1;
continue;
} else {
currentFlag = 0;
continue;
}
} else if(currentFlag == 1){
currentFlag = doSwapForConditions(a, i, 1);
} else {
currentFlag = doSwapForConditions(a, i, 0);
}
i++;
}
}
private static int doSwapForConditions(int[] a, int i, int oper) {
int j = a.length-1;
int temp;
while(j>i) {
if(oper ==0 ? a[j] > 0 : a[j] < 0) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
break;
}
j--;
}
return oper ==0 ?1:0;
}
Sure, the best way is to use additional structure (array, queue, etc), but there is way to do this with O(1) additional space and O(n) runtime. The trick is to keep 4 pointers: positive, swap positive, negative, swap negative and one cursor. Cursor moves through the array, at each iteration the following invariant is provided: positive and negative pointers point to next positive and negative numbers in the array. "Swap" pointers are used in cases, when we need to swap the next integer (e.g. expected +, but have -, so we swap - to next + and appoint swap negative variable to just moved position). At each iteration swap variable keeps the position of next positive or negative number, that must be placed at next matching cursor position.
This all is difficult to understand, just run the code, see tracing output and you will understand.
If anyone creates data sets, that break the program - will be glad to see.
public class InterleavePosAndNegIntegers {
static int dp, sp, dn, sn;
static int cursor = 0;
static int[] data;
public static void interleave() {
boolean expectedPositive, tail = false;
int N = data.length;
// initialization
dp = -1; sp = -1; dn = -1; sn = -1;
cursor = 0;
expectedPositive = data[0] > 0;
propagatePositive(false);
propagateNegative(false);
while (cursor < N) {
printStats("main" + cursor);
boolean nextPositive = data[cursor] > 0;
// These are good situations: numbers are placed ok - just skipping
if ((tail || expectedPositive) && nextPositive) {
propagatePositive(true);
}
else if ((tail || !expectedPositive) && !nextPositive) {
propagateNegative(true);
}
// Bad situation1:
else if (expectedPositive && !nextPositive) {
swapNegativeWithPositive();
}
else if (!expectedPositive && nextPositive) {
swapPositiveWithNegative();
}
// if positive or negative numbers ended - just propagate the tail
if (dp < 0 || dn < 0) {
tail = true;
}
expectedPositive = !expectedPositive;
cursor++;
}
}
private static void swapNegativeWithPositive() {
assert dn == cursor;
// two swaps: current negative with swapped negative, and then current negative with future positive
if (sn > dn) {
swap(data, cursor, sn);
printStats("neg->pos.0");
}
swap(data, cursor, dp);
// point swap negative pointer to just moved negative number
sn = dp;
printStats("neg->pos.1");
// propagate
propagatePositive(false);
propagateNegative(false);
printStats("neg->pos.2");
}
private static void swapPositiveWithNegative() {
assert dp == cursor;
// two swaps: current positive with swapped positive, and then current positive with future negative
if (sp > dp) {
swap(data, cursor, sp);
printStats("pos->neg.0");
}
swap(data, cursor, dn);
// point swap negative pointer to just moved negative number
sp = dn;
printStats("pos->neg.1");
// propagate
propagateNegative(false);
propagatePositive(false);
printStats("pos->neg.2");
}
private static void propagatePositive(boolean swap) {
// assert dp == cursor;
if (sp > dp && swap) {
swap(data, dp, sp);
}
for (int i = dp + 1; i < data.length; i++) {
if (data[i] > 0) {
dp = i;
return;
}
}
// there is no more positive
dp = -1;
}
private static void propagateNegative(boolean swap) {
// assert dn == cursor;
if (sn > dn && swap) {
swap(data, dn, sn);
}
for (int i = dn + 1; i < data.length; i++) {
if (data[i] < 0) {
dn = i;
return;
}
}
// there is no more negative
dn = -1;
}
private static void printStats(String str) {
System.out.printf("[%s] dn: %d, sn: %d, dp: %d, sp: %d, array: %s\n", str, dn, sn, dp, sp,
Arrays.toString(data));
}
private static void swap(int[] ints, int i, int j) {
int t = ints[i];
ints[i] = ints[j];
ints[j] = t;
}
public static void main(String[] args) {
check(new int[]{-1, -8, -5, -6, 7, 9, -3, 1, 6}, new int[]{-1, 7, -8, 9, -5, 1, -6, 6, -3});
// with tail
check(new int[]{2, 3, -5, 6, 7}, new int[]{2, -5, 3, 6, 7});
// unchanged
check(new int[]{-1, 2, -3, 4, -5, 6, -7, 8}, new int[]{-1, 2, -3, 4, -5, 6, -7, 8});
check(new int[]{1, 5, -2, 3, 7, -3, 6, 6, -2}, new int[]{1, -2, 5, -3, 3, -2, 7, 6, 6});
}
private static void check(int[] input, int[] expected) {
data = input;
interleave();
assert Arrays.equals(data, expected): String.format("Expected: %s\n Result : %s\n", Arrays.toString(expected), Arrays.toString(data));
System.out.println(" OK: " + Arrays.toString(data));
}
}
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. The indicator is to indicate what value is to find, negative or positive, or what value is needed in the position of OutOfPlaceTracker.
This algorithm terminates when the second tracker reaches the end of the array and requires 4 variables (2 tracker, 1 indicator and 1 temp variable) to complete. So this solution is O(N) in computing complexity and O(1) in space complexity.
The whole article including analysis, code and test find here: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-order.html
#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;
}
}
}
}
Are you sure memcpy() takes O(1) time? I always thought it takes O(n) time, in this case you algorithm is O(n^2).
memcpy has much faster performance than for-loop and usually it is target-dependent because most of CPU architecture support chunk memory relocation. Techniques like SIMD and Vectorisation are often used. Memory usage-wise often register and L1/L2 cahces are utilized in extreme with these hardware optimization techniques.
With a linked list data structure it will not have this memory shifting issue. If interested please refer to: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-linked.html
for (int j = 0; j < arr.length; j++) {
if(arr[j]>0)
{
if(arr[0]<0)
{
int k=j;
while(true)
{
if(i==k)
{
i=i+2;
break;
}
else
{
int temp=arr[k-1];
arr[k-1]=arr[k];
arr[k]=temp;
k--;
}
}
}
else
{
int k=j;
while(i<k)
{
int temp=arr[k-1];
arr[k-1]=arr[k];
arr[k]=temp;
k--;
}
i+=2;
}
}
}
This should be an O(1) space and O(n) algorithm as both the for loop and while loop do not run at once for n.
import java.util.Arrays;
public class PositiveNegative
{
public static void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int[] arrangePosNeg(int a[])
{
int start = a[0], index = 0;
for(int i = 0;i < a.length-1; i++)
{
if(a[i] > 0 && a[i+1] > 0) //two consecutive numbers are of same sign
{
index = i + 1;
while(a[index] > 0) // find next number with different sign
{
index++;
if(index >= a.length){
return a;
}
}
swap(a, i+1, index); //swap the 2nd consecutive number with different sign
}
if(a[i] < 0 && a[i+1] < 0)
{
index = i + 1;
while(a[index] < 0)
{
index++;
if(index >= a.length){
return a;
}
}
swap(a, i+1, index);
index = i;
}
}
return a;
}
public static void main(String args[])
{
int[] a = { 2, -1, 9, -3, 5, -7, -8, -5, -7 };
System.out.println("Original" + "\n" + Arrays.toString(a) + "\n" + "Reversed:");
System.out.println(Arrays.toString(PositiveNegative.arrangePosNeg(a)));
}
}
#include<stdio.h>
#include<string.h>
int main()
{
char arr[9]={2,-1,-3,-7,-8,9,5,-5,-7};
int arrsize=9,i,j,k,tmp,chk1=0,chk2=0,p,m;
printf("\n input arr =");
for(i=0;i<arrsize;i++)
{
printf("%d ",arr[i]);
}
for(i=0;i<arrsize;i++)
{
printf("\n i=%d",i);
for(j=i+1;j<arrsize;j++)
{
if(arr[i]<0)
{
if(arr[j]>0)
break;
else{
k=j;
do
{k++; if(k>=arrsize){chk1=1; break;}}while(arr[k]<0);
if(chk1!=1)
{
tmp=arr[k];
m=k-1;
do {arr[m+1]=arr[m]; m--;} while(m>=j);
// arr[k]=arr[j];
arr[j]=tmp;
}
chk1=0;
}
}else if(arr[i]>0)
{
if(arr[j]<0)
break;
else{
k=j;
do {k++; if(k>=arrsize){chk2=1; break;} } while(arr[k]>0);
if(chk2!=1)
{
tmp=arr[k];
m=k-1;
do {arr[m+1]=arr[m]; m--;} while(m>=j);
//arr[k]=arr[j];
arr[j]=tmp;
}
chk2=0;
}
}else;
}
printf("\n arr =");
for(p=0;p<arrsize;p++)
{
printf("%d ",arr[p]);
}
}
/*
printf("\n output arr =");
for(i=0;i<arrsize;i++)
{
printf("%d ",arr[i]);
}*/
printf("\n");
}
#include<stdio.h>
#include<string.h>
int main()
{
char arr[9]={2,-1,-3,-7,-8,9,5,-5,-7};
int arrsize=9,i,j,k,tmp,chk1=0,chk2=0,p,m;
printf("\n input arr =");
for(i=0;i<arrsize;i++)
{
printf("%d ",arr[i]);
}
for(i=0;i<arrsize;i++)
{
printf("\n i=%d",i);
for(j=i+1;j<arrsize;j++)
{
if(arr[i]<0)
{
if(arr[j]>0)
break;
else{
k=j;
do
{k++; if(k>=arrsize){chk1=1; break;}}while(arr[k]<0);
if(chk1!=1)
{
tmp=arr[k];
m=k-1;
do {arr[m+1]=arr[m]; m--;} while(m>=j);
// arr[k]=arr[j];
arr[j]=tmp;
}
chk1=0;
}
}else if(arr[i]>0)
{
if(arr[j]<0)
break;
else{
k=j;
do {k++; if(k>=arrsize){chk2=1; break;} } while(arr[k]>0);
if(chk2!=1)
{
tmp=arr[k];
m=k-1;
do {arr[m+1]=arr[m]; m--;} while(m>=j);
//arr[k]=arr[j];
arr[j]=tmp;
}
chk2=0;
}
}else;
}
printf("\n arr =");
for(p=0;p<arrsize;p++)
{
printf("%d ",arr[p]);
}
}
/*
printf("\n output arr =");
for(i=0;i<arrsize;i++)
{
printf("%d ",arr[i]);
}*/
printf("\n");
}
#include<stdio.h>
#include<string.h>
int main()
{
char arr[9]={2,-1,-3,-7,-8,9,5,-5,-7};
int arrsize=9,i,j,k,tmp,chk1=0,chk2=0,p,m;
printf("\n input arr =");
for(i=0;i<arrsize;i++)
{
printf("%d ",arr[i]);
}
for(i=0;i<arrsize;i++)
{
printf("\n i=%d",i);
for(j=i+1;j<arrsize;j++)
{
if(arr[i]<0)
{
if(arr[j]>0)
break;
else{
k=j;
do
{k++; if(k>=arrsize){chk1=1; break;}}while(arr[k]<0);
if(chk1!=1)
{
tmp=arr[k];
m=k-1;
do {arr[m+1]=arr[m]; m--;} while(m>=j);
// arr[k]=arr[j];
arr[j]=tmp;
}
chk1=0;
}
}else if(arr[i]>0)
{
if(arr[j]<0)
break;
else{
k=j;
do {k++; if(k>=arrsize){chk2=1; break;} } while(arr[k]>0);
if(chk2!=1)
{
tmp=arr[k];
m=k-1;
do {arr[m+1]=arr[m]; m--;} while(m>=j);
//arr[k]=arr[j];
arr[j]=tmp;
}
chk2=0;
}
}else;
}
printf("\n arr =");
for(p=0;p<arrsize;p++)
{
printf("%d ",arr[p]);
}
}
/*
printf("\n output arr =");
for(i=0;i<arrsize;i++)
{
printf("%d ",arr[i]);
}*/
printf("\n");
}
Time - O(n), Space-O(n) is following
take a vector,
navigate each element in the array, maintain one pointer for curpos.
insert the element if of alternate sign, otherwise move next. keep moving until element found.
insert found element with alternate sign in vector.
delete element from the array.
This solultion is simple, does not seem like Amazon type :)
How about this. As you said, without using another array, Can I use hash maps to solve this?
my code
int[] test = {2, -1, -3, -7, -8, 9, 5, -5, -7};
HashMap<Integer, Integer> positiveValue = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> negativeValue = new HashMap<Integer, Integer>();
int j=0,k=0;
for (int i=0; i < test.length; i ++){
if (test[i]<0) {
j++;
negativeValue.put(j,test[i]);
} else {
k ++;
positiveValue.put(k,test[i]);
}
}
int maxVal = Math.max(j,k);
for(int l =1;l<=maxVal;l++) {
if(positiveValue.get(l)!=null)
System.out.println(positiveValue.get(l));
if(negativeValue.get(l)!=null)
System.out.println(negativeValue.get(l));
}
void rearrange(int arr[], int n) { int outofplace = -1; for (int index = 0; index < n; index ++) { if (outofplace >= 0) { // find the item which must be moved into the out-of-place // entry if out-of-place entry is positive and current // entry is negative OR if out-of-place entry is negative // and current entry is negative then right rotate // // [...-3, -4, -5, 6...] --> [...6, -3, -4, -5...] // ^ ^ // | | // outofplace --> outofplace // if (((arr[index] >= 0) && (arr[outofplace] < 0)) || ((arr[index] < 0) && (arr[outofplace] >= 0))) { rightrotate(arr, n, outofplace, index); // the new out-of-place entry is now 2 steps ahead if (index - outofplace > 2) outofplace = outofplace + 2; else outofplace = -1; } } // if no entry has been flagged out-of-place if (outofplace == -1) { // check if current entry is out-of-place if (((arr[index] >= 0) && (!(index & 0x01))) || ((arr[index] < 0) && (index & 0x01))) { outofplace = index; } } } }Source : Geeks4Geeks
- shukad333 September 03, 2014