## Google Interview Question for Interns

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
5
of 7 vote

a preliminary solution can be to just sort the array and then push the last (n/2) elements at the even positions in any order and the condition will hold good
complexity O(nlogn)

or you can use selection algorithm for median finding and then push the number greater than median at even positions and others at odd position
complexiy O(n)

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

i wrote a program based on your idea but it doesn't work for median or surrounding elements.

``````#include<stdio.h>

void swap(int *x, int *y)
{
if( *x == *y )
return;
*x^=*y;
*y^=*x;
*x^=*y;
}
int findkth(int a[], int start, int end, int k)
{
int pivote = (start + end) >> 1;

int begin = start;
int smaller= start;

swap(&a[pivote], &a[end]);
while( begin < end )
{

if( a[begin] < a[end] )
{
swap(&a[smaller],&a[begin]);
smaller++;
}
begin++;
}
swap(&a[end], &a[smaller]);
if( smaller == k )
return a[smaller];
else
if( smaller < k )
start = smaller + 1;
else
end  = smaller - 1;

return findkth(a, start, end, k);
}
int a[] = {9, 6, 3, 2, 7, 1, 8, 5,4};
#define ASIZE(A,x) (sizeof(A)/sizeof(int))
int main()
{

int median = findkth(a,0, ASIZE(a,int)-1, (0+ASIZE(a,int))>>1);
printf("\nMedian is %d\n", median);

int i=0,j;
int k = (0+ASIZE(a,int))>>1;

for(i=0;i<ASIZE(a,int); i++)
printf("%d ",a[i]);

printf("\n");
for( i = 1, j = ASIZE(a,int)-2; i < j ; i+=2, j-=2)
{
swap(&a[i],&a[j]);
}
for(i=0;i<ASIZE(a,int); i++)
printf("%d ",a[i]);
return 0;
}``````

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

We can use Median of Medians or Selection algorithm in quick sort to find the median of an unsorted array in linear time

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

Finding median is actually the best solution

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

@Alok. Hell No.

There is a vastly better solution.

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

question?id=5684901156225024

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

sort the array and swap the positions. this'll not work if the elements are repeated.

sort(a, a+n);
cout << endl;
cout << "numbers entered (sorted) " << endl;

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

cout << endl;
cout << "ordering based on < and > ... " << endl;
for(int i = 1; i < n - 1;) {
swap(a[i], a[i+1]);
i += 2;
}

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

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

>>One handling could be if a[i] == a[j] then swap a[i] with last element also keep a pointer to it say k.
No wrongly wrote this. and the code mentioned also doesn't handle "==" case well.

Good solution would be scan till end untill we find a different element and then swap with a[i] and then continue code:

