Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
11
of 15 vote

There are two O(n) solutions for this problem that does not require ordering.

1. You can find the median in O(n) and then rearrange the elements around the median

2. (Better Solution) If you notice the desired ordering, the even numbered elements are bigger (or equal) than the next element, and the odd numbered elements are less than (or equal) than the next element, of course I am assuming the array is 0 offset.

So, you can iterate the array and swap the elements that doesn't match this arrangements,e.g., swap A[i] and A[i+1], when i is even and A[i] < A[i + 1].

- oOZz April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

or swap A[i] and A[i+1], when i is odd and A[i] > A[i + 1].

- oOZz April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Beautiful!

- iroodaz April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 votes

The 2nd solution may not work always. E.g:- It works for (0 1 2 3) giving 1 0 3 2 but for (2 3 0 1) it gives 3 2 1 0 which is incorrect.

- prd April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 votes

Are you sure solution 2 works? Check for this input
8 9 6 7

- srini April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

The median solution looks cool. Find elements greater than the median and put them in even numbered locations. Find elements smaller than the median and put them in odd numbered locations.

- prd April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, the median solution is cool. But what is it's efficiency class? Isn't it quadratic?

- srini April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

No, finding median is O(n). And then we linearly traverse the input array A. If A[i] > median, we put it in a even numbered location in the output array. If A[i] < median, we put it in a odd numbered location. So this will also take O(n) time but O(n) space too.

- prd April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, finding median is O(n). That is fine. My question is about worst case efficiency. How does it perform on this worst case input (1 2 3 4 5 6 7 8 9)?

- srini April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It will still be linear for your input.
The basic code is as follows:-

float median = find_median(a); 
int even = 0;
int odd = 1;
for(int i = 0; i < n ; i++)
{
if(a[i] < median)
{
  b[odd] = a[i];
  odd = odd + 2;
}
else
{
  b[even] = a[i];
  even = even + 2;  
}
}

- prd April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Here is the C++ code for solution 2:

void rearrange(std::vector<int> &A) {
    for (int i = 0; i < A.size(); ++i) {
        if (((i & 1) == 0 && A[i] > A[i +1]) || (i & 1) && A[i] < A[A+1])) {
            std::swap(A[i], A[i + 1])
        }
    }
}

- oOZz April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice solution of swapping adjacent numbers if they don't fit in the arrangement. O(n) solution without any extra space.
How did you come up with this?

- Andy April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Sorry the above code needs a few changes, because I typed too fast:

void rearrange(std::vector<int> &A) {
        for (int i = 0; i < A.size() -1; i++) {
            if ( ((i & 1) == 0 && A[i] < A[i +1]) || ((i & 1) && A[i] > A[i+1]) ) {
                std::swap(A[i], A[i + 1]);
            }
        }
}

@pratik Here are the trace output after each swap for your counter example:
Start:
2 3 0 1
3 2 0 1
3 0 2 1
End: 3 0 2 1

@srini

Start:
8 9 6 7
9 8 6 7
9 6 8 7
End:9 6 8 7

- oOZz April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@pratik, Yes, your above code runs in linear time but uses additional storage which is equal to original array.

- srini April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@oOZz, That's cool. You are right, it runs in linear time. This can also be solved with 3 elements at a time, placing smallest of 3 in the middle position and moving 2 positions right, as I mentioned below. Also, about your solution 1, isn't it quadratic time in worst case?

- srini April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No srini, they are both linear time solutions. In solution 1 you, you first find median in O(n) and then rearrange the elements in O(n), so it's 2 *O(n) , which is O(n) asymptotically, not O(n^2).

- oOZz April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@oOZz, And you mean without using extra storage?

- srini April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I support this solution. just keep checking backward for its right place. Only need update is swap once more if i-1<i<i+1 or other way around. if once more time swap then it will break the order and then it will algo will never look further back. So its still O(n).

- Pankaj April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right. But after two numbers are swapped, don't forget to check if it violate the order of A[i-1] and A[i], it may happen.

- Avaln May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Your solution 2 is the best. @Avaln: you don't need to check backwards. It is satisfied automatically.

- xiaoxipan June 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

For the 2nd solution, you will want to check the number at every index, not only the even-index ones. Otherwise it will not work, as shown by the counter example given previously by the other person: 8 9 6 7 => 9 8 7 6

So you should do as such (0-index):
at even index i, swap A[i] and A[i+1] if A[i] < A[i+1]
at odd index j, swap A[j] and A[j+1] if A[j] > A[j+1]

- nanmeng1983 October 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

