InterviewBit Entrance Test B

1

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

2

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

3

Can you share your approach here …

4

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
5

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 :confused: (it was printing just 1)

6

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…:pensive: But still at the end it gives me segmentation fault and I really didnt know where i am wrong…:persevere::pensive:

7

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

9

Logic for 5th Question?

10

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
Final answer : 3

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

1 Like
11

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 …:pensive:

12

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.

13

How did you get the question ? You’re already an academy student. :smiley:

14

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

15

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

16

Is solving 3 questions good enough to get selected?

17

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

18

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

19

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

20

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

21

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