DE Shaw

# Interview Experience ## Online Assessment *Format:** 3 questions. Camera and mic proctored. Questions to be attempted in the given order, no switching between them. Individual timers for each question: 25 min, 35 min, 35 min. ### Questions: **Service Utility Maximization:** Given a list of services, each having an associated cost value and a utility value, maximize the total utility if you are allowed to pick exactly two services within a budget. **Solution:** Solved using binary search on the array of services, ordered by cost values and with the prefix max being computed on the utility values. **Maximum Path Sum on a DAG:** **Solution:** Solved using topological sorting + DP. **Array Transformation:** Transform the given array into a permutation by applying operations where one can replace any element with an arbitrary value. Minimize the number of operations and report the lexicographically smallest permutation attainable. **Solution:** Solved using a greedy approach with a few checks and balances. -- ## Interview Round 1 The panel consisted of a single interviewer. He first introduced himself and then asked me to follow. **Graph Problem:** There are $n$ cities and $m$ two-way roads between them, each with an associated fuel cost. We have a vehicle with a tank capacity $c$ and we need to get from city A to city B. We can fill our tank to its full capacity in every city. Can we reach our destination given the capacity $c$? **Solution:** DFS from A to B after removing/while not considering edges exceeding capacity $c$. To be coded out on paper. **Minimum Tank Capacity:** I was then asked how to compute the minimum required tank capacity to get from A to B. **Solution:** Binary search using the DFS approach from (1) as the check function. **Alternative Approach:** Could I come up with another approach? **Solution:** Dijkstra's algorithm, to be coded out on paper. I was also asked for a rough sketch of the proof for the correctness of the algorithm. **Optimization:** Can I narrow down the search space in the binary search approach? **Solution:** I initially mentioned that my search space would be integers between the min and the max weighted edges. He wanted binary search over the indices of the sorted edge weight array. **Operating Systems:** I was asked what I knew about virtual memory. **Details:** Info dump on the role of the OS as an illusionist, MMU, Page Table, and TLB. **Language Differences:** Differences between Python and Java. **Details:** Gave 2 or 3 differences like dynamic typing, interpreted, functional vs object-oriented, etc., but I could sense that it was not what he was looking for. **C++ Concepts:** Polymorphism, what it means to mark a method virtual, and references in C++. **Details:** Explained compile-time and runtime polymorphism in C++. -- ## Interview Round 2 I was called into this interview shortly after the previous one. This panel had two interviewers. I was asked to introduce myself and then talk about a project/situation from my resume and how I overcame the associated challenges. I spoke about my work in the CTRI-DG lab and about code generation. I also told them about competitive programming and my journey to Candidate Master (CM) on Codeforces. The interviewer asked if I thought there was something other than grinding problems that could be done to get a rating boost. I explained that my bottleneck was observation skills rather than ignorance of algorithms. **Array Problem:** Find the rightmost larger element to the left of every element in an array. **Solution:** Standard stack-based approach. I was asked to code it out on paper. **String Problem:** Find the lexicographically smallest subsequence of a string containing each character exactly once. **Approach:** I asked for constraints. I started by thinking out loud about a greedy strategy but got nowhere. I pivoted to DP and came up with a bitmask approach. They didn't ask for an in-depth explanation and moved on. **System Design:** I was asked to design a library. **Details:** I wrote a rough draft of the requirements specification document while asking questions, then did requirement parsing to arrive at the UML diagram. I described how to implement it using Spring Boot rather than providing a low-level implementation. **C++ Virtual Methods:** Once again, I was asked to explain what it means to mark a method virtual. **Details:** They showed me a piece of C++ code using two classes and virtual methods and asked me to predict the output.