2nd sol does not work for {8,7,3,10,0,4,13,9,11,2};

- DD October 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@DD, FYI
8 7 3 10 0 4 13 9 11 2
8 3 7 10 0 4 13 9 11 2
8 3 10 7 0 4 13 9 11 2
8 3 10 0 7 4 13 9 11 2
8 3 10 0 7 4 13 9 11 2
8 3 10 0 7 4 13 9 11 2
8 3 10 0 7 4 13 9 11 2
8 3 10 0 7 4 13 9 11 2
8 3 10 0 7 4 13 9 11 2

- wwu November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
8
of 16 vote

Sort array first and swap pairs of numbers?

So 7 6 5 4 3 2 1 becomes - 7 5 6 3 4 1 2

- tejaswi.yvs April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Simple and elegant, thumbs up!

- puneet.sohi April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

impresive .but this problem can have multiple sequence of answer .so what if they ask for some other sequence.

- go4gold May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Swap is correct but you seriously don't need to sort it first, really!

- Avaln May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
6
of 8 vote

sort the array, then swap two neighbor elements from the second item

- sameul February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 votes

I meant that:
swap 1,2
swap 3,4
swap 5,6
swap 7,8

- samuel February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n log n) at best due to the sorting. Can you do it faster?

- decent solution, but can you do it faster? June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

Guys, you all missed the duplicates....

- blackball February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

dont think we need to consider duplicate, otherwise,how will u do it for
1 2 2

- samuel February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Given 1 2 2, the answer would be 2 1 2

- David.1138 April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

1) Sort the list first (5, 7, 1, 8, 3, 2, 9, 4, 2, 6 becomes 1, 2, 3, 4, 5, 6, 7, 8, 9)
2) Start filling the the odd indices. Keep track of remaining numbers and the number even slots (even slots are empty). The new array is like 1, _, 2, _, 3, _, 4 etc.
3) When the # of empty slots equals remaining numbers (there could be a boundary condition here +/- 1), start filling the even slots. That is when the array becomes 1, _, 2, _, 3, _, 4, _, 5 we have 4 dashes and 4 remaining numbers {6, 7, 8, 9}
So start filling the dashes. that is 1, 6, 2, 7, 3, _, 4, _, 5 and like that.
4) The end result will be 1, 6, 2, 7, 3, 8, 4, 9, 5 which is a solution.

Complexity = Sort + 2 pass
O ( n log n + 2*n) = O (n log n)

- Gokul February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a really good answer

- David.1138 April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

First, find the midpoint of the set. A great way to do this is to use a modified quicksort where you only drill into the partition on either side of your pivot that you know contains the midpoint. Return the midpoint as soon as the number of items to the left is equal to half the size of the list.

Then, just create a left and right list populated by taking every element from the original list except the midpoint and putting it in left if it's lower, right if it's higher. Merge the lists together by interleaving them, and put the midpoint at the end. The final ordering will match the required parameters, and except in worst case (an ordered list) the whole function is O(n).

import random

def arrange_high_low(shuffled_list):
    list_copy = shuffled_list[:]
    k = int(shuffled_list.__len__() / 2)+1
    size_left = 0
    pivot = 0
    while size_left != k:
        pivot = shuffled_list.pop()
        left = []
        right = []
        while shuffled_list:
            x = shuffled_list.pop()
            if x < pivot:
                left.append(x)
            else:
                right.append(x)
        if size_left+left.__len__()+1 > k:
            shuffled_list = left[:]
        elif size_left+left.__len__()+1 < k:
            shuffled_list = right[:]
            size_left += left.__len__()+1
        else:
            break

    print pivot
    left = []
    right = []
    for i in list_copy:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
    left.append(pivot)
    right.append(pivot)
    even = 0
    final = []
    for i in list_copy:
        if even:
            final.append(right.pop(0))
            even = 0
        else:
            final.append(left.pop(0))
            even = 1
    return final

shuffled_list = range(1,21)
random.shuffle(shuffled_list)
print ', '.join(map(str, arrange_high_low(shuffled_list)))

- Mason February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 13 vote

Swapping alternate elements solves the problem

private static void arrangeList(int A[]) {

	for (int i = 1; i < A.length; i++) {
	    if (i % 2 == 1 && A[i] < A[i - 1])
		swap(A, i, i - 1);
	    if (i % 2 == 0 && A[i] > A[i - 1])
		swap(A, i, i - 1);
	}
    }

    private static void swap(int[] a, int i, int j) {

	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
    }

