## Facebook Interview Question for SDETs

• 1
of 1 vote

Country: United States

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

The other solutions proposed so far all run in O(n^2). However, the more interesting question is whether one can do better than O(n^2) without extra data structures. Below is my solution, running in O(n log n).

Let me briefly explain it as follows. Let's call an array arr of length n "good", if the following holds:
1) The roundup(n/2) lowest values of arr all reside at indices 0, 2, 4, ... and are sorted in non-decreasing order,
2) the remaining larger values all reside at indices 1, 3, 5, ..., and are also sorted in non-decreasing order.
For example, the following arrays are good:
{1, 5, 2, 6, 3, 7, 4}
{12, 34, 14, 41, 21, 55, 33, 60}

Now, if an array is good, it can easily be transformed into the required ordering in linear time, by carefully reversing twice: once the whole array (with special treatment of odd array lengh) and once the elements at every second position.

Therefore, the remaining task is to make the input array a good one.
We can achieve this by first sorting the array into non-decreasing order, and then applying a divide-and-conquer approach. In essence, in order to merge to good subarrays, we swap the higher values of the left subarray with the lower values of the right one. Again we must be especially careful of odd subarray lenghts.

It should be noted that O(log n) memory is needed on the stack.

``````// make arr[] good in index range [l,r)
void solve(int arr[], int l, int r) {
if(r-l==3) {
swap(arr[l+1], arr[l+2]);
} else if(r-l>3) {
int mid = (l+r) / 2;
solve(arr,l,mid);
solve(arr,mid,r);

for(int i=l+1,j=mid; i<mid; i+=2,j+=2) {
swap(arr[i], arr[j]);
}
if((mid-l)%2) {
if((r-mid)%2) {
for(int i=r-1; i>mid; i--)
swap(arr[i], arr[i-1]);
} else {
for(int i=r-1; i>mid; i-=2)
swap(arr[i], arr[i-1]);
for(int i=mid-2; i>l; i-=2)
swap(arr[i], arr[r-1]);
}
} else {
if((r-mid)%2) {
for(int i=mid-1; i>l; i-=2)
swap(arr[i], arr[r-1]);
}
}
}
}

void reverse(int arr[], int l, int r, int step) {
while(l<r) {
swap(arr[l], arr[r]);
l+=step; r-=step;
}
}

void sort_alternate(int arr[], int n) {
sort(arr,arr+n);
solve(arr,0,n);

reverse(arr, 0, n-1-(n%2), 1);
reverse(arr, 1, n-1-(n%2), 2);
}

int main() {
int n = 5;
int arr[n] = {2,4,3,5,1};
sort_alternate(arr, n);

return 0;
}``````

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

This is my quick and dirty Ansi C solution.
Didn't put much thought into it. Just the first solution that came to my mind to try and solve it in less than 20 minutes.

``````void sortAlternate(int* nums, int size){
int* work=nums;
int aux;
int i,n;

for(n=0;n<size;n+=2){
for(i=n;i<size;i++){
int* next=work+i;
int* big=work;
int* little=work+1;

if(*next>*big){
aux=*big;
*big=*next;
*next=aux;
}

if(*next<*little){
aux=*little;
*little=*next;
*next=aux;
}
}
}
}``````

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

This is my quick and dirty solution in ANSI C. It's the first solution that came to my mind trying to solve it in less than 20 minutes. Feel free to propose better ones.

``````void sortAlternate(int* nums, int size){
int* work=nums;
int aux;
int i,n;

for(n=0;n<size;n+=2){
for(i=n;i<size;i++){
int* next=work+i;
int* big=work;
int* little=work+1;

if(*next>*big){
aux=*big;
*big=*next;
*next=aux;
}

if(*next<*little){
aux=*little;
*little=*next;
*next=aux;
}
}
}
}``````

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

