Technical phone screen:

1. NxN forest

'L' -> position of lion
'C' -> position of your car
'X' -> your position

0_1_2_3_4_5_6_7_8_9
0|||||||||||
1||||||||C|||
2|||||||||||
3|||||||||L||
4||L|||||||||
5|||||||||||
6|||||L||||||
7||||||||L|||
8|||||||||||
9||L|||X||||||

For any path from X to C, the closest you come to a lion in that path = k

Use manhatten distance (x1,y1), (x2,y2) = abs(x2-x1) + abs(y2-y1)

Goal: Find path with highest value of k and return k

Answer:
I used DP and solved this problem. Was happy with my performance. HR gave feedback that i could have done optimizations as time complexity of my solution was: n X n X number of lions.

Round1:
Let’s assume there are few cities and there are day-tours organised either within cities or between cities. Given a number of days,
we want to find a strategy for finding a starting city which is going to be most satisfying for the customer. How do we go about it?

Question was not explained well and no test case was given. I assumed that L5 level they expect me to ask right set of questions and model the problem.
Feedback from HR: I solved this problem correctly and but got confused in telling complexity. (i might have got nervous)

Round 2:
A car, with a tank of volume K liters, and a constant fuel consumption of X liter per kilometer, starts driving in a straight line from the origin towards a destination D kilometer away.
Along the road, there are N fuel stations, each at a distance di away from the origin. The cost of fuel at each fuel station is Pi per liter.
Write code to compute the cheapest cost of fuel to reach the destination. Assume that the car starts with a full tank.

Again here no test case was given and explaination was not given as i have written.
Interviewer said that you have to go from origin to some point and there are some petrol pumps on the way. and there are petrol pumps.
Then i asked whether i can asusme that mileage is same always - he said no. He told that petrol pumps can have different prices. I aksed him whether at origin there will be petrol pump- he said your car has tank of K capacity and it is filled.

I solved it using recursion and then showed that i can do dynamic programming with key as pair<index, currentPetrolInTank>;

Interviewer gave the hint that currentPetrolInTank can be double and thus DP might not be that helpful. But i didnt came with better solution at that time. After couple of hours thinking - i realized how i would have optimized it. But i felt this was really tough problem as it needed DP and greedy both to solve this problem in 45 mins.

Round3:
Given integer 'n', how can we re-arrange the numbers 1 to n in such that for any two numbers their avg. shouldnt come in between the two numbers: Example : for input 4 : answer wil be 1 3 2 4

Told brute force approach of generating permutations and validating whether condition is satisfied :) But obviously i have to optimize.
Interviewer started giving hints and we together came to the solution. But lost the time to code.

As L5 - i am 100% sure of rejection. :) Will try after 6 months again.

I feel that my bad luck started from round 2 itself. Round 2 question was hard as per me. Round 3 question was pattern detection. I hate pattern detection questions.

Please share your thoughts.