- thelineofcode February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Seems like most of swaps are done by the second if statement, if (i % 2 == 0 && A[i] > A[i - 1]). Under what case will it go into the first if statement?

- Guy February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorting => usually O(nlogn)
Then the swapping =>O(n)
Total =?

Wherease just swapping = O(n)

Sit down with pen and paper and trace code posted by people you trust, and find bugs OR learn from good code (whichever the case).

- S O U N D W A V E February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you, this is simple and efficient.

- CinderillaLi February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This algorithm will not work in below input
1,3,3,4
Above mentioned code will end up in showing same sequence, without any swapping.
Actual expected output is
3,4,1,3

- IntMainReturnZero February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a great example of a question where it can just be blow off to a completely hard problem. The trick is that the inequalities are not implying anything.

@thelineofcode is basically comparing 2 x 2 and making sure the inequality holds.

- morezaei00 February 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The code assumes the final state required is a <= b >= c <= d ...

- srikantaggarwal February 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

input = [7, 6, 5, 4, 3, 2, 1, 0]
print input
sorted_output = sorted(input)
sorted_output.reverse()
output = [sorted_output[0]]
for i in range(1, len(input)):
    if i % 2 == 1 and len(input) > i + 1:
        output.extend([sorted_output[i+1],sorted_output[i]])
if len(input) % 2 == 0:
    output.append(sorted_output[-1])
print output

- atiurrs April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Question is ambiguous (as usualy for CC).

a < b > c < d <-expressions like this are not well defined nor used in math.

a < b < c is an idiom that has come to mean a < b && b < c
But since it's the same inequality < used in both places, it matters not whether we explicitly state that a < c also (because this is true by transitivity automatically).

We can extend this to a < b < c < d < e < f safely.
Note above implies 5 inequalities directly, and 6choose2 inequalities in total.

Now if you have something like a < b > c < d > e

What does this say about the relative ordering of a vs. d or b vs. e ?
Or does it say nothing about these?

- S O U N D W A V E February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Heres a full solution in C#:
1. Sort the array in incrementing order
2. Check each value of the array (starting at 0), and determine if it withholds the stated rules (if even index, should be less than right, if odd should be greater than)
3. If not, continue moving right along indices and find element that withholds rules
4. Continue till exhausted all indices

using System;

namespace SortNegativeArray
{
	class MainClass
	{
		public static int[] nums = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};


		public static void Main (string[] args)
		{
			Array.Sort(nums);					//First sort the array in incrementing order
			PrintArray();
			SortNums(0);
			PrintArray();

		}

		public static void SortNums(int index) {
			Console.WriteLine("Pass " + index);
			if (index == nums.Length) return;

			//If its an even number, handle appropraitly
			if (index == 0 || (index%2 == 0)) {
				//Check less than right → We can assume this since we made it this far 
				for(int i = index+1; i < nums.Length; i++) {
					//If I’m less then the next one, we’re good, break the loop
					if (nums[index] < nums[i] && i == index+1) {
						break;
					}
					//Otherwise check if its less than the number if so replace whats already there
					else if (nums[index] > nums[i]) {
						int temp = nums[i];
						nums[i] = nums[index];
						nums[index] = temp;
						break;
					}
				}
			}
			//Likewise for odd
			else {
				//Check greater than right → We can assume this since we made it this far
				for(int i = index+1; i < nums.Length; i++) {
					if (nums[index] > nums[i] && i == index+1) break;
					else if (nums[index] < nums[i]) {
						int temp = nums[i];
						nums[i] = nums[index];
						nums[index] = temp;
					}
				}
			}
			SortNums(++index);
		} 
		public static void PrintArray() {
			Console.WriteLine("--Printing Array--");
			foreach(int num in nums) Console.Write(num + " ");
			Console.WriteLine("----------------");
		}
	}

}

- AddisonRodomista February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#define MAX_SIZE_ARRAY 10

void sortarray(int a[]);
void swap(int *a, int *b);

void sequence_swap(int * a);

int main(void)
{
	int a[MAX_SIZE_ARRAY], index;

	printf("Enter array elements\n");
	for(index = 0;  index < MAX_SIZE_ARRAY; ++index)
		scanf("%d",&a[index]);

	printf("Entered array elements is:\n\n");
	for(index = 0;  index < MAX_SIZE_ARRAY; ++index)
		printf("%d ",a[index]);

	printf("\n");

	sortarray(a);

	printf("sorted array is:\n");
	for(index = 0; index< MAX_SIZE_ARRAY; ++index)
	 printf("%d ", a[index]);
	
	printf("\n");

	sequence_swap(a);

	printf("a<b>c<d>e etc sequence is:\n");
	for(index = 0; index< MAX_SIZE_ARRAY; ++index)
	 printf("%d ", a[index]);

return 0;
}