``````public class YourClassNameHere {
public static void main(String[] args) {
int[] arr = {2,3,4,5,1};
sortAlternate(arr);
}

public static void sortAlternate(int[] arr){
boolean flag = true;
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(flag){
if(arr[j] > arr[i])
swap(arr,j,i);
}
else{
if(arr[j] < arr[i])
swap(arr,j,i);
}
}
flag = !flag;
}
}

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

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

``````public class YourClassNameHere {
public static void main(String[] args) {
int[] arr = {2,3,4,5,1};
sortAlternate(arr);
}

public static void sortAlternate(int[] arr){
boolean flag = true;
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(flag){
if(arr[j] > arr[i])
swap(arr,j,i);
}
else{
if(arr[j] < arr[i])
swap(arr,j,i);
}
}
flag = !flag;
}
}

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

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

public class YourClassNameHere {
public static void main(String[] args) {
int[] arr = {2,3,4,5,1};
sortAlternate(arr);
}

public static void sortAlternate(int[] arr){
boolean flag = true;
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(flag){
if(arr[j] > arr[i])
swap(arr,j,i);
}
else{
if(arr[j] < arr[i])
swap(arr,j,i);
}
}
flag = !flag;
}
}

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

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

one

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

``````public class YourClassNameHere {
public static void main(String[] args) {
int[] arr = {2,3,4,5,1,9,8};
sortAlternate(arr);
}

public static void sortAlternate(int[] arr){
boolean flag = true;
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(flag){
if(arr[j] > arr[i])
swap(arr,j,i);
}
else{
if(arr[j] < arr[i])
swap(arr,j,i);
}
}
flag = !flag;
}
}

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

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

``````public class SortAnArrayIntoSequenceOfHighestAndLowest1 {

public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] res = sort(arr);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + " ");
}
}

static int[] sort(int[] arr){
if(arr == null) return arr;
if(arr.length == 1) return arr;

int k = 0;
boolean getMax = true;
while(k < arr.length){
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minIndex = -1;
int maxIndex = -1;
for (int i = k; i < arr.length; i++) {
if(!getMax && min > arr[i]){
min = arr[i];
minIndex = i;
}
if(getMax && max < arr[i]){
max = arr[i];
maxIndex = i;
}
}
if(!getMax){
int m = arr[k];
arr[k] = arr[minIndex];
arr[minIndex] = m;
}else{
int m = arr[k];
arr[k] = arr[maxIndex];
arr[maxIndex] = m;
}
k++;
getMax = !getMax;
}
return arr;
}``````

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

What my idea is sort array
Then start picking element from last and replace with starting element and

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

``````void sortAlternate(int [] ip){

int index=0;
boolean max=true;
int tempIndex =0;
while(index<ip.length-1){
for(int i=index;i<ip.length;i++){
if(max){
if(ip[i]>ip[tempIndex]){
tempIndex=i;
}
}else{
if(ip[i]<ip[tempIndex]){
tempIndex=i;
}
}

}
swap(ip,tempIndex,index);
index++;
max=!max;
}

}

void swap(int[] ip, int a,int b){
int temp = ip[a];
ip[a]=ip[b];
ip[b]=temp;
}``````

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

Sort the array and then arrange in place. This solution takes O(nlogon) time complexity and O(1) space.

``````#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

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

void alternateSort(int a[], int n)
{
sort(a, a+n, greater<int>());
int step = n/2; //number of items to adjust

int pos = 1;
for(int i=0;i<step;i++)
{
int index = n-1;
int key = a[index];
while(index != pos)
{
swap(a[index-1], a[index]);
index--;
}
pos +=2; //small number are only at odd positions
}
}

int main() {
int a[] ={2, 4, 3, 5, 1};
int n = sizeof(a)/sizeof(a);
alternateSort(a, n);
for(int i=0;i<n;i++)
cout <<a[i]<<" ";
cout << endl;
return 0;
}``````

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

With Extra Space:

create sorted array [1,2,3,4,5] which is O(nlogn)
then take 2 pointer one at first and one at last, then in original array overwrite the elements by put largest first then smallest, and increase pointer one by one until they cross each other.

