Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Only way I could think of minimizing the number of move operations is if the array is already sorted in chunks with some un-sorted jumbled numbers in between them all of which are smaller than the first sorted chunk.
Then move them by moving them starting with largest among them.
Or start by finding the max element and if its already in the last position skip it and go on as long as we have a sorted chunk already in correct position at the end of the array. Then keep them moving each element to the front starting from largest among them.
I dont know if we can solve it in less than O(n^2).
public static void sort(int [] arr) {
for(int s = 0;s<arr.length;s++) {
moveFirst(arr,findMax(arr,s,arr.length-1));
}
}
public static int findMax(int [] arr, int s, int e) {
int idx = s;
int tmp = arr[s];
for(int i=s;i<=e;i++) {
if( arr[i] > tmp ) {
idx = i;
tmp = arr[i];
}
}
return idx;
}
public static void moveFirst(int [] arr,int idx) {
int tmp = arr[idx];
while(idx>0) {
arr[idx] = arr[--idx];
}
arr[0] = tmp;
}
Yes selection sort. This code finds biggest and puts in the front of the array. MoveToFront(x) assumes x is an index or else we will need to write a find function.
public void sort(){
for (int i = 0; i < a.length; i++){
int big = findBiggestIndex(i);
move(big);
}
}
private int findBiggestIndex(int x) {
int big = x;
for(int i = x ; i< a.length; i++){
if(a[i] > a[big])
big = i;
}
return big;
}
public void move(int x){
int temp = a[x];
for (int i = x; i > 0; i--){
a[i] = a[i-1];
}
a[0] = temp;
}
func moveToFront(arr: [Int], max: Int, atIndex: Int) -> [Int]{
var newArr = arr
newArr.removeAtIndex(atIndex)
newArr.insert(max, atIndex: 0)
return newArr
}
func sortArray(arr: [Int]) {
var newArr = arr
for i in 0..<newArr.count {
var max = 0
var maxIndex = -1
for j in i..<newArr.count {
if newArr[j] > max {
max = newArr[j]
maxIndex = j
}
}
newArr = moveToFront(newArr, max: max, atIndex: maxIndex)
print(newArr)
}
print(newArr)
}
sortArray([12,3,4,3,24,22,4,224,453,232])
private static void MoveToFront(int[] arr, int i)
{
if(i >= arr.Length || i < 1)
{
return;
}
int t = arr[i];
while(i > 0)
{
arr[i] = arr[i - 1];
--i;
}
arr[i] = t;
}
public static int SortUsingMoveToFront(int[] arr)
{
int calls = 0;
while (true)
{
int max = Int32.MinValue;
int maxI = 0;
for (int i = 0; i < arr.Length; ++i)
{
if(arr[i] < arr[0] && arr[i] > max)
{
maxI = i;
max = arr[i];
}
}
if(maxI == 0)
{
break;
}
MoveToFront(arr, maxI);
calls++;
}
return calls;
}
public void test(int[] nums){
Set<Integer> visited = new HashSet();
int max = 0, secondMax = -1;
for(int i=0;i<nums.length;i++){
if(nums[i]>nums[max]){
max = i;
}
}
visited.add(nums[max]);
int times = nums.length;
int len = nums.length;
while(times>0){
int i =0;
secondMax = -1;
while(i<len){
if(!visited.contains(nums[i])&&secondMax ==-1&& i!=max){
secondMax = i;
}
else if(!visited.contains(nums[i])&&nums[i]>max[secondMax]){
secondMax = i;
}
i++;
}
visited.add(nums[max]);
if(secondMax>max){
Move(nums[secondMax]);
max =0;
}else{
max = secondMax;
}
times--;
}
}
Swift:
func moveToFront(idx: Int, array: inout [Int]) {
let num = array[idx]
array.remove(at: idx)
array.insert(num, at: 0)
}
func moveToFrontSort(array: inout [Int]) {
guard array.count > 1 else { return }
for sortCursor in 0..<array.count {
var maxIdx = sortCursor
for idx in maxIdx..<array.count {
if array[idx] > array[maxIdx] {
maxIdx = idx
}
}
moveToFront(idx: maxIdx, array: &array)
}
}
var array = [12, 3, 4, 24, 22, 4, 224, 453, 232]
moveToFrontSort(array: &array)
public class sortedarraysquare {
public static void sortsquare(int[] array)
{
int negativeIntIndex = 0;
for (int i=0 ;i<array.length-1;i++)
{
if(array[i] > array[i+1])
{
array = movearray(0,i+1,array);
}
}
for(int i=0;i<array.length;i++)
{
System.out.println(array[i] );
}
}
public static int[] movearray(int fromIndex,int toIndex,int[] array)
{
int temp = array[toIndex];
for(int i = toIndex;i>= fromIndex+2;i--)
{
array[i] =array[i-1];
}
int temp2 = array[fromIndex];
array[fromIndex+1]=temp2;
array[fromIndex] = temp;
return array;
}
public static void main (String args[])
{
int[] array = new int[]{1,2,6,8,-10,11,-15,-16,17};
sortsquare(array);
}
}
What about nlogn solution? Sort it like in merge sort:
- pick up a random index pivot, move to front
- do pass over array all values larger than pivot move to front
- at this point array is partitioned left pivot right where left is larger than pivot and right
- do similar partition recursively on left portion
- end recursion when o ly 2 or less elements left
- when left recursion returns do right.
- in the end array will be sorted in ascending order left to right
- one catch is when inserting elements in front position of pivot moves this can be fixed by returning number of insertions from recursion and adjusting pivot
no, if B is before A then we leave it as is, then, how does it guarantee that it is in sorted order. consider this example
input : 5 3 10 1 2 8 6 after sort it would be 1 2 6 8 5 3 10, as 5 and 3 where before 10, they didn't get moved they are not in the order.
I think we need O(n) MoveToFront calls.
var len = array.length;
for (var i = 0; i < len; i++) {
moveToFirst(array, findMax(array, i, len));
}
return array;
}
function findMax(array, start, len) {
var big = array[start];
var index = start;
for (var i = start+1; i < len; i++) {
if (array[i] > big) {
big = array[i];
index = i;
}
}
return index;
}
function moveToFirst(array, index) {
var v = array[index];
for (var i = index; i > 0; i--) {
array[i] = array[i-1];
}
array[0] = v;
return array;
}
We can use bubble sort technique.
Look for adjacent elements and swap i.e for each i , if arr[i] < arr[i-1] , call moveToFront(i)
Keep doing until on each pass we have atleast one moveToFront calls ( use boolean flag to know that).
//Complete code
public class SortArrayMoveFront {
public static void moveToFront(int[] arr , int pos){
int tmp = arr[pos];
for(int j=pos;j>0;j--){
arr[j] = arr[j-1]; // shift
}
arr[0] = tmp;
}
//bubbles sort technique O(N^2)
public static void sortArray(int[] arr){
boolean moved = true;
while(moved){
moved=false;
for(int i=1;i<=arr.length-1;i++){
if(arr[i] < arr[i-1]){
moveToFront(arr,i); // moved
moved=true; // a move was made
}
}
}
}
public static void main(String[] args) {
//int[] arr = {11,4,5,4,7};
int[] arr = {12,3,4,3,24,22,4,224,453,232};
sortArray(arr);
//moveToFront(arr,0);
System.out.println(Arrays.toString(arr));
}
}
#include<bits/stdc++.h>
using namespace std;
void moveFront(vector<int>& a,int num)
{
int i = find(a.begin(),a.end(),num) - a.begin();
int temp = a[i];
for(int j=i-1;j>=0;--j)
{
a[j+1] = a[j];
}
a[0] = temp;
for_each(a.begin(),a.end(),[](int i){cout << i << " ";});
cout << "\n";
}
int main()
{
vector<int> arr={0,2,3,4,5,6,7,8,1};
int n = arr.size();
priority_queue<int> pq;
for(int i: arr)
{
pq.push(i);
}
int max1 = pq.top();
pq.pop();
int begin = find(arr.begin(),arr.end(),max1) - arr.begin();
int count = 1;
while(pq.top()==arr[begin-1])
{
count++;
pq.pop();
begin--;
}
int moves = n - count;
cout << "minimum moves " << moves <<"\n";
for(int i=0;i<moves;++i)
{
int elem = pq.top();
pq.pop();
moveFront(arr,elem);
}
}
Use selection sort since it utilizes the least swap(i.e. Move to front)
function sort_array($arr) {
$arrCount = count($arr);
for($i=0;$i<$arrCount;++$i) {
$maxKey=$i;
$maxKeySet = false;
for($j=$i; $j<$arrCount; ++$j){
if($arr[$j]>=$arr[$maxKey]){
$maxKey = $j;
$maxKeySet = true;
}
}
if($maxKeySet){
$arr = $this->moveToFront($arr,$maxKey);
}
}
return $arr;
}
function moveToFront($arr, $moveKey){
$arrCount = count($arr);
$newArr[0] = $arr[$moveKey];
$z = 0;
for($i=0;$i<$arrCount; ++$i){
if($i!=$moveKey){
$newArr[++$z] = $arr[$i];
}
}
return $newArr;
}
1. Find the largest number (I called it A) from the array and remember its index.
- jiahuang July 07, 20162. Find the next largest number (I called it B) from the array. If B comes before A, we're good, otherwise move B to the front, MoveToFront(B).
3. A = B, and repeat (2). it needs to loop n-2 times to check all other numbers.
It's not the fastest algorithm, but it should be very easy to understand. The time complexity is O(n^2).