Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

This does it in-place

public static void AlternateArray(int[] integer_array)
        {
            int[] alt_int_array = new int[integer_array.Count()];

            for (int i = 0; i < integer_array.Count(); i++)
            {
                int value = integer_array[i];
                /*Even iteration. Get +ve at this index*/
                if (i % 2 == 0)
                {
                    if (integer_array[i] < 0)
                    {
                        int posit_index = GetFirstPositiveIndex(i, integer_array, true);

                        if (posit_index > -1)
                        {
                            AdjustArray(i, posit_index, integer_array);
                        }
                    }

                }
                else
                {
                    if (integer_array[i] > 0)
                    {
                        int neg_index = GetFirstPositiveIndex(i, integer_array, false);

                        if (neg_index > -1)
                        {
                            AdjustArray(i, neg_index, integer_array);
                        }
                    }
                }

            }

        }

        public static void AdjustArray(int start_index, int end_index, int[] intger_array)
        {
            for (int i = end_index; i > start_index; i--)
            {
                int temp = intger_array[i];
                intger_array[i] = intger_array[i - 1];
                intger_array[i - 1] = temp;
            }
        }

        public static int GetFirstPositiveIndex(int start_index, int[] integer_array, bool get_pos)
        {
            int first_pos_index = -1;
            for (int i = start_index; i < integer_array.Count(); i++)
            {
                if (get_pos)
                {
                    if (integer_array[i] > 0)
                    {
                        return i;
                    }
                }
                else
                {
                    if (integer_array[i] < 0)
                    {
                        return i;
                    }
                }
            }

            return first_pos_index;

        }

- Sohaib December 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically for each index, we search for right item (next positive/next negative), move it to the right place and shift the array to the right. After this we are back to the beginning since the order of the array is reserved.

Quick Python code to illustrate:

def right_index(arr, start, side):
	for i in range(start, len(arr)):
		if arr[i] * side > 0:
			return i
	return None

def shift_right(arr, start, end):
	for i in range(end, start, -1):
		arr[i] = arr[i-1]


def alternate(arr, start, side):
	if start == len(arr):
		return arr

	target = right_index(arr, start, side)
	if target is not None:
		# swap
		temp = arr[target]
		shift_right(arr, start, target)
		arr[start] = temp
		return alternate(arr, start + 1, -side)
	else:
		return arr
		
# start with positive side, we can also check the first item to know which side to start
def alter(arr):
	return alternate(arr, 0, 1)

- chau December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you sure it works in O(N) time?

- glebstepanov1992 December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void alternateArray(int A[], int n, bool isPositive=true){
    if(A==nullptr || n < 1) return;
    if(isPositive){
        int i=0;
        while(i<n && A[i]<0)
            i++;
        if(i==n) return;
        while(i>0){
            A[i] ^= A[i-1];
            A[i-1] ^= A[i];
            A[i] ^= A[i-1];
            i--;
        }
        alternateArray(A+1, n-1, false);
    } else {
        int i=0;
        while(i<n && A[i]>0)
            i++;
        if(i==n) return;
        while(i>0){
            A[i] ^= A[i-1];
            A[i-1] ^= A[i];
            A[i] ^= A[i-1];
            i--;
        }
        alternateArray(A+1, n-1);
    }
}

- simon.zhangsm December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution for the easier case of using extra space. Should be self-explanatory.

class AlternateSigns {

