D.E. Shaw

## Round 0: Online Assessment The online round consisted of three problems. While the problems were not difficult, the fact that each question had an individual time limit (and we could not switch between problems) increased the pressure. **Problem 1:** A binary search / two pointer problem. **Problem 2:** A very standard problem of DP on directed graphs. **Problem 3:** A greedy problem involving finding a lexicographically minimum permutation. ## Round 1: Technical Interview Each interview consisted of two interviewers. In the first interview, they started with a coding problem where I had to explain the logic (no code required). **Coding Problem:** Given an array $A$ of length $n$, and a fuel capacity of $k$. Each day $i$ ($1 \le i \le n$) you can choose to either travel a distance of $A_i$ and reduce the fuel by 1, or do nothing and increase the fuel by 1. Fuel cannot be negative or above $k$ at any point. What is the maximum total distance you can travel? **Solution:** I offered a straightforward DP solution with time complexity $O(n \times k)$. **Follow-up:** Improve the memory complexity to $O(k)$. **Project Discussion:** They reviewed my projects and asked me to explain them. They were particularly interested in the OOP concepts used in my game projects. **Theory Questions:** Stack vs Heap memory. Abstract classes vs Interfaces in Java. ## Round 2: Technical Interview **Coding Problem:** Given a Fibonacci tree of order $n$ (definition provided), return the nodes on the path from index $u$ to $v$. Assume the tree is indexed according to preorder traversal. **Solution:** I came up with an $O(n)$ solution and wrote the pseudocode. **Core Theory (OOP, OS, CN, DBMS):** The interviewer went in-depth, and I struggled with several questions. **Example Question:** "Which scheduling algorithm is implemented in modern operating systems?" I was especially not well-versed with DBMS topics. The theory part was very difficult compared to the DSA part. ## Round 3: Final Technical / Behavioral Round **Behavioral Questions:** "How would I choose which project to focus on if there are many pending projects and an approaching deadline?" **OS Theory:** These were simpler than the previous round. Difference between process and thread. How to prevent race conditions. **Coding Problem:** Find the lexicographically smallest subsequence of a string containing all the characters of the original string exactly once. **Solution:** I provided an $O(n)$ solution using a stack. ## Overall Experience The primary focus of the interviews seemed to be on problem-solving, resume-based questions, DSA, and OOP. It helps to also know basic theory of OS, DBMS, and CN.