Phonepe Problem Solving Interview Experience (Off Campus)

• Experience: 6 months

Overall interview experience was nice, the interviewer was also great.

First we both introduced ourselves then moving on with the interview.

• First question
  • There is a restaurant and restaurant serves n dishes, each dish has a quality and a price.
  • A dish is considered better if the quality and price of it is higher than other dish.
  • Given n dishes find minimum number of changes in quality remove the above condition for any pair of dish.

I could not able to solve this, the hidden concept was "Longest Increasing subsequence", by sorting the array based on prices then applying LIS.

• Second question

  • The question was very much related to this https://leetcode.com/problems/minimum-speed-to-arrive-on-time/, basically same concept.

• Thid question, was related to finding maximum number of points can a rabbit make while reaching to the end of array provided maximum number of jumps k he can hoop.

  • Was a simple DP question but the discussion went more keeping tracking of maximum value of the moving window of size k.

For example, to reach index i I can jump from i-k... i-1. Right ? How I can keep track of maximum value of window while this window will be moving(like a queue) during the iteration. Sucks, I couldn't come up with satisfactory answer so he told we can use deque.

I don't think I will recieve a call considering I was able to solve only 2 questions (one and a half).

Edit: The third queston is related to https://leetcode.com/problems/jump-game-ii/