DE shaw OA | Scary question tbh
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.
Full Experience
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.
Interview Questions (2)
A complete graph is a graph where each pair of vertices is connected by an edge. Given an undirected weighted complete graph with g_nodes vertices, the weight of each edge is either 0 or 1. There are exactly g_edges edges provided in the form of two arrays, g_from and g_to, which denote an undirected edge between g_from[i] and g_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.
There are n servers in a data center. The operational status of each server is given by the binary string servers, where servers[i] = '1' if the ith server is operational, and servers[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.