PhonePe prep for onsite rounds.
DSA
Burning Tree
Shortest Path to Get All Keys
1235 Maximum profit in job scheduling
1657 Determine if two strings are close
Matchsticks to Square: I initially misread the example due to confusion around the input format, which cost me a bit of time. But once I understood the problem, I discussed my approach and time complexity. The interviewer seemed satisfied and we moved to the next question.
Kth Smallest Element in a Sorted Matrix: I discussed a bunch of solutions and decided that using a min heap would be the best solution. He hinted it could be optimized further. I could not think of a way, so he mentioned binary search, and gave me another hint around it, and then I could solve it.
https://leetcode.com/problems/burst-balloons/ (hard)
the celebrity problem (medium)
Round 2: PS/DS
1)https://leetcode.com/problems/remove-k-digits/description/
2)https://codeforces.com/problemset/problem/1037/D
Q1: Find the minimum number of swaps to make a string palindrome
I never seen this one before, so I tried a greedy approach, then i share my thought process, wrote the code
Q2: Given a binary tree, find the sum of all nodes at the deepest level
In this round, I was given two problems. The first one was about maximizing the total damage with spell casting. I had to come up with a strategy, either using something like a sliding window or dynamic programming, to balance between the choices and constraints and maximize the spell damage.
The second problem was about removing the most stones in the same row or column, which involved using graph theory and union-find to group stones and maximize the number removed through connected components.
I explained my approaches for both problems.
Trap Rain Water
Left View of a Binary Tree
Given a binary tree, find the list of elements which are at 'k' distance from the given target node.
Asked to implement stack and also to retrieve minimum element of the stack at any point of time.
Q1: print LOT of tree, changing direction on alternate levels, did easily
Q2: on monotonic stack, solved. He modified question, solved again, he modified 3rd time, could not complete in time, as we were nearning 1 hour 30 min (time wasted on platform issue)
https://leetcode.com/problems/matchsticks-to-square/description/
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
https://leetcode.com/problems/first-missing-positive/description/
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
https://leetcode.com/problems/complete-binary-tree-inserter/description/
ouput:- need to return the next element 5 plus the parentNode
trick:- is dont give O(n) solution want log(n) solution
able to solve in o(n)
not able to solve in log(n)
Q. I:- [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
https://leetcode.com/problems/queue-reconstruction-by-height/description/
first element :- define height of person
second elemtn:- position before
where the 4,4 means 4 people is stand above which has height greater than 4 =[5,7,6,5]
o:- [[5,0],[7,0],[6,1],[5,2],[4,4],[7,1]]
one question based on Binary Trees + DP was asked (https://leetcode.com/problems/house-robber-iii/description/).
find the Kth ancestor of the given node in the binary tree (https://leetcode.com/problems/kth-ancestor-of-a-tree-node/description/).
https://leetcode.com/problems/bricks-falling-when-hit/description/
The next question was related to the convex hull algorithm.
Asked to write a function that generates random points within a circle with equal probability distribution - solved post panel discussion
LC Hard - Maximum profit in job scheduling - explained brute force + DP optimization
Round-2 (PS/DS):
- Find an element in a rotated sorted array.
- Given a binary tree, where each node is storing a value,
find the maximum path sum of any non-empty path.
[Similar question: https://leetcode.com/problems/binary-tree-maximum-path-sum
In a array of integers. Count maximum integers you can add such that at any point the never go negative from left to right. ← However the question language was given in a scenario and it boils down to this question.
Explained and wrote code bit a typo which sucked 5 extra minutes
[sum-of-distances-in-tree] LC hard
Started with O(n*n) and eventually I gave O(n) solution. He ased to rite sudo code only as the time was less
Question 1 - Similar to rotten oranges
Question 2 - Greedy question like meeting schedule
Question 3 - Monotnic stack question similar to finding next greater question as here
Question 1 : https://leetcode.com/problems/house-robber-iii/description/
Question 2 : Close enough to the question of Leetcode: https://leetcode.com/problems/rotting-oranges/description/
2020
https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/
https://leetcode.com/problems/maximum-sum-bst-in-binary-tree
https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows
2021
https://leetcode.com/problems/trapping-rain-water/description/
https://leetcode.com/problems/number-of-islands/description/
https://leetcode.com/problems/diameter-of-binary-tree/description/
https://leetcode.com/problems/range-sum-query-2d-immutable/description/
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
2022
https://leetcode.com/discuss/study-guide/1886481/minimum-time-taken-to-burn-the-binary-tree-from-a-node
https://leetcode.com/problems/count-ways-to-build-good-strings/description/
https://leetcode.com/problems/binary-tree-cameras/description/
https://leetcode.com/problems/escape-the-spreading-fire/description/
https://leetcode.com/problems/daily-temperatures/description/
2023
https://leetcode.com/problems/longest-increasing-subsequence/description/
https://leetcode.com/problems/minimum-path-cost-in-a-grid/description/
https://leetcode.com/problems/simple-bank-system/
https://leetcode.com/problems/decoded-string-at-index/
https://leetcode.com/problems/check-array-formation-through-concatenation/
https://leetcode.com/problems/frog-jump/description/
https://leetcode.com/problems/number-of-islands/description/
https://leetcode.com/problems/where-will-the-ball-fall
https://www.hackerrank.com/challenges/down-to-zero-ii/problem
Q1. Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.
In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.
Return true if and only if you can transform str1 into str2.
Q2. https://leetcode.com/problems/ipo/description/
HLD
System Design Round
Duration: 1 hour
Was asked to design a Search Autocomplete feature.
Trie data structure needs to be used and I created a entire working solution. Discussed on its scalablility and handle different scenarios and discussion on optimisation of memory and time complexity.
System Design
The final round was a system design round to design Instagram. After discussing scope and expectations, we narrowed it down to four main features:
Posting content
Seeing one's own posts immediately after posting.
Feed generation
Likes and Comments
I discussed the qualities of the system (non-functional) and set my scale expectations well. From there, I outlined a high-level design and then looked into each of the services. While I covered the core architecture and trade-offs, I realized later that I didn’t allocate enough time to flesh out the likes/comments service fully. I hand-waved a bit near the end as I was short on time.
System Design: Design a service which registers triggers with delays, from other services and sends them response of the trigger after the time is completed for that trigger.
Design an online game like ludo/chess/snakeNladder
You need to drive the interview after this problem statement is given. Start with FNR, NFR, HLD, APIs. Talk about techstack you will use and how will you implement it, handle exceptions, fault tolerant, DB choices. Explain core logic used while designing(ex: how will you match Noob vs Noob, Pro vs Pro). Explain 2-3 approcahes for each step with trade-offs.
Key points checked: Core system design, Tech stack choice, Trade-offs, Reasoning, Knowledge depth.
Design Round
Design Payment Gateway Integration
Interviewers looked for very specific info
Design Instagram
Note: For feed publishing and fetching, Interviewer didn't agree with Message queue approach as it is not scalable for billions of users.
Design | 1 hr
Design Twitter
Functionalities:
Post Tweet
follow-following
user timeline
user profile
Focused Skills: LLD, HLD
Verdict: Strong Hire