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.