Google Interview Question Interns
Country: United States
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;
}
We can use Median of Medians or Selection algorithm in quick sort to find the median of an unsorted array in linear time
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] << " ";
}
>>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
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?
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[1])
{
temp = a[i];
a[i] = a[1];
a[1] = 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
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] << " ";
}
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;
}
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[400];
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]<<" ";
}
}
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"
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)
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){
list.add((int) (Math.random()*10000));
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++;
}
}
}
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).
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
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
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;
}
}
}}
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;
}
}
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;
}
}
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.
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;
}
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
- kkr.ashish November 24, 2013complexity 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)