Hi Everyone,
I had my 1st round of OA at DE shaw, which were 2 DSA questions:
- https://stackoverflow.com/questions/78605468/minimum-numbers-of-operation-required-to-make-an-array-bitonic
- Given a tree with n nodes, n-1 weighted edges, you can remove as many edges from the graph, output the maximum sum possible of the tree such that every node has atmost k edges
I solved the first question completely and second question 12/15 TCs passed using greedy approach, and was selected for the 2nd round which was codepair interview round
The codepair round started with introduction and project discussion, then he went for the first DSA question:
- Given a richer array where each array element states that the first person is richer than second, ex: [[0,1],[2,1],[2,3]]. You are also given a calmness array P stating the calmness value of each person. ex: calmness of person 0,1,2 given is [8,9,3]. Now return the answer array, where ans[x]=y, y is a person richer than x and having minimum calmness among all the person who are richer than x. It is guaranteed that there will always be a person with minimum richness. So ans[1] in this example will be 0, because person 0 & 2 both are richer that 1 but person 0 has the minimum calmness. I was able to solve this completely with O(n) complexity.
- Second, question was to code Map data structure and it's function, followed by a set of questions:
- How is this data structure able to take multiple data types in input, ex: map<int,int>, map<string,string>. Ans: It will be class structure using generics in Java
- Write the methods it should perform, like get, put, remove etc.
- What happens if the key is already present, what is this phenomena called? Ans: Collision and explained about collision handling.
- How will you make these methods thread safe?
- What are the variious issues when using multithreading?
- What is race-condition?
- What are volatile and synchronized?
I was able to answer all the queries except the last one, after this i was informed to have 4 rounds in a single day including HR round. But the next day they called me and said further rounds will be scheduled any other day only when I will clear the 3rd round.
Third round started with project discussion and then a DSA question:
- Given a string, we have to remove the duplicates from the string such that the resulting string should be lexicographically largest possible. Ex: cbdbca, possible strings with single occurences cbda, bdca, dbca etc, but the largest possible is dbca hence the answer.
- I couldn't solve this one, expected time complexity was O(n), the interviewer gave hints and by the end I coded the correct solution.
But the expectation here again was to solve atleast 2 DSA questions in an interview. Finally after 3 days i was given a beautiful rejection mail.
Hope this helps !!
Happy Coding !!