So this algorithm will run in O(nlogn)

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

Sort the array
and circular shift every subarray starting from 0-end, 2-end, 4-end etc etc.

``````#include <iostream>
#include <cstdlib>

void ccshift(int arr[], int start, int end){

std::cout << start << " " << end << "\n";

int temp = arr[end];

for( int i = end; i > start ; i--){
arr[i] = arr[i-1];
}

arr[start] = temp;

}

void solve(int arr[], int size){

int size_half = size/2;
int start = 0;
int end   = size -1;
for(int i = 0 ; i < size_half; i = i+1){
ccshift(arr, start, end);
start = start+2;

}

}

int main(){

int arr[] = {1,2,3,4,5,6};
int size_arr= 6;

solve(arr, size_arr);

for(int i = 0 ; i < size_arr; i++){
std::cout << arr[i] << " ";
}
std::cout << "\n";

}``````

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

``````import random

num_list = []
out_list = []

n = int(input('Please enter the number of elements : '))

while len(num_list) <= n:
num_list.append(random.randrange(1,100))

num_list.sort()
num_list.reverse()
print(num_list)

length = len(num_list)
mid = int(length / 2)
i = 0

while i < mid:
out_list.append(num_list[i])
out_list.append(num_list[length-i-1])
i += 1

print(out_list)``````

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

import random

num_list = []
out_list = []

n = int(input('Please enter the number of elements : '))

while len(num_list) <= n:
num_list.append(random.randrange(1,100))

num_list.sort()
num_list.reverse()
print(num_list)

length = len(num_list)
mid = int(length / 2)
i = 0

while i < mid:
out_list.append(num_list[i])
out_list.append(num_list[length-i-1])
i += 1

print(out_list)

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

# Python 3

import random

num_list = []
out_list = []

n = int(input('Please enter the number of elements : '))

while len(num_list) <= n:
num_list.append(random.randrange(1,100))

num_list.sort()
num_list.reverse()
print(num_list)

length = len(num_list)
mid = int(length / 2)
i = 0

while i < mid:
out_list.append(num_list[i])
out_list.append(num_list[length-i-1])
i += 1

print(out_list)

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

1. Sort the numbers
2. Reverse the second half (i.e. if n is odd reverse last n/2 + 1 numbers). For example: if
sorted nums = {1,2,3,4,5} after reversal nums = {1,2,5,4,3}
3. Keep 2 pointers i = 0 and j = n-1 (if n is even) or n-2 if (n is odd). In odd case after reversal the last number is at its final position so we start from n-2
4. Keep 2 temporary variables (temp_i and temp_j). These variables will store the elements originally in the locations being updated
5. Now do the following:

``````#define A(i) nums[(1 + 2*(i)) % (n | 1)]
int i = 0;
int j = n - (1 + n%2); // for even and odd as explained above
int temp_i = nums[i];
int temp_j = nums[j];
int cnt = 0;
while(cnt < n/2) {
/* places nums stored in temp_i, temp_j in their final position and loads the numbers currently in those locations into these temp vars for next round */
swap(A(i), temp_i);
swap(A(j), temp_j);
i = (1 + 2*(i)) % (n | 1);
j = (1 + 2*(j)) % (n | 1);
cnt++;
}``````

Thus, O(nlogn) time complexity and O(1) space. This is similar to wiggly sort.

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

Maintain a min and max heap.
Pick elements from top of max heap followed by top of min heap until the elements on top of the two heaps are the same at which pick from either of the heap and return.

o(n) memory, o(nlogn) speed.

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

find the greatest element in array(index 0 to n) and move it to beginning of subarray (to index 1). Then in remaining subarray (index 1 to n) find the smallest element and move it to begining of subarray (to index 2).
recurse this solution to remaining subarray starting from index 2 to n.

