Online Assessment
Questions:
Question 1
There's a game called Vegetable Crush. In this game, you are allowed to choose two dissimilar veggies and cut them. Each type of veggie is represented as an integer in an array. Formally you can choose any 2 unequal integers in the array and delete them. Given an array veggies of size n, return the minimum possible number of veggies left after the given operation is performed any number of times.
Example:
n=5 veggies=[3,3,1,1,2]
Output: 1 (all 3 and 1 combos get cancelled out)
Question 2
You've a canvas of n x m size which is initially painting white, waiting to be transformed into a beautiful canvas. Each minute the canvas goes under a unique coloring process as specified by the user. A beautiful canvas is defined by the presence of a square with a side length of k where all cells within the square are elegantly colored. Determine the minimum time required for the canvas to achieve the beauty. You'll be provided n, m, k as input, along with a 2D paint array of n*m dimension representing the coordinates of the cell to be painted at ith minute.
Example:
n=2, m=3, k=2, paint=[[1,2],[2,3],[2,1],[1,3],[2,2],[1,1]]
Output: 5
Candidate's Approach
I was able to solve the first question in O(nlogn) time and passed all test cases. For the second question, I hit TLE for the last 2 test cases. I tried to apply 2D prefix sum to efficiently identify whether the canvas was beautiful or not, but that approach wasn't effective, leading to TLE.
Interviewer's Feedback
No feedback provided.
Round 1 - DSA Round
Questions:
Question
In a game of chess, you are given that there are n players, and a list of m matches between players. If a player has won a match from another player then it is said that the winning player has higher rank than the losing player. Also, if ith player wins from jth player then ith player will win from all the players jth player won from. You're tasked to return the maximum number of players for which you can deterministically identify the ranks.
Example:
n=5, m=4, matches=[[A,B],[B,C],[C,E],[D,C]]
Output: 2 we can deterministically identify the ranks for C and D.
Candidate's Approach
I converted the problem into a graph and thought of applying topological sort to get the order of players by ranking. I also considered keeping track of wins and losses, iterating over the topological sort to find the first index where win and loss counts equal n-1. However, the interviewer pointed out that this approach wouldn't work and hinted at counting the number of wins for each node to build the solution, which I couldn't figure out in the given time.
Interviewer's Feedback
No feedback provided.
Round 2 - LLD Round
Questions: I was asked to design a cricket scoreboard application, something similar to Cricbuzz with commentary, score updates, innings analysis, and player analysis. I had to expose this application via API. I was able to design the entities but due to lack of practice ran out of time for a full solution.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Final Thoughts
This was my 2nd MAANG interview in the last month, and I've identified that I'm still lacking in DSA even after doing 500+ LC questions. I need to change my preparation strategy and identify what went wrong in the DSA rounds where I didn't perform well. I plan to work on those weak points and improve my DSA skills as well as my system design skills alongside.
I hope this post is helpful for someone. Let me know if you have any questions!
Thanks!