Intuit

## Online Assessment **Format**: 4 questions, Camera/Mic proctored. **Duration**: 1.5 hours. **Constraints**: Not visible. ### Questions: **Maximum Sum Non-Adjacent Elements**: Given an array, pick elements such that the total sum is maximized and no two elements are adjacent. *Solution*: Solved using 0-1 Dynamic Programming. **Minimum Squared Sum of Frequencies**: Given a string of lowercase English alphabets, perform $m$ operations where each operation entails deleting a character. Compute the minimum possible value of the squared sum of the frequencies of each character after operations. *Solution*: Solved using a priority queue. **Maximum Path Sum in Two Sorted Arrays**: Given two sorted arrays A and B. You can traverse the arrays with constraints: cannot visit an already visited element, can visit adjacent unvisited elements in the same array, and can jump from A to B (or vice versa) only if $x = y$. *Solution*: Partially solved using 2D DP while updating values in merge-sorted order. 2/6 test cases passed. **Contaminated Grid**: Given an $n \times m$ grid where cells are blocked, healthy, or contaminated. Compute the minimum time after which there are no healthy cells. Contaminated cells spread to neighbors. *Solution*: Solved using multi-source BFS. ## Interview Round 1 **Combinatorics/DP**: Count the number of ways to match people such that each person is either part of a pair or single. I used a combinatorial approach: $\sum f(x)$ where $x$ is the number of singles. The interviewer asked for manual calculations for $n=4, 5, 6$ to verify. For $n=6$, the answer was 76. **Scalability & Math**: How to handle large $n$ for the previous problem? Discussed modulo arithmetic, precomputing factorials, binary exponentiation, and Fermat’s Little Theorem for modular inverse. **SQL Query**: Write a query to return all duplicate email addresses in a table `(ID, email)`. Used `GROUP BY` and `HAVING count(*) > 1`. **Mathematics**: Prove that the average of odd primes of the form $(x, x+2)$ (where $x \neq 3$) is divisible by 6. Provided a proof using the $6n \pm 1$ property of primes. **Operating Systems**: Threads vs. Processes: Execution units, context, address spaces. Semaphores: Signaling, P (wait) and V (signal) operations. ## Interview Round 2 **Project Discussion**: Detailed discussion on Spring Boot usage in projects, specifically microservices generation from UML diagrams. **System Design (Monolith vs. Microservices)**: Why pivot from monolith to microservices? Discussed agility, independent scaling, and maintainability. Specific scenario: Adding a GPU-focused recommendation system to a CPU-heavy monolith. **Spring Boot Architecture**: Explained layers (API Gateway, Authentication, Eureka Server, Data Service) and components (Models, Services, Controllers, Annotations, Spring Data JPA). **ORM**: What is an ORM? Why use it over raw SQL? Discussed abstraction, developer convenience, and prevention of SQL Injection. **Spring Internals**: What is a Bean? Mentioned Dependency Injection and IoC containers. **C++ OOP**: Predict output for a method called in both constructor and destructor, overridden in a derived class. Discussed `virtual` methods and their behavior during construction/destruction. **Polymorphism**: Discussion on compile-time polymorphism (Function/Operator overloading). **Design Patterns**: Explained Strategy, Builder, and Singleton patterns. **Operating Systems**: Threads vs. Processes (repeated). Synchronization: Semaphores, Locks, and Monitors. **DSA Question**: Given a root of a binary tree where certain nodes are marked, compute the shortest path from the root that visits all marked nodes and returns to the root. *Solution*: Structured using DFS. Discussed optimizing into a single DFS call.