DE SHAW

# Interview Experience - D.E. Shaw ## Round 0: Online Assessment 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 timer remaining from one problem didn’t get transferred over to the next. **Question 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. **Question 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. **Question 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. ## Interview Round 1: Technical I had applied through campus placement, cleared the OA, and now I was about to face the final boss level of interviews. I'd heard stories about their tough questions and intense scrutiny, but I was ready. Or so I thought. I entered the interview room, and there they were: my interviewers, playing out the classic "good cop, bad cop" routine. On the left was Mr. Good Cop, who greeted me like we were old friends. On the right was Mr. Bad Cop, looking like he’d just lost a bet. And thus began my rollercoaster ride. ### Part 1: Mr. Good Cop (DSA & Logic) Mr. Good Cop kicked things off with a question that sounded deceptively simple: *"How many odd-length paths are there in this binary tree?"** He handed me a root node pointer and said, "We don’t care much about the code, just your thought process." I quickly proposed using BFS traversal to make the tree bipartite. My logic: even * odd distances equals the answer. Five minutes in, Mr. Good Cop, still smiling, said, “Hmm, your approach might fail in some cases.” I spent another five minutes debugging before I confidently proved it would work for all cases. He smiled even wider and said, "Actually, we just wanted you to mathematically prove it." After some back-and-forth, I nailed it and scribbled some pseudocode on paper. Next, he tossed me a curveball about **chocolate weights**. I had an array of them, and each day I could eat half of a chocolate’s weight. *Question:** What's the maximum chocolate I can eat in D days? Ready for a classic dynamic programming challenge, I started with a recursive approach. Mr. Good Cop interrupted, “Think simple.” I pivoted to an intuitive greedy approach, which made him nod approvingly. I coded it up on paper using a `multiset` and explained the STL implementation. ### Part 2: Resume & Mr. Bad Cop (CS Fundamentals) Before Mr. Bad Cop took over, he started reading my resume from the end, focusing on two projects I wasn't super confident about. I managed to answer all his questions related to those projects. Now it was Mr. Bad Cop's turn. He asked about the **implementation of an ordered map in C++**. I answered: “Well, it uses a hash function and stores keys in red-black trees.” He leaned in, eyes narrowing. “Explain red-black trees in detail.” My brain blanked on the nitty-gritty details, and he was not pleased. Next, he handed me a **hash function** and demanded I explain how to handle collisions. I suggested improving the hash function, but he wanted a deep dive into the mechanics which I struggled with. Shifting gears, he quizzed me on **Object-Oriented Programming (OOP)**: What’s up with virtual functions, pointers, and vtables? What if a constructor is private? I explained that only friend classes can invoke objects, using a banking system example. This seemed to appease him. Next, he asked if it’s possible to **run a process larger than the RAM**. I explained paging and virtual memory, discussed page replacement algorithms, and even mentioned Belady's anomaly. He nodded, somewhat satisfied. Finally, he asked **how to store heterogeneous elements in a vector**. The answer was generic templates, but I rambled about other methods. He was moderately satisfied. ## Conclusion With that, the interview concluded. Despite the smiles, I wasn’t called for further rounds. It was an adventure where I learned a lot about data structures, algorithms, and how to handle high-pressure situations. If you're gearing up for a D.E. Shaw interview, remember to prepare thoroughly. Know your data structures, brush up on your algorithms, and be ready to explain things at a low level.