Senior Software Engineer at MakeMyTrip

How it went

What they would tell you

How to prepare

Their background

Round by round

1. 1

   Data Structures and Algorithms60 min

   Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not. The problem is same as Leetcode 279 So, I was solving the problem for the first time and got bit nervous as I had never done this problem previously. So I initially proposed the solution to generate all perfect squares upto the given number n and then stores all these numbers in the array. And then we can check in similar way like unbounded knapsack for pick and not pick case. In my case the interviewer was not interacting much and was not helpful at all. When I shared him above solution he said "if you think this is correct then implement it". So I started coding the problem on vscode. I wrote recursive solution but I messed up the base conditions due to which answer was coming wrong. I wrote debug statement and spent lot of time to debug it. Eventually in last 5 minutes I was able to write recursive solution. Then he gave me a large number and my code was giving TLE as I had not memoized it. I explained him we can memoize it but since time was over, so he took my code and interview was over.

   • Perfect Squares

What came up