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)**

Two DSA questions were asked:

- House Robbery Gfg, link here: House Robbery

Click here to Practice

Submit Problem to OJ

2.

Click here to Practice

Submit Problem to OJ

```
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.
- Thorough knowledge of your project and brushing up your internship days will definitely help you, even in situation based questions.

**Verdict: Will be updated**

**All the Best to you guys!**

Entering edit mode

**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<ll> &dp, vector<ll> &a, ll n)
{
if (idx >= 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
}
```

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**

- In this case , the ball continues to move in direction

- Next movement of the ball in direction

**Pseudo Code**

```
for(int i=0;i<4;i++)
{
q.push({i,src});
dist[src.F][src.S][i]=0;
}
while(!q.empty())
{
pair<int,int> 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<int,int> temp=curr;
temp.F+=dx[dir];
temp.S+=dy[dir];
if(dist[temp.F][temp.S][dir]>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<4;d++)
{
pair<int,int> temp=curr;
temp.F+=dx[d];
temp.S+=dy[d];
if(valid(curr,d))
{
if(dist[temp.F][temp.S][d]>dist[curr.F][curr.S][dir]+1)
{
dist[temp.F][temp.S][d]=dist[curr.F][curr.S][dir]+1;
q.push({d,temp});
}
}
}
}
}
```