Here is the interview question prompt, presented for reference.
This problem is named the "Dutch national flag problem" because the flag of the Netherlands is comprised of the colors red, white, and blue in separate parts. Although we won't be using colors, the premise of the challenge is to develop a sorting algorithm that performs some form of separations of three kinds of elements.
To simplify things, we'll use 0
s, 1
s, and 2
s.
Given an array consisting of only 0s, 1s, and 2s, sort the elements in linear time and constant space.
const arr = [2, 0, 1, 0, 2]
dutchNatFlag(arr)
// [0, 0, 1, 2, 2]
100000
You can see the full challenge with visuals at this link.
Challenges • Asked almost 7 years ago by Jake from AlgoDaily
This is the main discussion thread generated for Dutch National Flag Problem.
Hi, Jake!
Tests for java are broken in this tutorial. Seems like it checks link equality not content equality of arrays
╷
├─ JUnit Jupiter ✔
└─ JUnit Vintage ✔
└─ MainTest ✔
├─ thirdTest ✘ expected:<[I@769f71a9> but was:<[0, 0, 0, 1, 1, 2, 2, 2]>
├─ firstTest ✘ expected:<[I@17046283> but was:<[0, 1, 2]>
└─ secondTest ✘ expected:<[I@5bd03f44> but was:<[0, 0, 1, 2, 2]>
Also tests required second parameter in method call :)
public void firstTest() {
assertEquals(this.dutchNationalFlag(new int[] {0, 1, 2}, 2), "[0, 1, 2]");
}
I didnt understand why mid is not incremented when the current element is 2. Or rather why mid is incremented when current element is 0? please help!