Question

Microsoft | OA Coding Questions and Solutions | Set - 34 | 2022

Answer 1

Sort the list of Integers with minimum number of swaps

 

Constraints:
 sort it in a way that even numbers are at the start of list in ascending order and the odd numbers are at the end of list in descending order.

Answer 2

//to ensure minimum number of swaps we have to use selection sort  
  public void sortListWithMinimumSwaps(int[] arr) {   
    int evenCount = 0;
    for(int el:arr) if(el%2==0) evenCount++;
    int oddCount = arr.length-evenCount;

    int i = 0;
    for(;i<evenCount;i++) {
        int smallestEvenValue = arr[i] % 2 == 0 ? arr[i] : Integer.MAX_VALUE;
        int indexOfSmallestEvenValue = i;
        for(int j = i+1;j<arr.length;j++) {
            if(arr[j]%2==0 && arr[j] < smallestEvenValue ) {smallestEvenValue  = arr[j]; indexOfSmallestEvenValue = j;}
        }
        int temp = arr[indexOfSmallestEvenValue];
        arr[indexOfSmallestEvenValue] = arr[i];
        arr[i] = temp;
    }
    for(;i<arr.length;i++) {
        int biggestOddValue = arr[i] % 2 == 1 ? arr[i] : Integer.MIN_VALUE;
        int indexOfBiggestOddValue= i;
        for(int j = i+1;j<arr.length;j++) {
            if(arr[j]%2==1 && arr[j] > biggestOddValue ) {biggestOddValue = arr[j]; indexOfBiggestOddValue= j;}
        }
        int temp = arr[indexOfBiggestOddValue];
        arr[indexOfBiggestOddValue] = arr[i];
        arr[i] = temp;
    }

 

}

Answer 3

Java solution : O(nlogn)
Space complexity: O(n)

 

   public static int sort(int[] arr) {
     //build the desired array
     int odd = 0, even = 0;

     for (int i : arr) {
       if (i % 2 == 0) even++; else odd++;
     }

     Integer oddArr[] = new Integer[odd];
     Integer evenArr[] = new Integer[even];
     even = 0;
     odd = 0;

     for (int i = 0; i < arr.length; i++) {
       if (arr[i] % 2 == 0) evenArr[even++] = arr[i]; else oddArr[odd++] =
         arr[i];
     }
     Arrays.sort(evenArr);
     Arrays.sort(oddArr);

     Collections.reverse(Arrays.asList(oddArr));

     int sortedArr[] = new int[arr.length];
     int j = 0;
     while (j < evenArr.length) {
       sortedArr[j] = evenArr[j];
       j++;
     }
     while (j < oddArr.length + evenArr.length) {
       sortedArr[j] = oddArr[j - evenArr.length];
       j++;
     }

     System.out.println(Arrays.toString(arr));
     System.out.println(Arrays.toString(sortedArr));
 
     //how many swaps to get from current arr to desired arr
     int swaps = minSwapsSort(sortedArr, arr);
 
     return swaps;
   }

   public static int minSwapsSort(int[] nums, int[] arr) {
     HashMap<Integer, Integer> hm = new HashMap<>();
     boolean[] visited = new boolean[nums.length];
     int j = 0, swaps = 0;

     for (int i : nums) {
       hm.put(i, j++);
     }

     for (int i = 0; i < nums.length; i++) {
       if (hm.get(arr[i]) == i && visited[i] != true) {
         visited[i] = true;
       } else {
         j = hm.get(arr[i]);
         while (visited[j] == false) {
           visited[j] = true;
           j = hm.get(arr[j]);
           if (visited[j] == false) swaps++;
         }
       }
     }
 
return swaps;
   }

Answer 4

Here is my code for this question:

 

#  Python code block
import heapq
def sortArrayByParity(nums):
        left=0
        right=len(nums)-1
        swap=0
        
        while left<right:
            if (nums[left]%2)!=0 and (nums[right]%2)==0:
                nums[left],nums[right]=nums[right],nums[left]
                left+=1
                right-=1
                swap+=1
                
            elif (nums[left]%2)!=0 and (nums[right]%2)!=0:   
                 right-=1
                    
            elif (nums[left]%2)==0:           
                 left+=1
        return nums,left,swap  

         
def min_swap_sort(num):
    key_dict=dict([(num[i],i) for i in range(len(num))])
    heap=num[::]
    heapq.heapify(heap)
    swap=0
    for i in range(len(num)):
        smallest=heapq.heappop(heap)
        if num[i]!=smallest:
            tmp=num[i]
            num[i], num[key_dict[smallest]]=smallest, num[i]
            key_dict[smallest],key_dict[tmp]=key_dict[tmp],key_dict[smallest]
            swap+=1
    return swap,num


def even_odd_sort(num):
    nums,left,swapb=sortArrayByParity(num) 
    swapo,numo=min_swap_sort(nums[:left])
    nume = [ -x for x in nums[left:]]
    swape,nume=min_swap_sort(nume)
    nume = [ -x for x in nume]
    print(numo+nume)
    return swapo+swapb+swape


print(even_odd_sort([7,3,8,1,5,6,2,4]))

 

Run-time: O(nlogn)
Space Complexity: O(n)