``````public class SortIntegers{
public void sortAlternate(int[] nums, int startIndx, int endIndx){
if(startIndx >= endIndx) return;
greatestFirst(nums, startIndx, endIndx);
smallestFirst(nums, ++startIndx, endIndx);
sortAlternate(nums, ++startIndx, endIndx);
}

public void greatestFirst(int[] nums, int startIndx, int endIndx){
for(int i=startIndx; i< endIndx; i++){
if(nums[i] > nums[startIndx])
swap(nums, i, startIndx);
}
}

public void smallestFirst(int[] nums, int startIndx, int endIndx){
for(int i=startIndx; i< endIndx; i++){
if(nums[i] < nums[startIndx])
swap(nums, i, startIndx);
}
}
}``````

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

Python solution: Sort array first, pop from last and insert in the needed position.

``````array = sorted([2, 4, 3, 1])

i, j = 0, len(array)-1

while i < j:
array.insert(i, array.pop(j))
i += 2

print array``````

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

Python solution. Sort the array first and then re-arrange:

``````def reArrange(array):
array = sorted(array)
i, j = 0, len(array)-1
while i < j:
array.insert(i, array.pop(j))
i += 2
return array``````

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

public static int[] SortAlternatly(int[] inputarray)
{
int count = 1;
int temp = inputarray;

for (int k = 0; k < inputarray.Length - 1; k++)
{
for (int i = 0; i < inputarray.Length - 1; i++)
{
for (int j = k ; j < inputarray.Length - 1; j++)
{

if (count % 2 != 0){
if (inputarray[j] < inputarray[j + 1]){
temp = inputarray[j];
inputarray[j] = inputarray[j + 1];
inputarray[j + 1] = temp;
}
}
else{
if (inputarray[j] > inputarray[j + 1]){
temp = inputarray[j];
inputarray[j] = inputarray[j + 1];
inputarray[j + 1] = temp;
}
}
}
}

count = count + 1;
}
return inputarray;
}

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

``````public class SortAlter {
public static void main(String args[]){
int[] arr = new int[]{4,3,2,1,5};
Arrays.sort(arr);
int tmp;
int len = arr.length - 1;
int n = 0;
while(n <= len/2) {
for (int i = n; i <= len; i++) {
tmp = arr[i];
arr[i] = arr[len];
arr[len] = tmp;
}
n = n + 2;
}
for(int i = 0; i <= len; i++){
System.out.println(arr[i]);
}

}
}``````

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

public static void main(String[] args)
{

ArrayList<Integer> arr=new ArrayList<Integer>();

Collections.sort(arr);
System.out.println("Sorted array "+arr);
int ln=arr.size()-1;
int n=2;

for(int i=1;i<=arr.size();i++)
{
if(i%2!=0)
{
ln--;
}
else{
n++;
}

}
System.out.println("list "+list);
}

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

There will be no O(nlogn) solution using O(1) space. Recursion does uses extra space, it's not O(1).

If we can solve this O(nlogn) and O(1) space, we can easily convert the result to sorted array in-place in O(n), that means we can sort an array in O(nlogn) using O(1), which is not true.

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

``````/*
*
* if we can use extra space (O(N)) then:
* sort the array. time=O(N * log(N))
* using 2 pointers (from min & max), merge into output. this is linear time.
*
* without extra space
* ----------------------
* we start by sorting the array
* now we interleave the elements on one end & use the other end (from which we removed min values) as temporary store for the elements we removed
* e.g.:
* we have a sorted array: 5,4,3,2,1
* we start from left:
*  = '5' is max
*  = '1'. since off is now clear, we put '4' in it
*  = '4' & '3' is put instead of it
* ...
*
* so the removal of minimal elements, makes space for a queue of large elements that we need to use
* but this is quite complicated considering that we push into queue before poping hence we have 2 elements more than space. and since we usually need space largers by 1 from number of elements, this becomes complicated
*  	further complication is by the fact thatsome traversal might inersect with the queue - to prevent, we'll need the queue to stay at end without copying it.
*  	this is too complicated
*
* simpler method, linear time, no extra space
* --------------------------------------------
* we can make a chain of element switch.
* when we pick an element, we can tell where it should go to (index).
* the destination must be another element that isnt in its place, bcz if it was in its place, we wouldnt have found something that needs to e in that same place (since each element has a single valid offset)
* so if we pick an element, move it to its only valid location & pick the item already there, we should have a chain of replacements that puts all elements in their place.
*
* we can do this loop with pull (what element will be moved into an offset) or push (where do i push my element, taken from index ?)
* if we do a push, it writes in an offset that is in use & that element must be pushed again to another busy offset that will be pushed .....
* if we do a pull, then we pick an offset & pull the right element to that offset. but then we need to push the element we overwrote.
* so it seems we need to do push in any case, so lets use just it.
* compute how many moves are required.
* start from last element
* while not all moves done {
*  	save dest value aside.
*  	do the push from src offset to dest.
*  	the dst offset becomes src offset
*  }
*
*
*/

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>

