Still working through the archives. This is another interesting problem, similar to the robots one, where it’s not strictly an algorithmic problem. The intention of this question is clearly not about implementing a sorting algorithm, but an exercise showing that you’re familiar with the idea of passing in a custom sort-predicate. As I think about this question I think it has value in a very targeted situation.

def parityKey(x):
    return x % 2
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        nums.sort(key=parityKey)
        return nums

Application to Interviewing

If I had to use this question for interviewing, I would compare a solution like the python above to the C++ solution below. This shows two (slightly) different APIs, and how to adapt them. There’s no reason why we couldn’t “just” use the same value-mapping approach the Python implementation suggests (just have int xOdd… and do the < comparator as usual), but here we get the added benefit of having each sub-sequence sorted.

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        std::sort(std::begin(nums), std::end(nums),
                 [](int x, int y) {
                     bool xOdd = x % 2;
                     bool yOdd = y % 2;
                     if (xOdd == yOdd) {
                         return x < y;
                     }
                     if (xOdd) {
                         return false;
                     }
                     return true;
                 });
        return nums;
    }
};

Application

As I think more about this, I would think this is a nice question to lecture on, or share as a bit of trivia. Maybe asking the original question as an exercise, to help introduce the idea of a sorting API and passing functors, is useful. I think this is too pointed (you either know about the API idea or not) for an interview question. I want to see if there’s something more general to help students take-away with the difference between the Python and C++ approach. With more material, maybe an idea will become clearer.

I believe this is the first question on sorting; more will be listed here.