Microsoft

"Given a set of N points on a 2D plane, dynamically insert points and query for the point that maximizes the dot product with an arbitrary 2D vector (P . V) in sub-linear time": The interviewer barred rebuilding a static convex hull ($O(N \log N)$) upon every point insertion; I solved it by implementing a Dynamic Convex Hull Trick using a self-balancing binary search tree (Chtholly / Li Chao Tree or std::set with line slopes), where lines are inserted online and intersecting ranges are dynamically pruned via adjacent slope and cross-product orientation tests to answer maximum linear evaluation queries in strict $O(\log N)$ time. "Given an unweighted directed graph, dynamically determine whether adding a directed edge (u, v) introduces a directed cycle, processing an arbitrary online stream of edge additions": The interviewer pointed out that running a full DFS/Tarjan cycle check ($O(V + E)$) per edge addition causes $O(E^2)$ blowup; I resolved it by implementing the Bender-Fineman-Gilbert-Tarjan (BFGT) online topological ordering algorithm, which maintains an explicit vertex topological ordering and only performs localized bi-directional searches within the affected topological rank window $[topo(v), topo(u)]$ to update ranks and detect cycles in amortized $O(\min(m^{1/2}, n^{2/3}))$ per edge insertion. "Given a tree of N nodes where each node has a weight, answer online queries asking for the median node weight along the unique simple path between any two nodes u and v": The interviewer rejected linear tree traversals and heavy decomposition flattenings that require $O(N)$ auxiliary storage per query; I designed a Persistent Segment Tree over Tree Structure architecture, where each tree node inherits the persistent frequency segment tree of its parent during a pre-order Euler tour DFS; I then evaluated the path aggregate via segment tree subtraction using the four roots: $Root[u] + Root[v] - Root[LCA(u, v)] - Root[parent(LCA(u, v))]$, walking down the binary range tree in $O(\log(\max W))$ time to isolate the $k$-th order statistic.