Sort a book of short, flat, and long positions
Asked at Akuna Capital
Each account holds a position marker: -1 for short, 0 for flat, +1 for long. Rearrange the array in place so all shorts come first, then all flats, then all longs. Do it in one pass with constant extra space.
positions = [1, -1, 0, 1, -1]
-> [-1, -1, 0, 1, 1]
Sort the three-valued array in place in time and space.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.