D E Shaw Interview Experience || OA
So my interview started with some basic personal questions like
- Tell me about yourself.
- What is your interest in fields? I replied that I am quite confident in Java, and apart from it, I am also working on Python, Django, etc.
Then we were shifted to the coding round, They asked me 2 questions,
Question 1) Server Maximum Cost
Some nodes were given with edge weight. We can have maximum k edge to a each nodes. remove the extra nodes such that edge weigth sum is maximum.
eg.
K = 2
Total Nodes = 5,
2 4 15 (from, to, weight)
2 3 30
2 0 5
0 1 10
graph =>
result => 15 + 30 + 10 => 55
explanations => 2 has total 3 egdes but we can have maximum 2 so remove the 2———-0 so that edge weight sum become maximum.
eg 2
K = 2
graph =.>
0 1 1
1 2 1
2 3 1
result => 1 + 1 + 1 => 3
explanation => no need to remove any edge because all edge degree is less than or equal to 2.
Second question that he asked was
Question 2) Problem Setting
N Ideas were given with M Tag & relations between Problems & tag is given in 2D Matrix
tag[ith][jth] = 1 or 0 , 1 means there is relations between ith idea & jth tag. Cost to each tag row is given.
constrains
N <= 700
M <= 12
cost[i] <= 10^9
We have to select all the tag such that total idea cost is minimum
eg.
costs => 2, 2, 2, 3
matrix
[[0,1,0,1]
[0,1,1,1],
[1,1,0,0],
[1,0,1,0]]
There will be two combinations such that all the tags are selected
row 0 & 3 & cost => cost[0] + cost[3] => 5
if we select row 1 & 2 then cost => 2 + 2=> 4
so answer is 4.
I answered both question confidently.
At last, they asked about my experience with this interview and about my views on Favtutor company, and If I was having any queries to ask.
I asked about the objective of their company.
So that’s all about my interview experience, and 3 days later I received a joint letter for this internship.