Pratik Patil

PhonePe Interview Experience

Round 1: The first round was entirely focused on data structures and algorithms. Three questions were asked during this round, mostly from dynamic programming, trees, and graphs. The difficulty level of the questions ranged from medium to hard. Question 1: You are given a tree where each node has a value associated with it. You can pick any node, and the value corresponding to that node will be added to your score. However, once a node is selected, you cannot pick its direct children. Your task is to maximize the score. My Approach: I explained a solution using tree-based dynamic programming concepts. The solution was based on the pick or don't pick strategy. I maintained a Boolean variable to decide whether to take the current node or not. Depending on the decision made for the current node, the next process was simulated. Then, I memorized the solution using a DP table of size N2. Question 2: Best Time to Buy and Sell Stock IV My Approach: I explained the solution using a recursive function with parameters like index, transactions used, and a Boolean parameter to indicate whether we should buy or sell. For buying, I added the negative of the price, and for selling, I added the actual price. I memoized the solution using a DP table of size NK*2, and then I explained an iterative solution with optimal space complexity using just PREV and CURR, similar to Striver's approach. Question 3: Given a binary tree, find the k-th ancestor of any node and report -1 if the ancestor is not present. My Approach: I explained the solution using binary lifting. In binary lifting, we store the 2^i-th parent for all the nodes. I started by finding the 2^0 th parent for each node using DFS, and then calculated the2^(i+1)-th parent using the 2^i-th parent. This approach is better for query-based problems. The interviewer was impressed since I provided optimal solutions and used concepts like binary lifting to solve the problem. We then had a discussion about PhonePe and the importance of problem-solving for software engineer.

Round 2: This round also focused on data structures and algorithms, and the problems asked were more challenging than those in the first round. The first question was about Disjoint Set Union (DSU). The problem involved deleting edges, but DSU is typically used to add edges. To solve this, the offline queries technique was required. By starting the queries from the last one, deleting edges could be treated as adding them, since it’s done in reverse order. This approach allowed for the correct handling of edge removals using the Disjoint Set Union. The second problem was based on geometry. The task was to find the maximum slope between points and connect those points. The solution involved calculating and comparing the slopes to determine the maximum one. I was able to solve the second problem successfully. For the first problem, I shared my idea of using the Disjoint Set Union as part of the solution, even though I didn’t fully solve it.

Round 3: During this interview, the focus was on my internship at TraceLink Inc., where I worked for two months. The interviewer started by asking me to describe my overall experience. I talked about the company, the projects I worked on, and the new skills I gained. After that, we discussed my specific tasks in detail. The interviewer wanted to know how I managed the data used to create Grafana dashboards. I explained how I collected the data, sent it to Grafana, and ensured that everything worked smoothly. He was particularly interested in how I avoided race conditions when sending data to the Prometheus server. I explained that I used proper synchronization methods to make sure data was handled correctly and that no conflicts occurred. Next, we talked about GraphQL. The interviewer asked me to explain what it is and why it’s used. I described GraphQL as a tool that helps request exactly the data needed from an API, making it more efficient as it solves the problem of over fetching and under fetching. We then moved on to HTTP protocols. The interviewer asked about the format of HTTP requests and responses. I explained that an HTTP request includes a method, headers, and a body, while the response includes a status code, headers, and sometimes a body. I also talked about common HTTP status codes like 200 (OK), 404 (Not Found), and 500 (Internal Server Error), explaining what each one means. The conversation then shifted to the branching system we used during my internship. I explained how we used Git to manage our code, created separate branches for new features, and merged them after reviewing the changes. The interviewer was interested in how I handled conflicts during this process. I described how I communicated with team members to resolve any issues, carefully reviewed the changes, and made sure everything worked properly after merging. Finally, we discussed the interviewer’s work. He shared details about his projects and the challenges he faced, which gave me a better understanding of the work environment and how my experiences compared to his.

VERDICT: Selected