# InterviewBit Entrance Test B

Did anyone get question 1, and 5 AC ???

Yeah, I solved Question 1, It was standard DP problem.

Can you share your approach here â€¦

Define a function

``````int solve(int i,int j,int B){ //Currently we are at coordinate (i,j) with B units energy left.
if(i<0 || j<0 || i>=n || j>=n || B<0)
return -inf; //if we are getting out of grid or we have negative energy we can return
//-inf to ignore this state in answer.
if(B==1 && i==n-1 && j==n-1)
return a[i][j]; // Return the a[i][j] value, it is base case which was given in question.
if(dp[i][j][B]!=-1)
return dp[i][j][B];
int ans=-inf;
ans=max(ans,a[i][j]+solve(i,j+1,B)); // Go right without spending any energy.
ans=max(ans,a[i][j]+solve(i+1,j,B)); // Go down without spending any energy.
ans=max(ans,a[i][j]+solve(i-1,j,B-1)); // Go up by spending 1 unit energy.
ans=max(ans,a[i][j]+solve(i,j-1,B-1)); // Go left by spending 1 unit energy.

return dp[i][j][B]=ans;
}
``````

The answer of problem can be found by calling function as solve(0,0,B);

5 Likes

Possibly dumb question, but recursive functions were being called just once. What was I possibly doing wrong?
I checked the base cases, tried both in Python and Java even tried a dummy simple recursive function to print 1 to 10 (it was printing just 1)

In 4th question I was doing everything correctly but still getting segmentation fault then I just check it on my terminal and it runs.The same code which give me segmentation fault doesnt give me nothing and print the correct outputâ€¦ But still at the end it gives me segmentation fault and I really didnt know where i am wrongâ€¦

For the 4th you just had to find maximum degree in the graph, and return (max_deg + 1)

Logic for 5th Question?

Those who donâ€™t know the 5th question:
We have an array A of length N. Now we can choose any index i such that A[i]==A[i+1] and replace both elements by a single element A[i]+1. We need to maximize the maximum element in the array after any number of operations.
N<=250
A[i]<=50
Eg.
1 1 1 1 1
â€“> 2 1 1 1
â€“> 2 2 1
â€“> 3 1

If anyone knows how to solve this then please share your approach!!

1 Like

I was doing the same thing but still didnt know why I am getting segmentation fault on interviewbit compiler and not on my own terminal â€¦

Just wondering is there any partial marking ? I wrote a brute force solution and optimized it to my best knowledge. Some test cases did pass but final result was Memory Limit Exceeded for some N roughly equal to 100.

Verdict was something like this : Memory Limit Exceeded : You need to optimize your solution in actual interviews.

How did you get the question ? Youâ€™re already an academy student.

Some ppl were discussing this on a group after the contest!!

Yes there are partial scores, but theyâ€™d let you know if your code was partially accepted, they clearly state the verdict.

Is solving 3 questions good enough to get selected?

Not sure, somewhere near May 2019, entrance test was conducted, heard that people who solved 3 got selected, so maybe 3 is enough, but competition grows everyday, this yearâ€™s icpc online round, people solved way more questions than last yearâ€¦so having solved 3 questions, thereâ€™s some chance of getting selected, all you can do is hope for the bestâ€¦ good luck

This time they also conduct a personal interview if you cleared the test which means that compared to last time selection process is difficult .

How many questions did you solved though? And they will consider best of the two days right?

Best score is going to be considered out of the two.
I was really close to solving 5, but something got messed up in 1 question so, 4 completely solved in test â€śAâ€ť and gave up halfway through test â€śBâ€ť, solved 3

Wait. I received no email for test B. I solved all 5 in test A though. Is test B the second stage ?