Flexport's 3-Part Shipping Route Coding Question

Flexport wraps a classic range-query problem in its logistics domain: shipping routes with congestion levels that get updated in ranges and queried in ranges. It builds from a difference array to a full lazy segment tree across three parts. Here is the full question, Java for each part, and the rubric.

The question

Part 1 · Range updates, full readout

If you only need the whole array after updates, a difference array applies each range update in O(1) and materializes the array in O(n). Reach for the segment tree only when range queries arrive in Part 2.

class Routes {
    private final long[] diff;     // diff[i] - diff[i-1] reconstructs route i

    Routes(int[] congestion) {
        diff = new long[congestion.length + 1];
        for (int i = 0; i < congestion.length; i++) { diff[i] += congestion[i]; diff[i + 1] -= congestion[i]; }
    }

    void update(int l, int r, int change) { diff[l] += change; diff[r + 1] -= change; }

    long[] snapshot() {
        long[] out = new long[diff.length - 1];
        long run = 0;
        for (int i = 0; i < out.length; i++) { run += diff[i]; out[i] = run; }
        return out;
    }
}

Part 2 · Range-minimum queries

Once you must answer many range-min queries between range updates, a difference array is O(n) per query. A segment tree with lazy propagation does both range add and range min in O(log n). The node stores a min; lazy holds a pending add pushed down on the way through.

class SegTree {
    final int n; final long[] min, lazy;

    SegTree(int[] a) { n = a.length; min = new long[4 * n]; lazy = new long[4 * n]; build(1, 0, n - 1, a); }

    private void build(int node, int lo, int hi, int[] a) {
        if (lo == hi) { min[node] = a[lo]; return; }
        int mid = (lo + hi) >>> 1;
        build(2 * node, lo, mid, a); build(2 * node + 1, mid + 1, hi, a);
        min[node] = Math.min(min[2 * node], min[2 * node + 1]);
    }

    private void apply(int node, long add) { min[node] += add; lazy[node] += add; }
    private void push(int node) { if (lazy[node] != 0) { apply(2*node, lazy[node]); apply(2*node+1, lazy[node]); lazy[node] = 0; } }

    void update(int l, int r, long add) { update(1, 0, n - 1, l, r, add); }
    private void update(int node, int lo, int hi, int l, int r, long add) {
        if (r < lo || hi < l) return;
        if (l <= lo && hi <= r) { apply(node, add); return; }
        push(node); int mid = (lo + hi) >>> 1;
        update(2*node, lo, mid, l, r, add); update(2*node+1, mid+1, hi, l, r, add);
        min[node] = Math.min(min[2*node], min[2*node+1]);
    }

    long queryMin(int l, int r) { return queryMin(1, 0, n - 1, l, r); }
    private long queryMin(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return Long.MAX_VALUE;
        if (l <= lo && hi <= r) return min[node];
        push(node); int mid = (lo + hi) >>> 1;
        return Math.min(queryMin(2*node, lo, mid, l, r), queryMin(2*node+1, mid+1, hi, l, r));
    }
}

Part 3 · Minimum and sum together

Adding range-sum is not a new structure, just a second aggregate on the same node. A range add of v over k elements increases the sum by v * k, so apply and pull each maintain both fields.

// Add to the node arrays: long[] sum;
// build leaf:   sum[node] = a[lo];
// pull:         sum[node] = sum[2*node] + sum[2*node+1];

private void apply(int node, int lo, int hi, long add) {
    min[node] += add;
    sum[node] += add * (hi - lo + 1);   // every element in the segment shifts by 'add'
    lazy[node] += add;
}

long querySum(int l, int r) { return querySum(1, 0, n - 1, l, r); }
private long querySum(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return sum[node];
    push(node); int mid = (lo + hi) >>> 1;
    return querySum(2*node, lo, mid, l, r) + querySum(2*node+1, mid+1, hi, l, r);
}

Because apply now takes the segment bounds, push and update must pass lo, hi and mid through. The lesson Flexport rewards: pick the lightest structure each part needs, and grow the segment tree by adding aggregates, not rewriting it.

How Flexport scores it

Flexport interview FAQ