Microsoft

"Process offline queries asking for the number of inversion pairs inside an arbitrary subarray [L, R] of an array of N integers": Mo’s algorithm with a standard BIT is too slow at O(N sqrt(N) log N), so I implemented Mo's Algorithm with Square-Root Decomposition on Values (secondary block array), achieving O(1) pointer shifts and O(sqrt N) query time to hit strict O(N sqrt(N)) total complexity. "Given a directed graph with non-negative edge weights and negative cycle detection requirements, support dynamic edge insertions and deletions while maintaining shortest paths": Dynamic Dijkstra fails on deletions, so I modeled this using a Dynamic Top-Tree over a decremental Shortest Path Tree, updating path aggregates via local tree-contraction operations in O(log^2 V) per topology change. "Find the k-th shortest simple path (loopless) between a source and sink in a directed weighted graph": Standard k-shortest paths algorithms allow cycles, so I implemented Yen’s Algorithm using Eppstein’s persistent heap optimization, generating candidate deviations by temporarily masking root-path vertices to compute next best candidates in O(K * V * (E + V log V)).