PhonePe | SE (backend) 1 - 3 years DSA round | Interview
Summary
I applied online for a Software Engineer (backend) role at PhonePe and faced two DSA questions in the interview, which I was unable to solve.
Full Experience
yoe: 2yrs applied online
was asked two DSA questions
- https://leetcode.com/problems/burst-balloons/ (hard)
- the celebrity problem (medium)
interviewer was nice and helped where ever they could. Wasn't able to solve any of them.
Interview Questions (2)
Given n balloons, indexed from 0 to n - 1. Each balloon has a number printed on it representing its point value. You are asked to burst all the balloons. If you burst balloon i, you will get nums[left] * nums[i] * nums[right] points. left and right are adjacent indices of i. After the burst, the left and right then become adjacent. Find the maximum points you can collect by bursting the balloons wisely.
In a party of N people, a celebrity is a person who is known by everyone but does not know anyone. You are given a square matrix M[][] of size N x N where M[i][j] = 1 if i knows j, and M[i][j] = 0 otherwise. Your task is to find the celebrity in the party. If a celebrity is present, find their index (0-indexed). If no celebrity is present, return -1. You may assume that the knows(A, B) function is available which returns true if A knows B, and false otherwise.