Phonepe Problem Solving Interview Experience (Off Campus)
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.
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/