Menu
We are given a string of the form: RBBR, where R - red and B - blue.
We need to find the minimum number of swaps required in order to club the colors together. In the above case that answer would be 1 to get RRBB or BBRR.
I feel like an algorithm to sort a partially sorted array would be useful here since a simple sort would give us the number of swaps, but we want the minimum number of swaps.
Any ideas?
This is allegedly a Microsoft interview question according to this.
352
How many balls should you take out of a bag that has red and green balls in order to get two matching balls? Ans. Suppose that you take out a red ball and then a green ball. After two times, you will automatically get either a red or green ball which means you will own a pair of matching balls the third time.
Which sort has minimum swaps? The selection sort has minimum swaps. It searches for the nth element in the nth iteration and then places it in its correct position. In the worst case of n-1 iteration, it will have O(n) swaps.
Eg: If the bag contains 2 red, 2 green, and 2 blue and k=2 then we need to choose minimum 4 balls out of bag such that 2 balls are of same color.
Take one pass over the string and count the number of reds (#R) and the number of blues (#B). Then take a second pass counting the number of reds in the first #R balls (#r) and the number of blue balls in the first #B balls (#b). The lesser of (#R - #r) and (#B - #b) will be the minimum number of swaps needed.
151
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