void sortarray(int *a)
{
 int i , j, n;
 n = MAX_SIZE_ARRAY;
 for(i = 0; i < n; ++i)
	 for (j = n - 1; j > i; --j)
		 if(a[j-1] > a[j])
			 swap(&a[j],&a[j-1]); 
}

void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

void sequence_swap(int *a)
{
	int i;
	int temp;
	for (i =1; i < MAX_SIZE_ARRAY-1 ; i +=2 )
	{
	temp = a[i];
	a[i] = a[i+1];
	a[i+1] = temp;
	}

}

- aravind February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Post-order travel of a BST?

- Anonymous February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in Java. Let me know what you think.

package InterviewPractice;
import java.util.Arrays;
public class sortArray {
    public static void main(String[] args) {
        int[] nums = new int[]{1,8,2,5,9,3,6,4,7,15,21,12};//this is the array of ints, it can change
        Arrays.sort(nums);                              //sort the array
        int[] swapped= swap(nums);                      //call swap on nums array 
        System.out.println(Arrays.toString(swapped));   //print result of swap 
    }
    public static int[] swap(int[] arr) {
        int[] returnArr = new int[arr.length];
        returnArr[0] = arr[0];
        int arrCounter = 2;
        for (int i = 1; i < arr.length - 1; i++) {
            returnArr[i]=arr[arrCounter];
            if(i%2==0){
                arrCounter+=3;
            }else{
                arrCounter--;
            }
        }
        if(arr.length%2==0){
            returnArr[returnArr.length-1]=arr[arr.length-1];
        }else{
            returnArr[returnArr.length-1]=arr[arr.length-2];
        }
        return returnArr;
    }
}

- Michael February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there is no need to sort complete array, we can make use of min-heap here. Complete algorithm can complete in O(n/2 * log n)
Steps:
1. Transform array into min-heap, in O(n)
2. Swap root with second last element in array
3. Reduce heap size by 2 (which means last 2 elements are already in required form)
4. Heapify root element.
5. Repeat steps 3 and 4 until heap size becomes 0 (this operation completes in O(n/2 * log n))

Please refer below source code

import java.util.Random;

public class Seven {

    public static int[] numbers = new int[21];
    public static int size = numbers.length;
    public static void main(String [] args) {
        
        //prepare input
        Random rn = new Random();
        System.out.println("Original array");
        for (int i=0; i<numbers.length; i++){
            numbers[i] = rn.nextInt(100);
            System.out.print(" " + numbers[i]);
        }

        //transform array which contains actual algorithm
        transformArray();
        
        //print output
        System.out.println("\nTransformed array");
        for(int k=0; k<numbers.length; k++){
            System.out.print(" " + numbers[k]);
        }
        
    }

    private static void transformArray() {
        //Transform un-sorted array into min-heap -> O(n)
        for(int j=size-1/2; j>=0; j--){
            minHeapify(j);
        }
            
        //Size getting decremented by 2, so n/2 iterations
        while (size>0){
            if(size%2==1){ 
                swap(0,size-1);
                size-=1;
            }else{
                swap(0,size-2);
                size-=2;
            }
            //min-heapify single element -> O(log n)
            minHeapify(0);
        }
    }

    private static void minHeapify(int i) {
        int smallest;
        int left = i * 2;
        int right = i * 2 + 1;
        if (((left < size) && (numbers[left] < numbers[i]))) {
            smallest = left;
        } else {
            smallest=i;
        }

        if (((right < size) && (numbers[right] < numbers[smallest]))) {
            smallest = right;
        }
        if (smallest != i) {
            swap(i, smallest);
            minHeapify(smallest);
        }
        
    }
    private static void swap(int i, int j) {
        int t = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = t;
    } 
}

- IntMainReturnZero February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n/2 * log n) = O(n log n)

- Gokul March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void arrange(int[] array) {
	for(int i = 0; i < array.length - 1; i++) {
		if(i % 2 == 0) {
			if(array[i] > array[i + 1]) {
				swap(array, i, i + 1);
			}
		}
		else {
			if(array[i] < array[i + 1]) {
				swap(array, i, i + 1);
			}
		}
	}
}

- usunyu March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a brute force solution which lists all combinations of possible solutions given an unordered array.

public class ArrayTest1 {
	
