Intuit

# Interview Experience ## Round 0: Online Assessment *Type:** Online Assessment *Duration:** 90 minutes *Format:** 4 problems Note: Please make sure to write this test on Chrome browser and on Windows. I started the test on Ubuntu and my keyboard stopped working and I lost around 15 minutes in that.* **String Cost Minimization:** Given a string with lowercase Latin letters, define the cost of the string as the sum of $f^2$ for every character from 'a' to 'z', where $f$ is the frequency of that character. Given a number $m$, you can remove at most $m$ characters from the string. Find the minimum cost you can achieve. *Solution:* Take the most frequent character and decrease its frequency by one; repeat this $m$ times. **Maximum Sum Subsequence:** Given an array of integers, select a subsequence with maximum sum such that it doesn’t include adjacent indices. Report the maximum sum. *Solution:* This can be solved easily using dynamic programming. **Infection Grid:** Given a grid with blocked, healthy, and infected cells, the infected cells can infect all adjacent healthy cells in one second. Find the time in which all the healthy cells will be infected. *Solution:* This can be solved easily using multi-source BFS. **Gold Collection in Tunnels:** Given two tunnels which have gold in sorted order, a robber starts collecting gold from one end and can jump to another tunnel at any spot if the number of gold at that particular spot is equal to it. The robber can’t visit an already visited cell. Report the maximum amount of gold he can achieve. *Note:* The problem didn’t look solvable to me in the given constraints, so I focused on getting it partially correct and got 3/6 test cases right. ## Round 1: Technical *Type:** Technical The round started with a brief introduction and shifted to projects. I was asked to choose a project, and there were in-depth questions about it. I was asked if I was in touch with Computer Networks (CN); I said I’m not, and there were no questions about it. There were questions from **OS**, **DBMS**, and one **DSA** problem: **DSA Problem:** [Minimum number of towers required such that every house is in the range of at least one tower](https://www.geeksforgeeks.org/minimum-number-of-towers-required-such-that-every-house-is-in-the-range-of-at-least-one-tower/) I was also asked to code it. ## Round 2: Technical *Type:** Technical The interview again started with an introduction. Then I was asked to design a class model for MySQL and provide brief ideas of how I’ll go about implementing them, which covered various **OOPs** concepts. There were various **OS** and **DBMS** related questions and no questions from CN. Then I was asked the following **DSA** problem, with the only change that it was a square grid: **DSA Problem:** [Atlantic Pacific Water Flow](https://www.geeksforgeeks.org/atlantic-pacific-water-flow/) **Approach:** First provided an $O(n^4)$ solution (BFS from all nodes). Then provided an $O(n^2 \log n)$ solution using DSU. Then provided an $O(n^2)$ time and space solution. **Follow-up:** Optimize the space complexity to $O(1)$ (ignoring the space used by the queue). I did that by modifying the original grid, and they were satisfied. ## Overall Experience The interviewers were very friendly and supportive throughout the interview. The questions related to core subjects were in-depth, and superficial knowledge won’t be enough. The DSA problems were relatively easy for me.