int qsort_descending_comp(const void	*_v1,
const void	*_v2)
{
const int		*v1 = (const int*)_v1;
const int		*v2 = (const int*)_v2;

if (*v1 < *v2) {
return 1;
} else if (*v1 == *v2)
return 0;
else
return -1;
}

void sort_alternate(int		*arr,
int		N)
{
int		tmp[N];

qsort(arr, N, sizeof(*arr), qsort_descending_comp);
memcpy(tmp, arr, N * sizeof(*arr));
for (int i = 0; i < N/2; i++) {
arr[2*i  ] = tmp[i];
arr[2*i+1] = tmp[N-1-i];
}
if (N % 2) {
arr[N-1] = tmp[N/2];
}
}

void sort_alternate_in_place(int		*arr,
int		N)
{
int 	n_moves = (N % 2) ? ((N-1) - 1) : N-1;
int		q_head, q_tail;	// head & tail of queue of large elements that temporarily reside in end of array
int 	from, to;		// array indice for move of element
int		val_old, val_new;			// value that is being moved

qsort(arr, N, sizeof(*arr), qsort_descending_comp);
if (N <= 2)
return;

for (from = N-1, val_old = arr[from]; n_moves > 0 ; n_moves--) {
assert (from >= 0 && from < N);
if (from < (N+1)/2) {
to = 2*from;
} else /*if (from > N/2)*/{
to = 2*(N - from - 1) + 1;
}
val_new = arr[to];
arr[to] = val_old;
from = to;
val_old = val_new;
}
}

int main ()
{
const int		in_0[] = {1,2,3,4,5,6};
int				in_extra_mem;
int				in_in_place;
int				N, size_of_arr;

N = 5;
size_of_arr = sizeof(in_0) * N;
memcpy(in_extra_mem, in_0, size_of_arr);
memcpy(in_in_place,  in_0, size_of_arr);
sort_alternate(in_extra_mem, N);
sort_alternate_in_place(in_in_place, N);
assert(memcmp(in_extra_mem, in_in_place, size_of_arr) == 0);

N = 6;
size_of_arr = sizeof(in_0) * N;
memcpy(in_extra_mem, in_0, size_of_arr);
memcpy(in_in_place,  in_0, size_of_arr);
sort_alternate(in_extra_mem, N);
sort_alternate_in_place(in_in_place, N);
assert(memcmp(in_extra_mem, in_in_place, size_of_arr) == 0);

return 0;
}``````

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

``````def wierd_sort():
l = [2, 4, 3, 5, 1]
l = partition(l)
m = []
l = l[::-1]
print(l)
n = len(l)
while len(l)>0:
m.append(l)
l.pop(0)
if len(l)>1:
m.append(l[-1])
l.remove(l[-1])
print(m)

# Quick sort module used here
def partition(x):
less = []
greater = []
pivot= []
if len(x)>0:
indx = x
for i in x:
if int(i) < int(indx):
less.append(i)
elif int(i) == int(indx):
pivot.append(i)
elif int(i) > int(indx):
greater.append(i)
return(partition(less)+pivot+partition(greater))

else:
return(x)``````

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.