Question: AppDynamics, On-Campus, IIT-BHU, SDE-1, Interview Experience, 2022 Placement Season | House Robbery
0
Entering edit mode

OnCampus: IIT BHU

Post: SDE

Total CTC: 28 LPA

Tentative Location: Bangalore

Initial Shortlisting

Initial shortlisting had 3 Coding Questions and few MCQs. Coding questions were easy, and solved were most of the students, hence MCQs played a vital role in shortlisting.

Round 1: DSA round (45 minutes)

1. House Robbery Gfg, link here: House Robbery

2.

``````There is a grid with 0 and 1. 0 means wall and 1 means free path
there is a starting and ending point given for a ball. Ball can be
rolled in any direction once rolled it keeps on rolling until it
finds an edge or a wall. Find min number of roles to reach endpoint.
``````

Round 2 (Managerial round) (45 minutes)

The interview started off as a general introduction. Following the introduction was grilled a lot on Projects and previous Internship Experience. No DSA questions were asked.

Round 3 (HR round) (20 minutes)

Basic HR questions were asked like

• Strengths and weaknesses
• Competitors of Cisco and what do you know about Cisco

Tips and Takeaways

• Be vocal, think loud and keep your fundamentals clear.
• MCQs played a key part in shortlisting which most candidates miss out on.

Verdict: Will be updated

All the Best to you guys!

0
Entering edit mode

## Question 1 (House Robbery)

Overview

• There are N houses built in a line, each of which contains some value in it.
• A thief is going to steal the maximal value of these houses, but he can’t steal in two adjacent houses because the owner of the stolen houses will tell his two neighbors left and right sides.
• The task is to find what is the maximum stolen value.

Solution

• This is a simple dp problem where you have two cases.
• First is the case where you take the current house value. In this case, you cannot take the value present at the next index, so you move to index+2.
• Second is the case where you do not take the current element. In this case, you move to index+1.
• At last answer is maximum(case2,case3) that is maximum(arr[i]+solve(idx+2),solve(idx+1)).

PseudoCode

``````ll fnd(ll idx, vector&lt;ll&gt; &amp;dp, vector&lt;ll&gt; &amp;a, ll n)
{
if (idx &gt;= n)
return 0;

if (dp[idx] != -1)
{
return dp[idx];
}

ll ans = 0;
ans = max(ans, a[idx] + fnd(idx + 2, dp, a, n));// if current value is taken
ans = max(ans, fnd(idx + 1, dp, a, n));// if current value is not taken
return dp[idx] = ans; // return maximum of the above two
}
``````
0
Entering edit mode

Q2) Minimum Rolls

Assumption

• If the ball has a chance to change direction i.e in case of blockage, then it can chose any 4 directions( N,S,E,W) which is not blocked.
• The number of rolls are corresponding to number of steps.

Solution

• The question can be solved by BFS with some modification.
• The thing to observe here is ,the ball continues to roll until it founds a blockage, and if it founds a blockage then it can take any 4 direction.
• Let's suppose if ball is currently at (X,Y,dir), and if it comes with direction dir at (X,Y). Here we have two cases, i.e
• Next movement of the ball in direction dir is blocked.
• In this case, the ball can move in any direction if it is not blocked.
• Next movement of the ball in direction dir is not blocked
• In this case , the ball continues to move in direction dir

Pseudo Code

``````    for(int i=0;i&lt;4;i++)
{
q.push({i,src});
dist[src.F][src.S][i]=0;
}

while(!q.empty())
{
pair&lt;int,int&gt;  curr=q.front().S;
int dir=q.front().F;
q.pop();
if(valid(curr,dir))//Check whether there is no blockage in direction dir
{
pair&lt;int,int&gt;  temp=curr;
temp.F+=dx[dir];
temp.S+=dy[dir];
if(dist[temp.F][temp.S][dir]&gt;dist[curr.F][curr.S][dir]+1)
{
dist[temp.F][temp.S][dir]=dist[curr.F][curr.S][dir]+1;
q.push({dir,temp});
}
}
else
{
for(int d=0;d&lt;4;d++)
{
pair&lt;int,int&gt; temp=curr;
temp.F+=dx[d];
temp.S+=dy[d];
if(valid(curr,d))
{
if(dist[temp.F][temp.S][d]&gt;dist[curr.F][curr.S][dir]+1)
{
dist[temp.F][temp.S][d]=dist[curr.F][curr.S][dir]+1;
q.push({d,temp});
}
}
}
}
}
`````` Similar Posts