	public static void main(String[] args){
		int[] a = new int[10];
		Random r = new Random();
		for (int i = 0; i < a.length; i++){
			a[i] = r.nextInt(10);
			System.out.print(a[i] + ",");
		}
		System.out.println();
		
		List<List<Integer>> results = new ArrayList<List<Integer>>();
		for (int i = 0; i < a.length; i++){
			exch(a, 0, i);
			inequalty(a, 0, true, results);
		}
		
		
		for (List<Integer> sol: results){
			System.out.println();
			for (Integer i: sol)
				System.out.print(i + ",");
		}
	}
	
	private static void inequalty(int[] a, int index, boolean condition, List<List<Integer>> results){
		if (a == null || a.length == 0) return;
		if (index == a.length - 1){
			List<Integer> r = new ArrayList<Integer>();
			for (int i = 0; i < a.length; i++)
				r.add(a[i]);
			results.add(r);
		}
		else{
			for (int i = index + 1; i < a.length; i++){
				if (a[i] > a[index] == condition && a[i] != a[index]){
					if (i != index + 1)
						exch(a, i, index + 1);
					inequalty(a, index + 1, !condition, results);
				}
			}
		}
	}
	
	private static void exch(int[] a, int i, int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

}

- kartrace March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

std::list<int> L ={16,2,9,7,1,8,5,3,6,2,8,2};
    L.sort();
    L.unique();
    std::vector<int> V {std::make_move_iterator(std::begin(L)),
        std::make_move_iterator(std::end(L)) };
    
    for (int i = 0; i<V.size()/2; i++) {
        if (i%2 ==1) {
// a < b > c < d > e, etc
            std::iter_swap(V.begin()+i, V.begin()+i+V.size()/2-1);
        }
        
    }
        for (int i = 0; i<V.size(); i++) {
            std::cout<<V[i]<<" ";
        }

- D3nat March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a<b>c<d...
a<b means a must not be the maximum number, so let's swap a[0] and a[1] if a[0] > a[1], this guarantees a is not the maimum number in the array.
b>c means b must not be the minimum number, so let's swap b and a[2] if b < a[2], this guarantees b (the a[1] after possible swap) is not the minimum number from a[1] to a[n];
do it till end.

The algorithm is:
if i % 2 == 0, swap a[i] and a[i + 1] if a[i] > a[i + 1];
else swap a[i] and a[i + 1] if a[i] < a[i + 1];
for i = 0 to n -1;

void reorder(int* a, int size)
{
	for (int i = 0; i < size - 1; ++i)
	{
		if ((i % 2 == 0 && a[i] > a[i + 1]) ||
			(i % 2 == 1 && a[i] < a[i + 1]))
		{

			a[i] ^= a[i + 1];
			a[i + 1] ^= a[i];
			a[i] ^= a[i + 1];

		}
	}
}

- guest.guest April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The trick is to sort them.

#include<stdio.h>

void sort(int *array1, int size);
void scramble(int *array1, int size);
void print(int *array1, int size);

int main(void)
{

	int array1[13] = {8,3,1,89,6,4,5,12,33,456,90,81,2};

	print(array1, 13);
	scramble(array1, 13);
	print(array1, 13);

	return 0;

}

void sort(int *array1, int size)
{
	for(int i = 0; i < size - 1; i++)
	{	
		for(int j = i + 1; j < size; j++)
		{		
			if(array1[i] > array1[j])
			{			
				int temp = array1[i];
				array1[i] = array1[j];
				array1[j] = temp;			
			}		
		}	
	}
}

void scramble(int *array1, int size)
{

	sort(array1, size);

	for(int i = 0; i < size - 1; i += 2)
	{
	
		int temp = array1[i];
		array1[i] = array1[i+1];
		array1[i+1] = temp;

	}

}

void print(int *array1, int size)
{

	for(int i = 0; i < size - 1; i++)
	{
	
		printf("%d, ", array1[i]);

	}

	printf("%d\n", array1[size-1]);

}

- Alejandro Gonzalez Perez April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An O(n) time, O(1) space solution:

Consider 3 consecutive numbers A(i), A(i+1), A(i+2)

Suppose A(i) and A(i+1) are in correct order.
If A(i+1) and A(i+2) are also in correct order, then continue doing for A(i+1), A(i+2), A(i+3);

If A(i+1) and A(i+2) are not in correct order, then swap A(i+1) and A(i+2). After swapping, A(i), A(i+2), A(i+1) must be all in correct order (can you check that ?). Then, continue doing for A(i+2), A(i+1), A(i+3)...

Initially, we can swap A(1) with the max of (A). Then A(1), A(2) will be in correct order.

- ninhnnsoc April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def waveSort(array):
	# First sort the list.
	array.sort()

