DE shaw OA | Scary question tbh
- Posted
- 7 Nov 2025
Summary
I encountered two challenging algorithmic problems during my DE Shaw Online Assessment. The first involved finding the minimum spanning tree weight in a complete graph with 0/1 edge weights, and the second was about maximizing system redundancy by flipping a consecutive sequence of server statuses.
How it went
I recently took the Online Assessment for DE Shaw, and honestly, the questions were quite intimidating. I was presented with two distinct problems that required a strong grasp of algorithms and data structures. It was a tough experience overall.
Questions asked (2)
- 01
MST on Complete Graph with 0/1 Edges
Data Structures & Algorithms
A complete graph is a graph where each pair of vertices is connected by an edge. Given an undirected weighted complete graph with
g_nodesvertices, the weight of each edge is either 0 or 1. There are exactlyg_edgesedges provided in the form of two arrays,g_fromandg_to, which denote an undirected edge betweeng_from[i]andg_to[i]with a weight of 1, while all other edges have a weight of 0.
A spanning tree is a sub-graph of an undirected connected graph that includes all the vertices of the graph and has the minimum possible number of edges to ensure all vertices are connected in the sub-graph. For a connected graph with x nodes, its spanning tree contains (x - 1) edges. Among all possible spanning trees, a minimum spanning tree is one where the sum of the weights of the edges is the least possible.
Given the 1-weighted edges of the complete graph, determine the weight of the minimum spanning tree of the graph.
Needed the most optimised code. - 02
Maximize System Redundancy with One Server Flip Operation
Data Structures & Algorithms
There are
nservers in a data center. The operational status of each server is given by the binary stringservers, whereservers[i] = '1'if theith server is operational, andservers[i] = '0'if it is not.
The data center can perform at most one operation: select a consecutive sequence of servers and switch their operational status. This means that operational servers in the selected sequence become non-operational, and non-operational servers become operational.
The redundancy of the system refers to the number of unique values representing the number of operational servers across all possible configurations after the operation. Each distinct count of operational servers contributes to this redundancy. Determine the maximum redundancy of this system.