Facebook Interview Question SDE1s
Country: United States
Well, if array has even length it can be done in a single run across list - just for each pair of neighbours put max in odd position and min in even. So we just start cycle from beginning and compare each two elements. so, lets say 6, 5, 4, 3, 2, 1 will give us 5, 6, 3, 4, 1, 2
If array has odd length, like 6, 5, 4, 3, 2, 1, 100 then it's slightly trickier - we need to run second, backward cycle again, but starting from the last element
so, 6, 5, 4, 3, 2, 1, 100 after first cycle will be 5, 6, 3, 4, 1, 2, 100 and after second cycle
5, 6, 3, 4, 1, 100, 2
public void rearrange(int[] input) {
for(int i = 0; i < input.Length - 1; i+=2) {
if(input[i] > input[i + 1]) {
swap(input, i, i+1);
}
}
if (input.Length % 2 == 1) {
for(int i = input.Length - 1; i > 0; i -= 2) {
if(input[i] > input[i - 1]) {
swap(input, i, i - 1);
}
}
}
}
public void swap(int[] data, int from, int to) {
int temp = data[from];
data[from] = data[to];
data[to] = temp;
}
I don't think you need 2 rounds for odd. In both cases (even or odd n), instead of incrementing i by 2, increment it by 1 and ensure the odd place number is greater than even.
for(int i = 1; i < n; ++i) {
if (((i & 1) && nums[i] < nums[i-1]) || (!(i & 1) && nums[i] > nums[i-1])) {
swap(nums[i], nums[i-1]);
}
}
Note this only works if there are no duplicates. For example if arr = [1,2,2,3], The answer is [2,3,1,2] which won't be achieved by the above.
This leaves room for interpretation, I assumed that every value at an odd
index should be greater than the value at an adjacent even index, e.g.
a[0] < a[1] > a[2] < a[3] > a[4] < a[5] > ...
e.g.
1,2,3,4,5 --> 1 < 4 > 2 < 5 > 3
1,1,1,3,3 --> 1 < 3 > 1 < 3 > 1
0,1,1,3,3 --> 0 < 3 > 1 < 3 > 1
0,1,2,2,3 --> 2 < 3 > 1 < 2 > 0
0,2,2,2,3 --> 2 < 3 > 2 < .... no solution
Idea:
--
If the array was sorted, pick greater and smaller values as needed. Best is,
if all elements are max distance away from their origin because this allows
for longest sequences of equal values:
1,2,3,4,5,6,7,8 --> 1 < 6 > 2 < 7 > 3 < 8 > 4 < 9 > 5
1,1,1,1,2,2,2,2 --> 1 < 2 > 1 < 2 > 1 < 2 > 1 < 2 > 1
we can rearrange this in a simple for loop in O(n)
==> sorting requires O(lg(n)), not quite there yet.
Optimize for O(n) average time complexity (O(n^2) worst case time complexity)
--
Since we do not really care about sorting but only need to separate bigger
and smaller values, it's okay to partition the array in such a way around the
median. This can be done in O(n) average time in various ways (I used the
quick-sort partition method).
It needs to be modified in a way that all elements that are equal to the
median are not seperated by other elements. The standard partition property
left <= median < right won't work here because we could create something
like 1,5,2,5,3,5,6,7,8 where it should be 1,2,3,5,5,5,6,7,8 in order to hold
the wanted properties after rearranging
(1 < 5 => 5 < 6 > 3 < 7 > 5 < 8 > 3 vs. 1 < 5 > 2 < 6 > 3 < 7 > 5 < 8 > 5)
maybe somebody finds a solution to re-arrange in place without additional
space...
public class OddGreaterEven {
public static int[] rearrange(int[] input) {
assert (input != null && input.length > 0);
// rearrange around median
int n = input.length;
int s = 0, e = n;
int medianIdx = n / 2;
while(true) {
// picks a pivot in [s, e) and rearranges around that pivot
// such that there exist three sub-arrays:
// [s..l) where all values are < pivot
// [l..m) where all values are = pivot
// [m..e) where all values are > pivot
// returns last pivot index in the range [s, e)
swap(input, (s + e) / 2, s); // move the pivot to the start
int l = s; // [s, l) < pivot
int m = l + 1; // [l, m) = pivot
int u = m; // [m, u) > pivot
while(u < e) {
if(input[u] > input[l]) {
u++; // the new element is already in the > pivot part
} else if(input[u] == input[l]) {
swap(input, m++, u++); // add the new element ot the = pivot part
} else {
swap(input, l++, u); // add the new element to the < pivot part
swap(input, m++, u++); // add element before to the = pivot part
}
}
if(l > medianIdx) e = l;
else if (m < medianIdx) s = m;
else break;
}
// rearrange
int[] result = input.clone();
for(int i = 1; i < n; i += 2) result[i] = input[(n + 1) / 2 + i / 2];
for(int i = 2; i < n; i += 2) result[i] = input[i / 2];
// TODO: check if the solution is valid or not,
return result;
}
// helper swap function
private static void swap(int[] input, int i, int j) {
int t = input[i];
input[i] = input[j];
input[j] = t;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(rearrange(new int[]{2,3,0,1})));
System.out.println(Arrays.toString(rearrange(new int[]{5,2,3,4,1})));
System.out.println(Arrays.toString(rearrange(new int[]{1,2,3,4,5})));
System.out.println(Arrays.toString(rearrange(new int[]{1,1,1,3,3})));
System.out.println(Arrays.toString(rearrange(new int[]{1,0,1,3,3})));
System.out.println(Arrays.toString(rearrange(new int[]{2,2,0,1,3})));
System.out.println(Arrays.toString(rearrange(new int[]{5,1,5,8,7,5,6,2,3})));
System.out.println(Arrays.toString(rearrange(new int[]{7,3,8,2,5,6,1,5,5})));
System.out.println(Arrays.toString(rearrange(new int[]{0,2,2,2,3}))); // should produce a wrong result, no solution
/* output
[0, 2, 1, 3]
[2, 4, 1, 5, 3]
[2, 4, 1, 5, 3]
[1, 3, 1, 3, 1]
[0, 3, 1, 3, 1]
[0, 2, 1, 3, 2]
[1, 5, 2, 6, 3, 7, 5, 8, 5]
[3, 5, 2, 8, 1, 7, 5, 6, 5]
[0, 2, 2, 3, 2]
*/
}
}
@Michael.Karn.Ivanov
I'm not sure i understand what your desired property is: 6,5,7,9 gives me 5,6,7,9 with your code, which I'm not sure you would agree on being correct. If you did mean to create a[0]<a[1]>a[2]<a[3] and assume all distinct values, you might try this one:
static public int[] rearrange(int[] input) {
for(int i = 1; i < input.length - 1; i+=2) {
if(input[i] < input[i - 1]) {
swap(input, i, i - 1);
}
if(input[i] < input[i + 1]) {
swap(input, i, i+1);
}
}
return input;
}
that works because of any 3 distinct values at a[i-1],a[i],[a+1] it creates a[i-1]<a[i]>a[i+1] for odd i
then, if a[i+2] was smaller then a[i+1], a[i+1] would decrease and therefore still holding a[i]>a[i+1]. If a[i+2] is bigger than a[i+1] nothing changes and the chain is extended etc. etc.
#include <stdio.h>
int main(){
int arr[]={1,2,3,4,5,6,7,8,9};
int len = sizeof(arr)/sizeof(int);
int i;
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
for (i=0;i< len-1; i+= 2){
if (i - 1 > 0){
if (arr[i-1] > arr[i]){
int tmp;
tmp = arr[i-1];
arr[i-1]=arr[i];
arr[i]=tmp;
}
}
if (arr[i] < arr[i+1]){
int tmp;
tmp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=tmp;
}
}
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
}
#include <stdio.h>
int main(){
int arr[]={1,2,3,4,5,6,7,8,9};
int len = sizeof(arr)/sizeof(int);
int i;
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
for (i=0;i< len-1; i+= 2){
if (i - 1 > 0){
if (arr[i-1] > arr[i]){
int tmp;
tmp = arr[i-1];
arr[i-1]=arr[i];
arr[i]=tmp;
}
}
if (arr[i] < arr[i+1]){
int tmp;
tmp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=tmp;
}
}
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
}
#include <stdio.h>
int main(){
int arr[]={1,2,3,4,5,6,7,8,9};
int len = sizeof(arr)/sizeof(int);
int i;
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
for (i=0;i< len-1; i+= 2){
if (i - 1 > 0){
if (arr[i-1] > arr[i]){
int tmp;
tmp = arr[i-1];
arr[i-1]=arr[i];
arr[i]=tmp;
}
}
if (arr[i] < arr[i+1]){
int tmp;
tmp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=tmp;
}
}
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
}
#include <stdio.h>
int main(){
int arr[]={1,2,3,4,5,6,7,8,9};
int len = sizeof(arr)/sizeof(int);
int i;
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
for (i=0;i< len-1; i+= 2){
if (i - 1 > 0){
if (arr[i-1] > arr[i]){
int tmp;
tmp = arr[i-1];
arr[i-1]=arr[i];
arr[i]=tmp;
}
}
if (arr[i] < arr[i+1]){
int tmp;
tmp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=tmp;
}
}
for(i=0; i < len;i++)
printf("%d ", arr[i]);
printf("\n");
}
public static int[] rearrangeArray(int[] a)
{
int temp=0;
if(a.length<=1)
throw new IllegalArgumentException();
for(int i=1;i<a.length;i+=2)
{
System.out.println("i here is" + i);
if(a[i] < a[i-1])
{
temp=a[i-1];
a[i-1]=a[i];
a[i]=temp;
}
System.out.println(i + " i th is" + ", and i-1 is: "+ temp);
}
return a;
}
public static int[] rearrangeArray(int[] a)
{
int temp=0;
if(a.length<=1)
throw new IllegalArgumentException();
for(int i=1;i<a.length;i+=2)
{
System.out.println("i here is" + i);
if(a[i] < a[i-1])
{
temp=a[i-1];
a[i-1]=a[i];
a[i]=temp;
}
System.out.println(i + " i th is" + ", and i-1 is: "+ temp);
}
return a;
}
The question states that the number at the odd index must be greater than the number at the even index but it doesn't specify which index that means that the number at the first odd position must be greater than any number at any even position. To do this we have to compute the median of the vector and assign the values accordingly. There are several ways to compute the median in linear time, you can use the Median of medians algorithm or use a heap. Here is the solving code in python
- Fernando May 15, 2017import heapq def rearrange(input_vector): # Compute the median using a heap. Total cost 2n + n/2 heap = input_vector[:] # This has cost n heapq.heapify(heap) # This has cost n for x in xrange(len(input_vector) / 2): # This has cost n / 2 median = heap.pop() # The rest of the code has cost n, so the total cost of the function # is 3n + n/2 which is O(n) solution = [ 0 ] * len(input_vector) even = 1 odd = 0 for v in input_vector: if v < median: solution[odd] = v odd += 2 else: solution[even] = v even += 2 return solution