	# Get an index for the midpoint of the sorted list. 
	lenA = len(array)
	splitIndex = lenA // 2

	# Now we are going to go through half the list and append
	# an element from the first half and from the second half
	# to the solution, producing a wave.
	result = []
	for i in range(splitIndex):
		result.append(array[splitIndex+i])
		result.append(array[i])

	# If the array had odd length, we have skipped the last element
	# in above loop, so we simply append before returning solution
	if lenA % 2 == 1: result.append(array[-1])
	return result

# print waveSort([6,2,4,3,8,9,1,5,7])
# print waveSort([6,2,4,3,8,9,1,10,5,7])

- btcarb April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is O(n) solution.

public static int[] createWave(int[] arr){

		for(int i=0; i<arr.length-1;i++){	

			if(i%2 == 0){
				if(arr[i] < arr[i+1]){
					arr = swap(arr,i,i+1);
				}
			}else{
				if(arr[i] > arr[i+1]){
					arr = swap(arr,i,i+1);
				}
			}
		}
		
		return arr;
	}

	private static int[] swap(int[] arr,int i,int j){

		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		return arr;
	}

- GS April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Arrange first 3 elements (0,1,2) in desired order and then shift 2 positions right and again order next 3 elements (2,3,4) and continue doing the same till you reach end of the array. Resultant array is the desired one.

This algorithm does n/2 iterations and no extra space.

- srini April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can it be n/2? What about comparisons done to arrange 3 numbers?

- Anonymous April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is n/2 because you are shifting 2 positions right. But this will make 2 comparisons to find smallest of 3 on each iteration. So, effectively it is O(n).

And regarding comparisons, compare 3 elements and place smallest of 3 elements in the middle position (which is always odd position because we are shifting 2 positions on each iteration) of the 3 element window.

Example

Input: 1 2 3 4 5 6 7

1st: 3 1 2 4 5 6 7
2nd: 3 1 5 2 4 6 7
3rd: 3 1 5 2 7 4 6

- srini April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void makeWave(int arr[], int n)
{
	for(int i = 0; i < n; ++i){
		if(i & 1){//odd index should be smaller than after
			if(i + 1 < n && arr[i] > arr[i+1]) swap(arr[i], arr[i+1]);
		}
		else{//even index should be larger than after
			if(i + 1 < n && arr[i] < arr[i+1]) swap(arr[i], arr[i+1]);
		}
	}
}

- uuuouou April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) Solution, can any tell am I correct or not?
Thanks in advance.

public class O {
	public static void main(String[] args) {
		int a[] = { 4, 3, 2, 1, 8, 9 };
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "  ");
		}
		System.out.println();
		for (int i = 0; i < a.length; i += 2) {
			if (i + 1 == a.length) {
				break;
			}
			if (a[i] < a[i + 1]) {
				int t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
			}
			if ((i + 2) >= a.length) {
				break;
			}
			if (a[i + 1] > a[i + 2]) {
				int t = a[i + 1];
				a[i + 1] = a[i + 2];
				a[i + 2] = t;
			}
		}
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "  ");
		}
	}
}

- Srinivas April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import random

input = random.sample(range(30), 20)
print input

input.sort()
output = [input[0]]
for i in range(1, len(input)):
    if i % 2 == 1 and i + 1 < len(input):
        output.extend([input[i+1], input[i]])
if len(input) % 2 == 1:
    output.append(input[-1])
print output

- atiurrs April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort_like_wave(vector<int>& a){
bool rise = false;
for (int i = 0; i < a.size()-1; i++){
if (rise){
if (a[i] > a[i+1]) swap(a[i], a[i+1]);
}else{
if (a[i+1] > a[i]) swap(a[i], a[i+1]);
}
}
}

- Jie Feng April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort_like_wave(vector<int>& a){
    bool rise = false;
    for (int i = 0; i < a.size()-1; i++){
        if (rise){
            if (a[i] > a[i+1]) swap(a[i], a[i+1]);
        }else{
            if (a[i+1] > a[i]) swap(a[i], a[i+1]);
        }
    }
}

