Microsoft OA Min Adj Swaps to Group Red Balls

Microsoft OA Min Adj Swaps to Group Red Balls | Minimum number of swaps in constant time

Min Adj Swaps to Group Red Balls Solution

There are N balls positioned in a row. Each of them is either red or white . In one move we can swap two adjacent balls. We want to arrange all the red balls into a consistent segment. What is the minimum number of swaps needed?

Given string S of length N built from characters “R” and “W”, representing red and white balls respectively, returns the minimum number of swaps needed to arrange all the red balls into a consistent segment. If the result exceeds 10^9, return -1.

Also See: Amazon OA Online Assessment 2023 Questions and Answers

Example 1:

Input:WRRWWR

Output: 2

Explanation:

We can move the last ball two positions to the left:

• swap R and W -> WRRWRW
• swap R and W -> WRRRWW

Example 2:

Input:WWRWWWRWR

Output: 4

Explanation:

We can move the last ball two positions to the left:

• swap R and W -> WWRWWWRRW
• swap R and W -> WWWRWWRRW
• swap R and W -> WWWWRWRRW
• swap R and W -> WWWWWRRRW

Example 3:

Input:WR repeated 100000 times.

Output: -1

Explanation:

The minimum needed number of swaps is greater than 10^9. So return -1.

Example 4:

Input:WWW

Output: 0

Explanation:

There are no red balls to arrange into a segment.

Also See: AMCAT Study Materials, Preparation Guide

SOLUTION

Probably the first idea you get after reading this task is to count all Ws surrounded by Rs and multiply them to number of Rs divided by Ws which we need to move. But if we will move Rs to left or to right side it may happens that the number of swaps will be not minimum. For example if we move RWRWWRRR from right to left we spend 10 swaps but if we will move from left to right we spend only 5 swaps.

The optimum way is moving Rs to the middle of the row.

So let’s process the row from the left and the right side simultaneously. We will move from the ends to the middle, find all pairs of Rs of the ends, count Ws between of them and add these counts to the result.

For example lets process the row: RWWWRWRWWR

We start from the sides and see that left and right sides are ending by Rs

R W W W R W R W W R
|                                    |
left		                 right

Number of Ws in between = 6, so in order to move two Rs from the ends to the middle we need to do 6 swaps. We add 6 to the result variable and continue.

Now we passing all Ws until we meet next pair of Rs

R W W W R W R W W R
                 |       |
              left    right

Number of Ws in between = 1, in order to move two Rs from the ends to the middle we need to do 1 swap. We add 1 to the result variable and finish with the result = 7.

In order to calculate how many Ws we have between Rs we should count number of all Rs in the row before start of the main algorithm.

Program C++: Min Adj Swaps to Group Red Balls Solution in C++

Description of the algorithm for similar task from Google
So we can solve this question by sliding window method. We always keep a window that contains k girls’ position and process the string char by char. If we encounter a boy, we do nothing; otherwise we move the window to contain the current girl and pop out the left most girl.

To solve the minimum swaps needed in the current window, one can find the median position of k girls in the window and calculate the distances from the other girls to the girl in the median position. For example, consider string = “B[GGGBBBBG]BBGGBGG”, the median position in the current window is 2 or 3 (indexed from 0). Let the median position be 2, the total distances from all the other girls is 1 + 1 + 6 = 8.

Then you minus the fixed adjust distance (1 + 1 + 2) = 4 and get the minimum number of swaps = 4. The fixed adjust distance here is because you move all girls into the median position, but the girls are sitting in a consecutive row instead of the same position.

Therefore we already have a O(kn)-time O(k)-space algorithm, k is for the time to solve the minimum number of swaps in the current window and n is for the time to scan the whole string. Of course you can improve the algorithm to be O(n) time. This is because when the window is sliding to the next one, the median position can be tracked easily if the window is implemented by a linked list. Regarding updating the distances to the median position, let the left_distance be the total distances from the girls to the left of the median girl and similarly for the right_distance.

Let m be the median position and m’ be the new median position. Consider the window slides to the next girl at position j and pops the most left girl at position i.
The the new left_distance = left_distance – (m – i) + (m’ – m) * ((k – 1) / 2)
and the new right_distance = right_distance + (j – m’) – (m’ – m) * (k / 2).

Therefore we can calculate the minimum number of swaps in constant time.
Here is the code:

int minSwapNum(string& s, int k) {
    list<int> window;
    int i = 0;
    while ((i < s.size()) && (window.size() < k)) {
        if (s[i] == 'G') {
            window.push_back(i);
        }
        i++;
    }
    //No enough girls
    if (window.size() < k) {
        return -1;
    }
    auto med_it = window.begin();
    advance(med_it, (k - 1) / 2);
    int left_dist = 0;
    int right_dist = 0;
    for (auto idx : window) {
        if (idx < *med_it) {
            left_dist += (*med_it - idx);
        } else {
            right_dist += (idx - *med_it);
        }
    }
    int adjust_dist = (k % 2 == 0) ? k * k / 4 : (k * k - 1) / 4;
    int min = left_dist + right_dist - adjust_dist;
    for (; i<s.size(); i++) {
        if (s[i] == 'G') {
            int head = window.front();
            int tail = i;
            int old_med = *med_it;
            window.pop_front();
            window.push_back(tail);
            med_it++;
            left_dist = left_dist - (old_med - head) + (*med_it - old_med) * ((k - 1) / 2);
            right_dist = right_dist + (tail - *med_it) - (*med_it - old_med) * (k / 2);
            if (left_dist + right_dist - adjust_dist < min) {
                min = left_dist + right_dist - adjust_dist;
            }
        }
    }
    return min;
}

Program: Min Adj Swaps to Group Red Balls Solution in C++

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> get_char_indices(const string & s, char c) {
    int s_len = s.length();
    vector<int> indices;
    indices.reserve(s_len);
    for (int i = 0; i < s_len; ++i) {
        if (s[i] == c) {
            indices.push_back(i);
        }
    }
    indices.shrink_to_fit();
    return indices;
}
int solution2(const string & s) {
    auto reds = get_char_indices(s, 'R');
    int mid = reds.size() / 2;
    int min_swaps = 0, reds_num = reds.size();
    for (int i = 0; i < reds_num; i++) {
        // number of swaps for each R is the distance to mid, minus the number of R's between them
        min_swaps += abs(reds[mid] - reds[i]) - abs(mid - i);
    }
    return (min_swaps > pow(10, 9)) ? -1 : min_swaps;
}
int solution(const string & s) {
    int red_count = 0;
    // count number of Rs in the string
    for (char c : s) {
        if (c == 'R') ++red_count;
    }
    // Init indexes to the ends of the string and the result
    int left = 0, right = s.size() - 1, result = 0;
    // moving from the ends to the middle
    while (left < right) {
        // if we meet pair of Rs on the ends
        if (s[left] == 'R' && s[right] == 'R') {
            // add the the result number of Ws between of these Rs
            red_count -= 2;
            result += right - left - 1 - red_count;
            // and shrink the processing window
            ++left;
            --right;
        }
        // pass all Ws we meet
        else if (s[left] != 'R') {
            ++left;
        }
        else {
            --right;
        }
    }
    return result;
}
int main() {
    cout << solution("RRRWRR") << " Expected: 2" << endl;
    cout << solution("WRRWWR") << " Expected: 2" << endl;
    cout << solution("WWRWWWRWR") << " Expected: 4" << endl;
    cout << solution("RWRWWRRR") << " Expected: 5" << endl;
    return 0;
}

Program Java: Min Adj Swaps to Group Red Balls Solution in Java

public static int minAdjSwapRedBalls(String s) {
        List<Integer> redIndex = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'R') redIndex.add(i);
        }
        int res = 0, mid = redIndex.size() / 2;  // mid is the point to get minimum swaps; greedy.
        for (int i = 0; i < redIndex.size(); i++) {
            res += Math.abs(redIndex.get(mid) - redIndex.get(i)) - Math.abs(mid - i);
        }
        return res;
    }

Microsoft Online Assessment 2023 Questions List

• Maximal Network Rank Solution
• Min Deletions To Obtain String in Right Format
• Day of week that is K days later Solution
• Minimum Adjacent Swaps to Make Palindrome Solution
• Lexicographically Smallest String
• Longest Substring Without Two Contiguous Occurrences of Letter
• String Without 3 Identical Consecutive Letters
• Microsoft OA Longest Semi-Alternating Substring
• Microsoft OA Min Steps to Make Piles Equal Height
• Max Inserts to Obtain String Without 3 Consecutive ‘a’
• Concatenated String Length with unique Characters
• Largest K such that both K and -K exist in array
• Microsoft OA Min Adj Swaps to Group Red Balls
• Maximum Length of a Concatenated String with Unique Characters
• Microsoft OA Unique Integers That Sum Up To 0
• Find N Unique Integers Sum up to Zero
• Microsoft OA Particle Velocity Solution
• Microsoft OA Arithmetic Slices Solution
• Microsoft OA Widest Path Without Trees Solution
• Microsoft OA Jump Game Solution
• Microsoft OA Fair Indexes Solution