Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
To elaborate a little.
Suppose you have rearranged a_1, a_2, .., a_k to have the property.
The claim is that given a_{k+1}, you either have to do nothing, or swap with the last element (in the rearranged version of a_1, a_2, ..., a_k) to get a valid rearrangement of a_1, a_2, ..., a_k, a_{k+1}.
Hey in both the if check...you are performing the same operation...M i missing out something ?
@TOpcoder:
3,7,5,8,4,9 is a perfectly valid ouput. Why does it have match the _sample_ output?
This code is giving correct outputs for all the inputs I tried: ideone(.)com(/)EjnCSV
But I still don't get the logic :)
O(nlogn)
Sort first, then swap elements from 1...n-2 [a(0-n-1)] array
import java.util.Scanner;
public class LessGreatArray
{
public int n;
int a[];
public LessGreatArray()
{
Scanner s = new Scanner(System.in);
System.out.println("Enter the size");
n = s.nextInt();
System.out.println("Enter values");
int i=0;
a = new int[n];
while(i < n)
{
a[i] = s.nextInt();
i++;
}
}
public static void main(String args[])
{
LessGreatArray x = new LessGreatArray();
x.lessGreatSort();
}
public void lessGreatSort()
{
MergeSorter m = new MergeSorter(a);
a = m.mergeSort(a);
for(int i=0;i<a.length;i++)
{
if(i==0 || i == a.length-1)
{
continue;
}
//swap(a[i+1],a[i]);
int x = a[i+1];
a[i+1] = a[i];
a[i] = x;
i++;
}
System.out.println("The less great sort array is : ");
int i=0;
while(i<a.length)
{
System.out.println(a[i]);
i++;
}
}
public void swap(int a, int b)
{
int temp = a;
a = b;
b = temp;
}
}
public class MergeSorter
{
int n;
int a[];
public MergeSorter(int x[])
{
n = x.length;
int i = 0;
a = new int[n];
while(i<n)
{
a[i] = x[i];
i++;
}
}
public int [] mergeSort(int a[])
{
if(a.length == 1)
return a;
int start = 0;
int end = a.length -1;
int mid = (end - start )/2;
int left[] = new int [mid+1];
int right[] = new int [end - mid];
for(int i=0;i<=mid;i++)
left[i] = a[i];
for(int j=mid+1;j<=end;j++)
right[j-(mid+1)] = a[j];
left = mergeSort(left);
right = mergeSort(right);
int k[] = new int[left.length + right.length];
merge(left,right,k);
return k;
}
private void merge(int[] left, int[] right, int[] k)
{
int i=0;
int j=0;
int m=0;
while(m<k.length)
{
if(i < left.length && j < right.length && left[i] <= right[j])
{
k[m] = left[i];
i++;
}
else if(i < left.length && j < right.length && left[i] > right[j])
{
k[m] = right[j];
j++;
}
else if(i == left.length)
{
for (int u=j;u<right.length;u++)
{
k[m] = right[u];
m++;
}
}
else if(j == right.length)
{
for(int v=i;v<left.length;v++)
{
k[m] = left[v];
m++;
}
}
m++;
}
}
}
CONSOLE:
=========
Enter the size
20
Enter values
2
5
4
3
1
8
7
9
34
56
71
12
28
90
76
43
31
98
67
76
The less great sort array is :
1
3
2
5
4
8
7
12
9
31
28
43
34
67
56
76
71
90
76
98
Sort the array in ascending order
Array.sort(inputArray);
Once sorted traverse the array for modifications and swap every two elements in the following logic
for(i=1; i<inputArray.length-2; i=i+2)
{
int temp = inputArray[i];
inputArray[i] = inputArray[i+1]
inputArray[i+1] = input Array[i]
}
This will result the array in required output. Please correct me if I am wrong.
Dinesh,
Your logic might simple, but the total time complexity is high.
For Sorting O(n log n) for swapping n/2 approximately.
But Jason and few others solutions is O(n)
You can solve this in O(n) time by finding the median of the array in O(n) using quickselect or the median-of-medians algorithm, and then placing numbers less than the median (in any order) in even positions (for a 0-indexed array), and numbers greater than the median (in any order) in odd positions. For elements equal to the median, distribute them between both even and odd slots that remain after placing the other elements. The correctness of this approach follows from the observations that every constraint on the final output is of the form a[some_odd_index] >= a[some_even_index], and that this construction ensures all odd indexes are >= the median and all even indexes are <= the median, therefore guaranteeing that all odd indexes are >= all even indexes.
public static void arrange(int array[]){
char int[] = Programming.mersort(array,0,array.length);
int i = 0;
int e = sorted.length -1;
boolean flag = false;
while(i<=e){
if(flag){
System.out.print( sorted[e--] + (i<=e?" >= ":"") );
}else{
System.out.print( sorted[i++] + (i<=e?" <= ":"") );
}
flag = !flag;
}
System.out.println("");
}
int []{3,4,5,7,8,9};
output
3 <= 9 >= 4 <= 8 >= 5 <= 7
Little modification to the merge sort will work for this
1) Divide the input as we do in the merge sort
2) While merging use a variable which is incremented on every merge operation
3) Use ascending order condition for merging if it is even or descending order when it is odd
package ms.cc.alternatesorting;
public class AlternateSorting {
int[] inputArray = {3,5,7,8,4,1,2,12,15};
void mergeSort(int[] array)
{
int[] helper = new int[array.length];
mergesort(array, helper, 0 , array.length-1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
private void mergesort(int[] array, int[] helper, int low, int high) {
if (low<high)
{
int middle= (low+high)/2;
mergesort(array, helper, low , middle);
mergesort(array, helper, middle+1 , high);
merge(array, helper,low, middle, high);
}
}
private void merge(int[] array, int[] helper, int low, int middle, int high) {
for (int i = low; i <= high; i++) {
helper[i]=array[i];
}
int helperLeft= low;
int counter=0;
int helperRight= middle+1;
int current=low;
while(helperLeft<=middle && helperRight<=high)
{
if(counter%2==0)
{
if(helper[helperLeft]<=helper[helperRight])
{
array[current]=helper[helperLeft];
helperLeft++;
}
else
{
array[current]=helper[helperRight];
helperRight++;
}
}
else
{
if(helper[helperLeft]>=helper[helperRight])
{
array[current]=helper[helperLeft];
helperLeft++;
}
else
{
array[current]=helper[helperRight];
helperRight++;
}
}
counter++;
current++;
}
int remaining = middle- helperLeft;
for(int i= 0; i<=remaining;i++)
{
array[current+i]= helper[helperLeft+i];
}
}
public static void main(String[] args) {
AlternateSorting i = new AlternateSorting();
i.mergeSort(i.inputArray);
}
}
Incorrectness: can be proved by unit test. The output will be 3 7 5 8 4 9. Who are these people who voted for this answer?
1.Sort the given Array to make Array A
2.Add elements in new Array(B) in this order
(a)Take two iterators which points to beginning and end of Array A
(b)Fill B with element from beginning and then element from end
(c)increment beginning and decrement end
(d)Repeat step 2(b) until beginning < end
B is our required result(Elements in Alternative Order)
Running time: O(n log n)
So if the input Array is 3 5 7 8 4 9
Then A = 3 4 5 7 8 9
B = 3 9 4 8 5 7 which is our output
#include <iostream>
#include <algorithm>
using namespace std;
void swap(int &a,int &b)
{
int temp =a;
a =b;
b= temp;
}
int main()
{
int a[] = {3,5,7,8,4,9};
int n = sizeof(a)/sizeof(a[0]);
sort(a,a+n);
for(int i=1;i<n-2;i+=2)
{
swap(a[i],a[i+1]);
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
Java Code
Complexity O(n)
public class Dummy1 {
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++;
}
}
}
//this algorithm works if numbers are not repeated a<b>c<d
public static int[] ReorderArray(int[] array)
{
array = MergeSort(array);
for (int i = 1; i < array.Length-1; i++)
{
if (array[i] < array[i - 1])
{
continue;
}
else
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
return array;
}
private static int[] MergeSort(int[] a)
{
if (a.Length == 1)
{
return a;
}
int middle = a.Length / 2;
int[] left = new int[middle];
for (int i = 0; i < middle; i++)
{
left[i] = a[i];
}
int [] right = new int[a.Length -middle];
for (int i = 0; i < a.Length -middle; i++)
{
right[i] = a[i+middle];
}
left = MergeSort(left);
right = MergeSort(right);
int l = 0, r = 0;
int[] sort = new int[a.Length];
for (int k = 0; k < a.Length; k++)
{
if (l < left.Length && r < right.Length)
{
if (left[l] < right[r])
{
sort[k] = left[l++];
}
else
{
sort[k] = right[r++];
}
}
else
{
if (l < left.Length)
{
sort[k] = left[l++];
}
else
{
sort[k] = right[r++];
}
}
}
return sort;
}
internal void AlternateSort(int[] input)
{
bool findLower = false;
var len = input.Length;
int temp = 0;
if (input[0] < input[1])
{
findLower = true;
}
else
{
findLower = false;
}
for (int i = 1; i < len -1; i++)
{
int j = i + 1;
if (input[i] < input[j] && findLower == true)
{
temp = input[i];
input[i] = input[j];
input[j] = temp;
}
else if (input[i] > input[j] && findLower == false)
{
temp = input[i];
input[i] = input[j];
input[j] = temp;
}
findLower = !(findLower);
}
foreach (int i in input)
{
Console.Write(i + " ");
}
}
The idea is that while traversing the array, you maintain a flag that indicates whether a "less than" or a "greater than" comparison should succeed. If it does not succeed you swap the previous index with the current index.
This will be easier to understand through an example. Let's say we have the above array {3, 2, 6, 4, 9, 7, 1, 10, 8, 5}. We traverse the array starting at the second element (2), since we'll be comparing the current with the previous element. We also have to maintain the above mentioned flag, say a flag named lessThan which will be defaulted to true since our format definition indicates that we have to start from a less than sign. So we have our element "2" and previous element "3". Is element "3" less than element "2" ? No, then we swap the elements which results in the array {2, 3, 6, 4, 9, 7, 1, 10, 8, 5}. We also have to switch the lessThan flag and then go to the next index. Now the flag tells us that we have to use the "greater than" sign. Is element "3" greater than element "6" ? No, then swap the numbers. But wait, what happens to the previous comparison ? The second index has to stay greater than the first one, but note that this did get verified by the condition that we just imposed by comparing "6" with "3". "6" is greater than "3", which is greater than "2" - this means "6" is greater than "2", thus it's safe swapping "6" with "3". This results in {2, 6, 3, 4, 9, 7, 1, 10, 8, 5}. This goes on until the end of the array.
Eugene posting some theoretical mumbo jumbo again without any real coding or psuedocode.
You can write the code yourself if you know the approach. Developing the approach is the more interesting and more difficult aspect. Keep in mind also that my solution was the first posted on this page to reach O(n) time -- at the time I posted, every other solution involved a sort, and I came up with my solution by thinking about how I could avoid sorting. Turns out there's an easier way to avoid sorting as seen in Jason's answer.
void arrangeList(int A[], int n) { for(int i=1; i<n; i++) { if(i%2 && A[i] < A[i-1]) swap(A[i], A[i-1]); if(i%2==0 && A[i] > A[i-1]) swap(A[i], A[i-1]); } return; }Time: O(n),
- Jason November 16, 2013Space: O(1),
Correctness: can be proved by mathematical induction.