DE Shaw

## Online Assessment (Virtual) 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. *Question 1:** We were given an array of services for a company with “costs” and “uses” associated with each service along with an overall “budget” and we can buy exactly 2 services out of these such that the number of “uses” is maximized and is within the budget. **My approach:** I solved it using binary search by fixing one service and finding the one which lies within maximum budget with maximum uses. *Question 2:** We are given a directed graph with n nodes where each node has a value associated with it. We want to maximize the total value by choosing a start city and end city and walking along the path between them. We can visit each city at most once and the graph does not have cycles. **My approach:** Topological Sort + DP *Question 3:** Don’t remember the exact problem but it had a greedy solution. We were given an array and we had to convert it to a permutation in minimum number of steps and if multiple were possible, we had to make the lexicographically smallest one. In one step we could choose any element and change it to any value. **My approach:** Find all missing numbers in permutation and place them greedily. ## Interview Round 1 (On-campus) It was supposed to be a panel of 2 interviewers but one of them was running late (he didn’t arrive till the end of the interview). We started with a brief introduction and he asked me about the language for which I foolishly answered English first (yeah I was nervous) before changing it to C++. I had kept my resume on the desk and did not hand it over to him. Others who handed over the resume to the interviewers were asked questions regarding it. He first asked me a standard question: [Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/description). I gave a recursive solution which would have a time complexity of O(N^2) after memoizing and he was satisfied with it. There is an O(N) solution also using Catalan numbers but we did not discuss it. After this, we discussed the construction of the trees themselves and not just the count of the trees where I told him about returning a vector of TreeNodes and he was satisfied. All this was done on a sheet of paper where I was explaining as I wrote the code for the problem. Then he moved to core questions and asked me if I was comfortable with SQL queries and asked me to write the query for the following problem: Given a table of employees that has: EmployeeID, EmployeeName and ManagerID, find all the managers who have more than 5 employees under them. I gave him a solution based on using `GROUP BY` clause in SQL but since I had mentioned using `JOIN` when I first heard the question, he asked me to come up with a solution using that also. After this, there were few questions regarding OOPS: What are friend functions/classes and what all can they access: private/public/protected. What’s the difference between friend class and child class? What are abstract classes, how are they different from interfaces? Virtual functions in C++ and their working. Now there was still time and he asked me one more problem - a 2D DP problem which had a standard solution and then we discussed the time and space complexity for it for which he asked me to optimize the space complexity. ## Interview Round 2 (On-campus) The second round took place around an hour after the first round. This was also a panel of two interviewers, but in this case, only one person was asking questions while the other was observing. After introductions, I was asked about my recent project and what challenges I faced during it and how I tackled the same. Then he started with a basic question of difference between threads and processes and how they work internally and went into depth asking follow-up questions: Where are threads used? Have you written programs that use threads? Why use threads if we have classes? What issues can arise because of using threads? Then the discussion moved to concurrency where we talked about semaphores, locking and how we can avoid race conditions. He also asked how we can allow threads to work concurrently without using locking mechanisms and ensuring safety. I answered that if we can schedule them in such a way that there’s no conflict then we can achieve it without locks but then this is not practical. Then we moved to the DSA problems: *Problem 1:** A variation of [Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/description/). A lot of candidates were asked this exact problem, but I was asked a different (harder) variation of it: instead of lexicographically smallest/largest, I was given a cost function `(c(s) = sum over all indices (ASCII(si) * i))` and was asked to minimize this. After we discussed the brute force approach, I came up with a greedy solution for this problem similar to one discussed here: [Lexicographically largest subsequence containing all distinct characters only once](https://www.geeksforgeeks.org/lexicographically-largest-subsequence-containing-all-distinct-characters-only-once/). The interviewer was not that satisfied with it and we discussed a few examples of the same before moving to the next question. *Problem 2:** We have to schedule a meeting with n people, who have m free time slots each. Find the maximum meeting duration such that all of them can attend it. I started with a binary search based solution but that was too complex. By the time I realized a better solution of marking the left as +1 and right+1 index as -1 and using prefix sums, it was already late and we moved ahead in interest of time. At the end, the second interviewer asked me a question to explain what all classes will I use if I have to design the same for a library and we discussed it for some time regarding what all methods will be present and how it will work.