	static void rearrange(int[] arr) {
		LinkedList<Integer> positives = new LinkedList<Integer>();
		LinkedList<Integer> negatives = new LinkedList<Integer>();
		for(int i : arr) {
			if(i > 0)
				positives.add(i);
			else negatives.add(i);
		}
		for(int i=0; i<arr.length; i++) {
			if ((i%2 == 0 && positives.size() > 0) ||
					(i%2 == 1 && negatives.size() == 0)) {
				arr[i] = positives.remove();
			} else {
				arr[i] = negatives.remove();
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[args.length];
		for(int i=0; i<args.length; i++) {
			arr[i] = Integer.parseInt(args[i]);
		}
		rearrange(arr);
		for(int i : arr)
			System.out.print(" " + i);
	}
}

- Sunny December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution without using additional space (other than to create a few variables). Idea is same as other people.

class AlternateSigns {

	static void rearrange(int[] arr) {
		int len = arr.length;
		for(int i=0; i<len; i++) {
			if((i%2 == 0 && arr[i] > 0) || (i%2 == 1 && arr[i] < 0))
				continue;
			int j=i+1;
			while(j<len) {
				if((arr[i] > 0 && arr[j] < 0) || (arr[i] < 0 && arr[j] > 0))
					break;
				else j++;
			}
			if(j>=len)
				break;
			int tmp = arr[j];
			while(j>i) {
				arr[j] = arr[j-1];
				j--;
			}
			arr[i] = tmp;
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[args.length];
		for(int i=0; i<args.length; i++) {
			arr[i] = Integer.parseInt(args[i]);
		}
		rearrange(arr);
		for(int i : arr)
			System.out.print(" " + i);
	}
}

- Sunny December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$data=array(1,5,-5,-6,88,11,23,35,-44,98,89);
$rs=array();
$temp=array();
for($j=0;$j<count($data);$j++){
for($k=0;$k<count($data);$k++){
if(empty($rs) && $data[$k]>0){
$rs[]=$data[$k];
break;
}
if(end($rs)>0 && $data[$k]<0 && !in_array($data[$k],$rs)){
$rs[]=$data[$k]; //-VE
break;
}else if(end($rs)<0 && $data[$k]>0 && !in_array($data[$k],$rs)){
$rs[]=$data[$k]; //+VE
break;
}
else if(!in_array($data[$k],$temp)){
$temp[]=$data[$k];
}
}
}
for($j=0;$j<count($temp);$j++){
if(!in_array($temp[$j],$rs)){
$rs[]=$temp[$j];
}
}

- aman December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$data=array(1,5,-5,-6,88,11,23,35,-44,98,89); // o/p = {1,-5,5,-6,88,-44,11,23,35,98,89}
$rs=array();
$temp=array();
for($j=0;$j<count($data);$j++){
	for($k=0;$k<count($data);$k++){
		if(empty($rs) && $data[$k]>0){
			$rs[]=$data[$k];
			break;
		}
		if(end($rs)>0 && $data[$k]<0 && !in_array($data[$k],$rs)){
			$rs[]=$data[$k]; //-VE
			break;
		}else if(end($rs)<0 && $data[$k]>0 && !in_array($data[$k],$rs)){
			$rs[]=$data[$k];  //+VE
			break;
		}
		else if(!in_array($data[$k],$temp)){
			$temp[]=$data[$k];
		}
	}
}
for($j=0;$j<count($temp);$j++){
	if(!in_array($temp[$j],$rs)){
		$rs[]=$temp[$j];
	}
}

- tom December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pretty ugly javascript solution. But it does the job. O(1) space and O(n) time. I think if these were put on a kmap, it can look a lot prettier, but also much harder to understand.

function sortInAlternatingWay(list) {
		var posPosition = 0;
		var negPosition = 0;
		var tmpPositive = [];
		var tmpNegative = [];

		for (var i = 0; i < list.length; i++) {
			// find next positive and negative numbers
			posPosition = findNextPosNumPos(list, i);
			negPosition = findNextNegNumPos(list, i);

			if (i % 2 == 0) { // this position is suppose to be positive
				if (list[i] == 0) { // this position is currently empty
					if (tmpPositive.length != 0) { // use temporarily stored positive number if exist
						list[i] = tmpPositive.shift();
					} else if (posPosition != -1 && posPosition != i) { // use next positive number if available
						list[i] = list[posPosition];
						list[posPosition] = 0;
					} else if (tmpNegative.length != 0) { // if no more positiveNumbers are left, use the negatives, use tmp first
						list[i] = tmpNegative.shift();
					}


				} else if (list[i] < 0) { // this position currently holds a negative number
					if (tmpPositive.length != 0) {
						tmpNegative.push(list[i]);
						list[i] = tmpPositive.shift;
					} else if (posPosition != -1 && posPosition != i) {
						tmpNegative.push(list[i]);
						list[i] = list[posPosition];
						list[posPosition] = 0;
					} else if (tmpNegative.length != 0) {
						var tmp = list[i];
						list[i] = tmpNegative.shift();
						tmpNegative.push(tmp);
					}


				} else { // this position currently holds a positive number
					if (tmpPositive.length != 0) {
						var tmp = list[i];
						list[i] = tmpPositive.shift();
						tmpPositive.push(tmp);
					}
				}


			} else { // this position is suppose to be negative
				if (list[i] == 0) { // this position is currently empty
					if (tmpNegative.length != 0) {
						list[i] = tmpNegative.shift();
					} else if (negPosition != -1 && negPosition != i) {
						list[i] = list[negPosition];
						list[negPosition] = 0;
					} else if (tmpPositive.length != 0) {
						list[i] = tmpPositive.shift();
					}
				} else if (list[i] < 0) { // this position currently holds a negative number
					if (tmpNegative.length != 0) {
						var tmp = list[i];
						list[i] = tmpNegative.shift();
						tmpNegative.push(tmp);
					}
				} else { // this position currently holds a positive number
					if (tmpNegative.length != 0) {
						tmpPositive.push(list[i]);
						list[i] = tmpNegative.shift();
					} else if (negPosition != -1 && negPosition != i) {
						tmpPositive.push(list[i]);
						list[i] = list[negPosition];
						list[negPosition] = 0;
					} else if (tmpPositive != 0) {
						var tmp = list[i];
						list[i] = tmpPositive.shift();
						tmpPositive.push(tmp);
					}
				}
			}
		}
	}

- Tiffany December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Objective C solution
    NSArray *numbersArray = @[@(2),@(3),@(-4),@(-9),@(-1),@(-7),@(1),@(-5),@(-6)];
    NSMutableArray *positiveNumbersArray = [NSMutableArray new];
    NSMutableArray *negativeNumbersArray = [NSMutableArray new];
    NSMutableArray *resultsArray = [NSMutableArray new];
    [numbersArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        if ([obj integerValue] >0) {
            [positiveNumbersArray addObject:obj];
        }else{
            [negativeNumbersArray addObject:obj];
        }
    }];
    NSInteger minArrayCount = positiveNumbersArray.count<negativeNumbersArray.count?positiveNumbersArray.count:negativeNumbersArray.count;
    for (int i = 0; i<minArrayCount; i++) {
        [resultsArray addObject:positiveNumbersArray[i]];
        [resultsArray addObject:negativeNumbersArray[i]];
    }
    if (positiveNumbersArray.count>negativeNumbersArray.count) {
        for (NSInteger j = minArrayCount; j<positiveNumbersArray.count; j++) {
            [resultsArray addObject:positiveNumbersArray[j]];
        }
    }else{
        for (NSInteger j = minArrayCount; j<negativeNumbersArray.count; j++) {
            [resultsArray addObject:negativeNumbersArray[j]];
        }
    }
    NSLog(@"Final output array : %@",resultsArray.description);

- Anonymous December 09, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More