 # 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 ?