We’ve been here before. Quite explicitly in fact, this question is obviously marked as a sequel.

This really drills into the idea of thinking about values versus indices. I think that’s something my students would get a lot out of. As mentioned in my comments, I feel like the term “sort” here is a bit deceptive. I would call this more like merging or partitioning, a helper function within a sort function. “Classify” by party? “Cubbyhole” by parity?

class Solution {
public:
    // Helpers inspired by commented out block in the main function.
    // This sort of "given the index, find the next valid index" pattern
    // is quite common. This is inclusive -- we can return start.
    // Yes I can have them share a function with lamdbads or whatever,
    // but let's not overcomplicate implementation.
    int nextEvenIndex(vector<int>& A, int start) {
        assert(start % 2 == 0);
        for (; start < A.size(); start += 2) {
            if (A[start] % 2) return start;
        }
        return -1;
    }
    int nextOddIndex(vector<int>& A, int start) {
        assert(start % 2);
        for (; start < A.size(); start += 2) {
            if (A[start] % 2 == 0) return start;
        }
        return -1;
    }
    vector<int> sortArrayByParityII(vector<int>& A) {
        // One of the quadratic sorts? This is almost more like merging or pivoting, than
        // sorting. The name feels deceptive :).
        
        // initialize i as the first even index to swap;
        int i = nextEvenIndex(A, 0);
        // j as the first odd index to swap;
        int j = nextOddIndex(A, 1);
        while (i != -1) {
            assert(j != -1);
            swap(A[i], A[j]);
            i = nextEvenIndex(A, i); // we should be able to get past i here, as it's now legal.
            j = nextOddIndex(A, j); // ditto
        }
        assert(i == -1 && j == -1); // we should both be done here.
        return A;
    }
};

Notes

• You can definitely see my merge-friendly perspective influencing my approach.
• I really like drilling into these loops where the index variables aren’t necessarily always incremented by a constant, as is here.
• I like how this has the implicit sub-arrays inside the main array.
• Avoiding a new allocation is a nice extended requirement, I think.

I think this is an obviously-contrived interview question, but it exercises nice things and the question (while a bit detailed) isn’t tricky. It’s very clear what a successful output should look like, or at least clear enough.