- Jie Feng April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sol1. First sort the array, then swap pairs of numbers.
sol2. Traverse the array starting from the first vertex till the second last vertex, when at an even position swap the value with the next position if the former is smaller; when at an odd position swap the value with the next position is the former is larger

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main () {
	int A[] = {1,2,3,4,5,6};
	
	// solution 1, O(nlog(n))
	int len_a = sizeof(A)/sizeof(int);
	sort(A, A+len_a);
	for (int i = 0; i < len_a; i+=2) {
		swap(A[i], A[i+1]);
	}
	cout << "{";
	for (int i = 0; i < len_a; i++) cout << A[i] << ", ";
	cout << "}" << endl;
	
	// solution 2 O(n)
	for (int i = 0; i < len_a-1; i++) {
		if (i & 1) {
			if (A[i] > A[i+1]) swap(A[i], A[i+1]);
		}
		else {
			if (A[i] < A[i+1]) swap(A[i], A[i+1]);
		}
	}
	
	cout << "{";
	for (int i = 0; i < len_a; i++) cout << A[i] << ", ";
	cout << "}" << endl;
}

- mayankme0077 April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if we dont need to satisfy a1<a3<a5... and a2<a4<a6..., then will took O(n)
if we do, just do a quick sort before this, any way the sort will always took O(nlogn) average

void wave(int *a, int size)
{
	if (size < 1)
		return;
	else if (size == 2)
	{
		if (a[0] < a[1])
			swap(a[0], a[1]);
		return;
	}

	for (int i = 0; i < size - 2; i+=2)
	{
		if (a[i] < a[i+1])
			swap(a[i], a[i+1]);
		if (a[i+1] > a[i+2])
			swap(a[i+1], a[i+2]);
	}
}

- limenglin1986 April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have implemented simple soultion as mentioned by - tejaswi.yvs

import java.util.Arrays;

/**
 * @author vishal.naik
 *
 */
public class WaveSort {

    public static void main(String[] args) {
	int[] arr = { 7, 3, 6, 9, 2, 5, 8, 4 };
	waveSort(arr);
	
	printArray(arr);
    }

    /**
     * Sorts the input array such that a1 >= a2 <= a3 >= a4 <= a5...
     * 
     * @param arr , not null
     */
    private static void waveSort(int[] arr) {

	// Sort the array. This sorts array in ascending order.
	Arrays.sort(arr);

	//Reverse the array. So the array will be in descending order.
	reverse(arr);
	
	// Iterate over the sorted array.
	for (int i = 1; i < arr.length - 1; i = i + 2) {
	    // Swap the numbers.
	    swap(i, i + 1, arr);
	}
	
    }

    /**
     * Prints the array.
     * 
     * @param arr , not null
     */
    private static void printArray(final int[] arr) {
	for (int i : arr) {
	    System.out.print(i + " ");
	}
    }

    /**
     * Reverses the array.
     * 
     * @param arr , not null
     */
    private static void reverse(int[] arr) {
	int start = 0;
	int end = arr.length -1;
	while(start <= end) {
	    swap(start, end, arr);
	    start++;
	    end--;
	}
    }

    /**
     * Swaps the element at position i with element at position j.
     * @param i , not null
     * @param j , not null
     * @param arr , not null
     */
    private static void swap(final int i, final int j, int[] arr) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
    }
}

Please visit java-fries site for the complete article.

- vishal naik May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep track of the current wave trend, up or down in a boolean value, swap adjacent numbers if the trend is violated. If swapped, go back one position to make sure it doesn't violate the sorted trend, but do not go back if i is already 0.

P.S. Can't believe the solution that requires sorting the entire array got the most votes.

WaveArray(int[] A){
  int i = 0;
  boolean up = true;
  while(i < A.length() - 1){
    if(isValidWave(up, i)){
      i++;
      up = !up;
    }
    else{
      swap(A, i, i+1);
      if( i > 0){
        i--;
        up= !up;
      }
    }
  }
}

isValidWave(boolean up, int i, int[] A){
  if(up)
    return A[i] <= A[i+1];
  else
    return A[i] >= A[i+1];
}

- Avaln May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can optimize this solution by not sorting.

1. Find the median (or kth element)... QuickSelect is O(n). This will enable us to find the median without sorting.
2. Iterate the array with two indices (one pointing to the next item equal or less than the median, and the second pointing to the next item larger than the median.)
2a. If odd iterator, swap with next equal or less.
2b. if even iterator, swap with next larger

The first part is a standard solution (you use either the built-ins or write your own). The second part is a simple coding...

