Facebook Interview Question SDETs
Country: United States
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;
}
}
}
}
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;
}
}
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
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;
}
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[0]);
alternateSort(a, n);
for(int i=0;i<n;i++)
cout <<a[i]<<" ";
cout << endl;
return 0;
}
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)
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";
}
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)
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)
# 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)
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.
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);
}
}
}
public static int[] SortAlternatly(int[] inputarray)
{
int count = 1;
int temp = inputarray[0];
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;
}
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]);
}
}
}
public static void main(String[] args)
{
ArrayList<Integer> arr=new ArrayList<Integer>();
List<Integer> list=new LinkedList<Integer>();
arr.add(5);
arr.add(3);
arr.add(1);
arr.add(7);
arr.add(9);
arr.add(2);
arr.add(17);
arr.add(14);
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)
{
list.add(arr.get(ln));
ln--;
}
else{
list.add(arr.get(i-n));
n++;
}
}
System.out.println("list "+list);
}
/*
*
* 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:
* [0] = '5' is max
* [1] = '1'. since off[4] is now clear, we put '4' in it
* [2] = '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[10];
int in_in_place[10];
int N, size_of_arr;
N = 5;
size_of_arr = sizeof(in_0[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[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;
}
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[0])
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[0]
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)
public class FacebookSDET1 {
public static void main(String[] args) {
int[] a= {2, 4, 3, 5, 1};
int[] r=sortingMechanism(a);
System.out.println(Arrays.toString(r));
}
public static int[] sortingMechanism(int[] a)
{
Arrays.sort(a);
int n=a.length-1;
int i=0;
while(i<n-1)
{
shift(i,a);
System.out.println(Arrays.toString(a));
i+=2;
}
if(a.length%2==0)
{
int temp=a[n];
a[n]=a[n-1];
a[n-1]=temp;
}
return a;
}
private static int[] shift(int i,int[] arr) {
int element=arr[arr.length-1];int j;
for(j=arr.length-1;j>i;j--)
{
arr[j]=arr[j-1];
}
arr[j]=element;
return arr;
}
}
public static int [] reArrangeAnArray(int [] arr) {
int [] newArr = new int [arr.length];
Arrays.sort(arr);
int p1 = 0;
int p2 =arr.length-1;
int idx = 0;
while(idx < arr.length) {
if(idx!= arr.length) {
newArr[idx++] = arr[p2];
p2--;
}
if(idx != arr.length) {
newArr[idx++] = arr[p1];
p1++;
}
}
return newArr;
}
public static int [] reArrangeAnArray(int [] arr) {
int [] newArr = new int [arr.length];
Arrays.sort(arr);
int p1 = 0;
int p2 =arr.length-1;
int idx = 0;
while(idx < arr.length) {
if(idx!= arr.length) {
newArr[idx++] = arr[p2];
p2--;
}
if(idx != arr.length) {
newArr[idx++] = arr[p1];
p1++;
}
}
return newArr;
}
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.
- Stephan April 06, 2017// 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; }