## 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].

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].

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

Beautiful!

Comment hidden because of low score. Click to expand.
1

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.

Comment hidden because of low score. Click to expand.
2

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

Comment hidden because of low score. Click to expand.
2

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.

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

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

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.

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

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)?

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;
}
}``````

Comment hidden because of low score. Click to expand.
2

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])
}
}
}``````

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

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?

Comment hidden because of low score. Click to expand.
2

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

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

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

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

@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?

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

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).

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

@oOZz, And you mean without using extra storage?

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

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).

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

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.

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.

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]

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

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

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

@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

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

Comment hidden because of low score. Click to expand.
-2

Simple and elegant, thumbs up!

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

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

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!

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2

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

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

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

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

Guys, you all missed the duplicates....

Comment hidden because of low score. Click to expand.
-1

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

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

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

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)

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

This is a really good answer

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)))``````

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;
}``````

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?

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).

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

Thank you, this is simple and efficient.

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

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

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.

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 ...

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``````

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?

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("----------------");
}
}``````

}

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;
}``````

}

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

Post-order travel of a BST?

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;
}
}``````

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))

``````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;
}
}``````

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

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

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);
}
}
}
}``````

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++)
}
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;
}

}``````

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]<<" ";
}``````

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];

}
}
}``````

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]);

}``````

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.

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])``````

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;
}``````

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.

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

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

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

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

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]);
}
}
}``````

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

O(n) Solution, can any tell am I correct or not?

``````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] + "  ");
}
}
}``````

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``````

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]);
}
}
}

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]);
}
}
}``````

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;
}``````

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]);
}
}``````

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.

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];
}``````

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;
}``````

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

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

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+" ");

}

}``````

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];
}
}``````

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];
}
}``````

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;
}

}

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]

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]<<" ";
}

}

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]<<" ";
}

}

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.

### 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.