D.E. Shaw

## Round 0: Online Assessment *Type:** Online Round This was the online assessment in which three DSA problems were asked. They were timed as 25 minutes, 35 minutes, and 35 minutes for individual questions, and the time remaining from one problem didn’t get transferred over to the next. **Problem 1:** A knapsack variation with cost and value associated with each element, but it didn’t require DP. There were various methods to solve it: `priority_queue` with a semi-sliding window approach, binary search, or a segment tree overkill. **Problem 2:** A very standard topological sort DP. It was something like finding the max sum path in a DAG, which was directly given in the problem statement. **Problem 3:** A greedy problem. Given an array, convert it to a permutation by changing any element to any other value, but with a minimum number of changes. If there are multiple permutations corresponding to the minimum changes, return the lexicographically smallest one. I got all three problems in around 50 minutes. ## Round 1: Technical *Type:** Technical There was a panel of two interviewers. They were asking questions one by one. After introductions, they noted the achievement sections in my resume. **Icebreaker:** I was asked to calculate the number of Indian accounts on CodeChef based on my rank and percentile. **Project Discussion:** I was asked to explain the top project in my resume, which used PostgreSQL, MongoDB, and Neo4j. They asked me to explain the differences between them and in what cases they are used. **System Design/Data Structures:** One of the interviewers asked: Suppose we have users on a coding platform where each user has an ID and a score. We want to get the top 100 users based on their scores. I gave two approaches: sorting the list and maintaining a priority queue. **Follow-up:** Imagine we have to maintain a dashboard of the top 100 users. New users can join and the scores of existing users can change. I was supposed to design a class for this. I suggested an approach similar to an LRU cache using a doubly linked list and hashmaps. I explained the $O(100)$ and $O(\log(100))$ solutions. **DSA Problem:** [Ways to Split Array Into Three Subarrays](https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/description/). I started with brute force, then made constant time optimizations, and finally reached the optimal approach. This took about 15 minutes. **OOP Concepts:** Since I had OOP experience on my resume, I was asked to "teach" the interviewer OOP. I covered objects, classes, and the four pillars. What is the point of encapsulation and abstraction? Difference between compile-time and runtime polymorphism, with examples. When should we not use inheritance? (Discussed multiple inheritance and the diamond problem in C++). **C++ Code Snippet:** I was given a piece of C++ code involving pointers and asked to identify potential issues and fixes. This round lasted about an hour; I was not asked to code on a compiler. ## Round 2: Technical + Managerial *Type:** Technical + Managerial This was also a panel of two interviewers, with one primary interviewer and one observer. I mentioned I preferred high-level real-world problems, so I was asked DSA problems in that context. **Problem 1:** Schedule a meeting with $n$ people who have $m$ free time slots. Find the maximum meeting duration such that all of them can attend. I suggested coordinate compression for floating-point values and optimized it with a sweep-line logic. **Follow-up:** What if intervals were given in increasing order for each person? I compared this to the merge function of merge sort with $n$ arrays and suggested a `priority_queue` optimization. **Problem 2:** A variation of [Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/description/). Instead of lexicographical order, I was given a cost function $c(s) = \sum (ASCII(s_i) * i)$ and asked to maximize this. I provided a brute-force solution. I attempted to optimize it using DP for 20-25 minutes. Although I didn't reach the final optimal solution, the interviewer liked my approach and how I identified flaws in my logic. **Behavioral Questions:** Tell me about a challenge you faced in a project. How would you prioritize projects if you’re given 4-5 of them simultaneously? What would you do if you didn’t like the projects you’re given? **Coding:** I was asked to write the functioning brute-force code for the second problem on paper. This round lasted about an hour. ## Overall Experience The interview was relatively rigorous. It was primarily focused on DSA, with some OOP and resume-related questions. All candidates seemed to have different experiences.