DE Shaw visited VIT, Vellore for the position of Quality & Test Engineering . The CGPA cutoff was 7.0 and more than 1500 students appeared for 1st online round.
1st online round – This round was conducted in Hackerrank portal for a total duration of 95 minutes and was divided into 4 sections.
1st section – Aptitude Section: 14 Questions for 28 minutes . Questions were moderate and not too hard to solve .But i was bit too nervous and completely messed it up and i think i solved around 5-6. The questions were a mix of quantitative reasoning and general aptitude.
2nd section – Technical Section: 12 Questions for 17 minutes. This section comprised of guess the output questions, general programming concepts, SQL questions ,and some based on Data Structures and Algos. I think I gave too much time to some questions rather than moving to next questions. I managed to solve 5-6.
3rd Section – There were 2 coding questions. 20 minutes were allocated for 1st question and 30 mins were allocated for 2nd question. Since, i have been doing competitive coding , i knew i can do well in this section.
(1) Given an array of positive integers, find out the number of sub-arrays which consist of prime numbers only – Fairly simple question , used sieve of Eratosthenes and coded in 7 mins and passed all test cases in first go. I build some confidence moving into next question.
(2) This was a hard question.Given 2 arrays, array A (containing only 0s and 1s) and the other cost array B of the same size. We needed to convert all the elements of array A to 1 in minimum cost. For every ith element in the array A, converting from 0 to 1 requires B[i] cost but if A[i-1] and A[i+1] are 1 then A[i] can be converted to 1 with 0 cost. Return the minimum possible cost to convert all 0s to 1s. I thought for around 12-13 mins but simply could not come up any optimal approach. Than i made up a BFS solution over all indexes (brute force approach) and to my surprise i passed 9/13 test cases.
18 students were shortlisted for ROUND 2.
It began next day 12 pm. There were 2 interviewers. It was a code pair round and was only about problem solving and lasted for almost 100 mins and i was given 5 back to back coding questions. They tested the solution that i coded with actual hidden test cases for 3 questions. Nothing was asked on projects and core subjects. T
(1) Given a BST, convert it to a complete BST (A Tree is a complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible) . My interviewer explained me the question. I was sitting idle . Nothing crossed my mind. I coded the solution for BST to AVL tree. He was adamant and wanted complete tree configuration. I gave up and he didn’t gave me any hints.
(2) Given a string, find the count of all substrings of a string having atmost 3 unique characters. Told them about brute force solution i.e n^2 approach. Than , i told them about 2 pointer approach and using a hashmap to store unique characters. Fast coded the solution and passed every test cases that they gave.
(3) Give a matrix of n rows and m columns of 0’s and 1’s. In each row, the first few cells have a value 0 and the remaining all have value 1. The problem is to find the minimum index of the column which contains a value 1. I skipped the O(n^2) and immediately gave binary search approach O(n*logm). They asked me for a better approach. I thought for a while and presently slightly more optimised solution. Later after the interview i realised that this can be done in linear time if we traverse the matrix diagonally.
(4) Given a grid . Find minimum moves to go from position (0,0) to (n-1,n-1). But, the grid will have some obstacles and we can only go through at most k obstacles. Free position will be marked 0 and obstacle will be denoted by 1. I took my time and came up with optimised Dijkstra with some modifications. They seemed satisfied as my code passed 39/41 test cases and was getting TLE for last 2 test cases.
(5) Word break problem (https://www.geeksforgeeks.org/word-break-problem-dp-32/). First coded the recursive approach , than they asked for more optimization. I added one dp table to store the results of overlapping solutions. Passed sample test cases and they tested against some corner cases. I was really confident now and thought i was done and was ready to submit it. But, they wanted more optimization. Now ,the optimization that dp solution gives us is that we can check if we have a possibility of partitioning the string from a certain index and if its not possible to partition from that index, dp table will simply return -1 and we wont check it again. But, the major issue is if its possible than what next ? We do have to generate all the combinations from that index again which was already computed earlier. So , we are repeating things which we have already done. We are not storing the combinations which is already generated from that index. For more clearity on what i said, What they wanted is :: given str = “aaaaaaaaaaa” dict = [“a”,”aa”,”aaa”,”aaaa”,”……”,] . Now, if dp returns true from a certain index ( say 5), still we will be calculating all the partitions from that index when we visit it another time in our recursion tree. Here , though index 5 will return true that at least 1 partition is possible but still suffix[5:len-1] will have many possibilities and dp isn’t returning those. I listened to them very carefully and understood shortcomings of my dp solution. My interviewer expected me to return also all the possible combinations. Again took some time and it took me around 20 mins more to change everything and dry run. They ran my code again, though i passed (9/11) but was getting segmentation fault in last 2 test cases.
Let me again explain what they really wanted from me, for example in a standard coin change problem , our dp[i][j] doesn’t only states whelther a sum of i is possible or not by taking first j coins, but in fact dp[i][j] also states us the number of ways a sum of i can be achieved by taking first j coins. They wanted this kind of optimization.
One interviewer seemed pleased while other didn’t. Finally , they asked me if i had any questions for them. I said no. I was pretty happy how things went. I really enjoyed the challenges. But, i was rejected after this round and around 6 people were called for next round. At last , 2 candidates were selected for internship.