int[] LTGTSort (int arr[], int size)
{
  // check for invalid arr and size here

  int median = QuickSelect(arr, size); // did not verify this function signature, but you get the idea.
  for (int i = 0; i < size; i++)
  {
    for (int j = i; j < size; j++) // this search can only be at most n/2
    {
       if (i%1 && arr[j] <= median) // odd
       {
         swap(arr, i, j);
         break;
       }
       else if (arr[j] > median) // even
       {
         swap(arr, i, j)
         break;
       }
    }
  }
  return arr;
}

- O(n) solution... June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Quick-select is O(N) average but O(N^2) worst case.

- Anonymous July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class swap {
	void swapElements(ArrayList<Integer> inp)
	{
		for(int i=1; i < inp.size();i++)
		{
			if((i%2==1 && inp.get(i) > inp.get(i-1)) || (i%2==0 && inp.get(i) < inp.get(i-1)))
			{
				//swap Elements
				inp.set(i-1, inp.get(i-1)^inp.get(i));
				inp.set(i,inp.get(i-1)^inp.get(i));
				inp.set(i-1, inp.get(i-1)^inp.get(i));
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		swap obj=new swap();
		ArrayList<Integer> inp=new ArrayList<Integer>(Arrays.asList(2, 3, 0, 1 ));
		obj.swapElements(inp);
		for(int elem : inp)
			System.out.print(elem+" ");
		

	}

}

- Dinesh June 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> build_wave(vector<int> v) {
	sort(v.begin(), v.end());
	int sz = v.size();
	int num_up = sz / 2 + sz %2;
	int num_down = sz / 2;
	vector<int> n(sz);
	// up values
	for (int i = 0, k = 0; i < sz; i+= 2, k++) {
		n[i] = v[k + sz/2];
	}
	// down values
	for (int i = 1, k = 0; i < sz; i+= 2, k++) {
		n[i] = v[k];
	}
}

- thiago.xth1 June 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> build_wave(vector<int> v) {
	sort(v.begin(), v.end());
	int sz = v.size();
	int num_up = sz / 2 + sz %2;
	int num_down = sz / 2;
	vector<int> n(sz);
	// up values
	for (int i = 0, k = 0; i < sz; i+= 2, k++) {
		n[i] = v[k + sz/2];
	}
	// down values
	for (int i = 1, k = 0; i < sz; i+= 2, k++) {
		n[i] = v[k];
	}
}

- thiago.xth1 June 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//without expensive sorting algo; complexity O(n)

public class waveSort2 {

public static void main (String[] args){
int [] arr = {9,12,10,3,7,17,4,10,20};
//output must be {a1 >= a2 <= a3 >= a4 <= a5 >=a6 <=a7}, {12 9 10 3 7 4 17 10 20}
waveSort(arr);
printArray(arr);
}

private static void printArray(int[] arr) {
// TODO Auto-generated method stub
for (int i : arr) {
System.out.print(i + " ");
}
}

public static void waveSort(int[] arr) {
// TODO Auto-generated method stub
for (int i=1; i < arr.length-2; i=i+2)
{
if ((arr[i-1] < arr[i]) && (arr[i] < arr[i+1]) && (arr[i-1] < arr[i+1]))
{
swap(i-1, i+1, arr);

}
else if ((arr[i-1] < arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] < arr[i+1]))
{
swap(i-1, i, arr);

}
else if ((arr[i-1] > arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] > arr[i+1]))
{
swap(i, i+1, arr);

}
else if ((arr[i-1] < arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] > arr[i+1]))
{
swap(i, i+1, arr);

}
else if ((arr[i-1] < arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] < arr[i+1]))
{
swap(i, i-1, arr);

}

}

}

public static void swap(int i, int j, int[] arr) {
// TODO Auto-generated method stub
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

}

- Deep July 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a wave print problem. For each even number i, make sure that num[i-1]<num[i]<num[i+1]

- allen.lipeng47 January 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int a[1000<<2];
int main()
{
long long int i,j,k,m,n;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i=i+2)
{
if(i==0)
{
if(a[i]<a[i+1])
{
swap(a[i],a[i+1]);
}
}
if(a[i]<a[i+1])
{
swap(a[i],a[i+1]);
}
if(a[i]<a[i-1])
{
swap(a[i],a[i-1]);
}
}

for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}




}

- vejon June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int a[1000<<2];
int main()
{
long long int i,j,k,m,n;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i=i+2)
{
if(i==0)
{
if(a[i]<a[i+1])
{
swap(a[i],a[i+1]);
}
}
if(a[i]<a[i+1])
{
swap(a[i],a[i+1]);
}
if(a[i]<a[i-1])
{
swap(a[i],a[i-1]);
}
}

for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}




}

- vejon June 15, 2015 | 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