Current Education : Final Year , B.E. Computer Engineering , Tier II
Current Experience : Interned at a Big Fintech Startup
Applied For : Member of Technical Staff
Company : D.E. Shaw
Location: Hyderabad , Telangana
Date: April 22 , 2022

Round 1 : OA

• This was an offcampus opportunity. I received a link for Online Assesment . It was a 2 hours coding round. It consisted of 3 questions purely based on Data Structures and Algorithms. The first question was related to binary search and was a medium problem. The second and third question involved dynamic programming and can be categorised as hard. I managed to solve the first question completely and the 2nd and 3rd question partially. I managed to get this round cleared and received an email regarding the further interview rounds.

Round 2 : Phone Screening | CodePair

• This round was scheduled one week after I received the email and had to be organised on codepair.

• The interview started with a linkedlist question .

  • https://leetcode.com/problems/copy-list-with-random-pointer/

  It was a leetcode medium and a pretty standard question , so I was able to dicuss the approach fluently with the interviewer and code it as well.

• The next question was based on stack and it was also a standard yet tricky problem.

  • Design a stack that supports getMin() in O(1) time and O(1) extra space.

  I had done this problem before , so , I tried explaining the solution. I knew about the “2x – minElement” thing , but , couldn't explain it well. The interviewer asked to me to agree that I had solved this problem before and he was cool with it. XD

• The interview proceeded with some rapid fire OOPS , DBMS and OS basic questions. The interviewer was pretty impressed. I cleared this round and received a mail of the next In-House Interview Rounds.

Now , the company had ghosted all the eligible interviewees and no one heard about the dates of interviews for the next round for nearly 2 months.

Round 3 : In-House Interview | CodePair

• This round was scheduled on codepair. There were 2 interviewers.

• The interview started with a data structure design question.

  • Design a waiting list queue system for a restaurant. The waiting queue should be able to pick only those groups of people for which vacancy is available.

  I started the dicussion with a implementation of using a queue and a map. The interviewer was convinced about the approach and added a follow up question to implement a assignTable and emptyTable functions for the restaurant. We discussed the time complexities for the same and I managed to answer the question.

• The next question was based on buy and sell stock problem.

  • https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
  • A follow up question to this was when only 2 transactions are allowed.
  • https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
    Now , the interviewer wanted to generalise the solution for K - transactions.
  • https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

  For the first 2 problems , I discussed a O(N) time complexity and O(1) space approach. But , when discussed about the third problem , I came up with a O(N^2K) dynamic programming solution and couldn't optimise it further. This is where I messed up the things in case of discussing complexities.

• The next question was based on recursion + dynamic programming algorithm.

  • Given an array of binary numbers ( 0 , 1 ) where 0 represents safe spot and 1 represents a spike. The ball initially started with a speed 's' and is placed on the first index. On every jump , the ball can either go to s+1 , s , s-1 distance in the either direction. We need to find out , if the ball could ever land safely on a safe path with a speed 0.

  For the problem , I discussed a recursive approach and was able to code it as well , but , I again answered the compexity to be O(2^N) which I later realised was incorrect. I was not asked to code the dynamic programming solution as we were short of time. There were no questions regarding the core subjects.

• The interview lasted for 2 hours and I was unsure of the results as , I clearly didn't answer few questions. But fortunately , later that day , I received an email that I had cleared this round and will be having a next in-house interview round.

Round 4 : In-House Interview | CodePair

• This round was scheduled on codepair. There were 2 interviewers.

• The interview started with a data structure design question.

  • Design a web browser history. The data structure should be able to do the following operations optimally :
    • Create a search history.
    • Delete a search history.
    • Retrieve a search history
    • Search URL in the history e.g. searching 'google' should show the results consisting of all the strings consisting of google in it.

  I discussed the approach with implementation of using a doubly linked list and a hashMap. The interviewer was convinced about the approach and discussed the time complexitied for the same. I managed to answer the question correctly.

• The next question was based on designing a database for a social media network.

  • You are given a company and its social media platform. A user can create a post and the post has likes and comments associated with it. The user can select which other users can see the post. The posts made by any department should only be visible to the employees of that department. Design a database and discuss the normalisation forms for the same.

  I started answering the question with help of NV( Noun Verb ) Technique. I made a few classes and started discussing the LLD of the system. The interviewer restricted me to design a SQL Database. So , I made a few assertions and made tables for user. The interviewer realised this would take a lot time and decided to move on to the next question.

• The next question was based on Binary Search Trees.

  • Given a BST and a new TreeNode , you need to insert the node in the tree , and return the parent of the node when and if inserted in the tree.

  I was confused at first and couldn't understand the question if we had to insert the node in the tree or just return the parent. We discussed the time complexities of naive solution and then took time to find the solution to optimise. I came up with the approach of finding the intervals of the leaf nodes in which the node with data 'x' could be inserted. I couldn't move further with the solution despite of hints. The interviewer told me he was done. I insisted him to tell the answer to the question and he said I discussed it rightly but didn't mention binary search on intervals.

• The interview lasted for 2.5 hours. I was unsure of the results just like the previous round.

• A few days later , I received an email of rejection.

The entire process of interviews lasted over a span of 3 months and was very exhausting. This was something that I suppose should not happen and could have wrapped up in lesser time. D.E. Shaw is very fanatical and extremely selective about hiring.