Category Archives: Sorting

Interview Questions, Sorting

Sort Array By Parity (Leetcode 34)

1 Comment

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.

Arrays, Interview Questions, Sorting

Move Zeros (Leetcode 3)

1 Comment

This problem is a fun exercise on arrays. Given an array, move all the zeros to the end of the array. Maintain the relative order of all other elements.

I have some familiarity with the C++ standard library, which includes algorithms similar-to-this (but without the relative order). In languages with very explicit memory-management, this is removing elements from the array “in spirit”. In C++, in fact, this is the solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        auto new_end = std::remove(std::begin(nums), std::end(nums), 0);
        std::fill(new_end, std::end(nums), 0);
    }
};

Really line 4 is the answer this problem is looking for. Really what happen is that remove “slides the contents down” to fill up the zeros. The new_end variable stores the end of the newly-shrunken array. However, the length of the original nums is unchanged — it’s up to the programmer (me) to really explicitly request that memory be freed, or otherwise messed with.

This also echoes, in a way even more directly, partitioning algorithms. We want to reorder the contents of nums such that one category of elements (those not equal to 0) are on one side, and the other category is at the other side. Again, C++ has this algorithm directly:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        std::stable_partition(std::begin(nums), std::end(nums), [](int n) { return n != 0;});
    }
};

A common critique of code (which I agree with!) is “don’t get too clever with one-liners”. I’ll stress that the above solution, in my mind, is fine because it really is just using the fact that the algorithm is exactly what the problem is asking for. Akin to using the built-in sort method for a question that asks you to sort items. C++ is just a bit verbose.

Say, however, that we don’t have such a partition algorithm. Or that the problem is explicitly asking us to implement a partition algorithm. One trick we can do here is exploit that we know how to create new 0s. In contrast to when our array might container pointers or similar, we can just “remember how many zeros to add in later”. Here’s a Python version, basically of the first C++ solution:

class Solution(object):
    def moveZeroes(self, nums):
        nextWrite = 0
        for nextRead in range(len(nums)):
            x = nums[nextRead]
            if x == 0:
                continue
            nums[nextWrite] = x
            nextWrite += 1
        for zeroOut in range(nextWrite, len(nums)):
            nums[zeroOut] = 0

Basically nextWrite serves as new_end, the first for loop is remove, and the second for loop is fill.

Say, however, instead of an array of 0s, we have an array of objects, and we’ve been partitioning them based on whether their, I don’t know, books-checked-out-of-the-library-count was 0. We couldn’t really do the above approach because we couldn’t reconstruct a whole object after-the-fact. A nice sequel problem to consider, basically, how do we “really” implement partition.

PS: This problem can be found in codewars, too. I’d say related questions are collected under array questions, or sorting questions.

Tools and Takeaways

  1. Moving elements within an array is a common sort of “vocabulary” pattern. Remove, partition, etc., are often building blocks of larger algorithms.
  2. Sometimes we may break a for-loop up into multiple “ranges”. In our first approach, we go through the “tail” of the input array to zero-out those contents.
  3. Sometimes we can recreate the same values we care about, but later. We can do this when the values are integers. Sometimes we can’t get away with that, and have to do something more sophisticated.