``````void reArrange(int *a, int len)
{
int i=0, j=1, k=0;
int temp = 0;
if(len < 2) return;

while(j < len)
{
if(a[i] == a[j])
{
k = j+1;
while(k < len)
{
if(a[k] == a[i])
{
k++;
}
else
{
temp = a[i];
a[i] = a[k];
a[k] = temp;
break;
}

}

}
if(i%2 == 0)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
else
{
if(a[i] < a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
i++;
j++;
}
}``````

Write the bad code part before or after rearranging

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

I think this code could not handle this input: 2, 2, 9, 8, 8. Using this algorithm, we will not be able to find a solution. but the one solution is 2, 8, 2, 9, 8.
Any thought?

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

Good catch.
I have handled the case when we are trying to find non equal number in the list >i. But i also need to handle when we are trying to find non euqal number in lis <i.
However 2nd case is trivial as we have already formed an array and we don't want to disturb it

something like this should work:

``````void reArrange(int *a, int len)
{
int i=0, j=1, k=0;
int temp = 0, p=0, s=-1;
if(len < 2) return;

while(j < len)
{
if(a[i] == a[j])
{
k = j+1;
while(k < len)
{
if(a[k] == a[i])
{
k++;
}
else
{
temp = a[i];
a[i] = a[k];
a[k] = temp;
break;
}

}
if(k == len) //this means from i to k elements are same, so now we need to find right place for those elements
{
s++;
while(s < i)
{
if(s == 0)
{
if(a[i] < a)
{
temp = a[i];
a[i] = a;
a = temp;
break;
}
}
else if(s%2)
{
if((a[i] > a[s+1]) && (a[i] > a[s-1]))
{
temp = a[i];
a[i] = a[s];
a[s] = temp;
break;
}
}
else
{
if((a[i] < a[s+1]) && (a[i] < a[s-1]))
{
temp = a[i];
a[i] = a[s];
a[s] = temp;
break;
}
}
s++;
}
}

}
if(i%2 == 0)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
else
{
if(a[i] < a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
i++;
j++;
}``````

}

After doing this the worst case for this algo becomes O(n).

So i thought of doing time complexity comparison of this algo and that of sorting:

Sorting:
best case: nlogn
average case: nlogn
worst case: nlogn

Thi algo:
best case: n
average case: n
worst case: n2

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

question doesnt look so clear .. 1. does it have duplicate elements ?
2. does it has number of duplicate elements > (n/2) -> n being number of elements in the array ?
3. if above 2 is correct, then we cant satisfy > < , instead we may need >= , <= somewhere .

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

``````sort(a, a+n);
cout << endl;
cout << "numbers entered (sorted) " << endl;

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

cout << endl;
cout << "ordering based on < and > ... " << endl;
for(int i = 1; i < n - 1;) {
swap(a[i], a[i+1]);
i += 2;
}

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

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

we don't need to sort all the array, all the even indexed elements are greater then its odd indexed neighbor , so we can just split the arrays half half, the right ones are all greater than left ones.

public static void reArrange(int arr[]){
int targetIndex = (arr.length-1)/2;
reArrageArry(arr,0,arr.length-1,targetIndex);
int start = targetIndex + 2;
for(int i=0;i<targetIndex;i+=2){
int tem=arr[i+1];
arr[i+1]=arr[start+i];
arr[start+i]=tem;
}
for(int i = 0 ; i < arr.length; i++){
System.out.print(arr[i]+" ");
}

}
private static void reArrageArry(int arr[],int start, int end,int targetIndex){
if(start==end)
return;
int part = partition(arr,start,end);
if(part==targetIndex)
return;
if(part>targetIndex){
reArrageArry(arr,start,part-1,targetIndex);
}else{
reArrageArry(arr,part+1,end,targetIndex);
}

}
private static int partition(int arr[],int start, int end){
int pos = arr[end];
int i = start-1;
int j = start;
while(j<end){
if(arr[j]<=pos){
i++;
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
j++;
}
arr[end]=arr[i+1];
arr[i+1]=pos;
return i+1;
}

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

have a look it as simple at all ... if any error plz report :)

``````#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<sstream>
#include<iostream>
#include<iomanip>
using namespace std;
inline void swapp(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}

int main()
{
int n,array;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>array[i];
}
for(int i=0;i<n-2;i++)
{
if(array[i]>array[i+1])
{
swapp(&array[i],&array[i+1]);
}
if(array[i+1]<array[i+2])
{
swapp(&array[i+1],&array[i+2]);
}
i=i+1;
}

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

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

Looks good

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

I think that this algo will not work with : {2,3,5,1}

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

I don't think there is any need to sort the array.
This can be done in single pass. Look at the below code:

``````void reArrange(int *a, int len)
{
int i=0, j=1;
int temp = 0;
if(len < 2) return;

while(j < len)
{
if(i%2 == 0)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
else
{
if(a[i] < a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
i++;
j++;
}
}``````

The code is self explanatory. However one thing to consider here is what if we have equal values then probably we'll need to hande the case seperately ex. 2,2,2,2,34,56
One handling could be if a[i] == a[j] then swap a[i] with last element also keep a pointer to it say k.
So then the code would modify to:

``````void reArrange(int *a, int len)
{
int i=0, j=1;
int temp = 0;
if(len < 2) return;

while(j < len)
{
if(a[i] == a[j])
{
temp = a[i];
a[i] = a[len-1];
a[len-1] = temp;
}
if(i%2 == 0)
{``````

The only catch in this code is that there should be enough greater numbers.
To catch this kind of anomaly After we have built the array we can scan it and it doesn't follow the pattern then we can simply return "bad input"

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

first algo will not work with :{2,3,5,1}

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

what if the numbers are not sorted already?

I think we need to add all numbers to binary search tree and recursively print in following order.

Print left, right and then root - for each sub tree in the bst
complexity - O(nlogn)

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

Doesn't matter if the array is sorter or not.
Say array is a1, a2, a3, a4 (assuming all are unique elements)
either a1 > a2 or a1 < a2
so after comparison we will have either a1 a2 or a2 a1
smilarly for a1 a3 and a2 a3.
Hope you got my point

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

Java Code
Complexity: O(n)

``````public class Dummy {

public static void main(String[] args) {
// TODO Auto-generated method stub
List<Integer> list = null;
list = createList();
System.out.println("Input Data: "+list);
applyPattern(list);
System.out.println("Output Data: "+list);

}

public static List<Integer> createList(){
List<Integer> list = new ArrayList<Integer>();
int limit = 100;
int i =0;
while(i<limit){
i++;
}
return list;
}

private static void applyPattern(List<Integer> list) {
int i = 0;
int limit = list.size();
int var1=0,var2=0;
while(i<limit-1){
int j=i+1;
if(i%2==0){
var1 = list.get(i);
var2 = list.get(j);
if(var1>var2)
{
list.set(i, var2);
list.set(j, var1);
}
}
else{
var1 = list.get(i);
var2 = list.get(j);
if(var1<var2)
{
list.set(j, var1);
list.set(i, var2);

}
}
i++;
}
}
}``````

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

What happens when var1 == var2? applyPattern does not seem to take that into consideration.

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

how about find the median by partitioning and continue picking one from either side ?

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

If you look at the merge sort algorithm you will see this step. O(nlogn)

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

For simplicity, suppose we have 2N elements and that the array A is indexed from 1 to 2N. Sort the elements in increasing order then swap A[2*(i+1)] with A[2*N-(2*i+1)] for
i=0 to (N-2)/2 when N is even
i=0 to (N-3)/2 when N is odd

So the running time is simply O(sort) + O(N), which if they are all integers, should be O(N).

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

The Algorithm will take O(N) time and O(Constant) space. Python.

``````def reArrange(elements):
elementCount = len(elements)
for i in range(0,elementCount)[::2]:
#subList will have atmost 3 elements
subList = (elements[i:i+3])

if(len(subList)>1):
#again subList is atmost 3 elements long.
#sorting 3 elements is a  constant time operation.
subList= sorted(subList)
#If the sublist has 3 elements then swap the last two
if(len(subList)>2):
temp = subList[-1]
subList[-1] = subList[-2]
subList[-2] = temp
#copy subList back to the element list
for index in range(0,len(subList)):
elements[i+index] = subList[index]
return elements

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

#output: 3, 10, 4, 6, 1, 7, 2, 9, 5, 8``````

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

``````int spl_sort(int *a, int len)
{
int temp;
int loop_length=len;

if (loop_length%2)
{
for (int i=1;i<loop_length-1;i++)
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
i++;
cout << a[i] << "\t" << a[i+1]<< "\n";
}

}

else
{
for (int i=1;i<loop_length-2;i++)
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
i++;
cout << a[i] << "\t" << a[i+1]<< "\n";
}
}

}``````

Basically, sort the array and swap 2 elements at a time starting from 2nd element... handle cases for odd n even number of elements

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

The below code will work in O(n), but not handle the duplicates.

{{
public static void reOrder(int[] A){
boolean smaller = true;
for (int i = 1; i<A.length; i++){
if ((smaller && A[i-1] > A[i]) || (!smaller && A[i-1] < A[i])){
int tmp = A[i];
A[i] = A[i-1];
A[i-1] = tmp;
}
smaller = !smaller;
}
}
}}

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

The following code works in O(n), but does not handle duplicates.

``````public static void reOrder(int[] A){
boolean smaller = true;
for (int i = 1; i<A.length; i++){
if ((smaller && A[i-1] > A[i]) || (!smaller && A[i-1] < A[i])){
int tmp = A[i];
A[i] = A[i-1];
A[i-1] = tmp;
}
smaller = !smaller;
}
}``````

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

THis won't work,, 123456789,

then it interchanges 23 and again interchanges 32

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

Here is some working Java code. It works well with all test cases suggested in this thread.
(1) Sort array in ascending order (using Quicksort in this case). O(n log n)
(2) Pick one element from begin and one from end.
(3) if last added element violates the rule, swap it with element X (for even positions) or X+1 (for odd positions), where X starts from 0 and is incremented with +2 after every swap.

``````public class ReorderTest {

static int[] theArray = new int[]{2,3,5,1};
static int[] newArray = new int[theArray.length];

public static void main(String[] args) {

Quicksort quickS = new Quicksort(); // Quicksort class not shown in this snippet
quickS.sort(theArray); // sorts the array in ascending order using Quicksort

int lastSwapPos = 0;
for (int i=0; i<theArray.length; i++)
{
if (i%2 == 0)
{
newArray[i] = theArray[i/2];
if ((i > 0) && (newArray[i] >= newArray[i-1]))
{
swapp(i, lastSwapPos);
lastSwapPos = (lastSwapPos+2 >= theArray.length) ? 0 : lastSwapPos+2;
}
}
else
{
newArray[i] = theArray[theArray.length-1-i/2];
if (newArray[i] <= newArray[i-1])
{
swapp(i, lastSwapPos+1);
lastSwapPos = (lastSwapPos+2 >= theArray.length) ? 0 : lastSwapPos+2;
}
}
}

for (int i=0; i<theArray.length; i++)
{
System.out.print(newArray[i] + " ");
}
}

private static void swapp(int i, int lastSwapPos) {
int temp = newArray[i];
newArray[i] = newArray[lastSwapPos];
newArray[lastSwapPos] = temp;
}

}``````

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

Assuming unique values, sort the entire array. Then place a pointer at the front and the back. S1 will be the first value in the array, S2 will be the last value in the array. Move both pointers forward by one. Then follow the above procedure.

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

Move one pointer forwards and the other backwards*

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

Construct a binary seach tree with the elements and do traverse tree in left-right-parent

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

``````public static void rearrange(int[] arr){
int i = 0;
while(i < arr.length - 1){
if(i % 2 == 0){
if(arr[i] > arr[i+1])
swap(arr, i, i + 1);
}else{
if(arr[i] < arr[i+1])
swap(arr, i, i + 1);
}
i++;
}
}

static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}``````

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

Use median of medians to find the middle, move it to middle, then recursively do same in each half. Of course we can handle border cases as they are trivial for me also. Giving more exact steps is beneath me.

I am a codechef topper.

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

Use median of medians to find the middle, move it to middle, then recursively do same in each half. Of course we can handle border cases as they are trivial for me also. Giving more exact steps is beneath me.

I am a codechef topper.

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

Use median of medians to find the middle, move it to middle, then recursively do same in each half. Of course we can handle border cases as they are trivial for me also. Giving more exact steps is beneath me.

I am a codechef topper.

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

1.) Sort the array.
2.) Starting from second element, swap 2nd and 3rd element, 4th and 5th element and so on.

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.