Google

## Online Assessment (Virtual) This was the online assessment in which 2 DSA problems were asked. The total time was 60 minutes for both of them. There was no individual time limit for each question, though the questions were tough to be solved within the given time. *Question 1:** Given an array with N elements and two integers X and Y, we can perform operations of 2 types: **Type 1:** Choose index and subtract 1 from it. **Type 2:** Choose index and replace it with 0. Determine the maximum length subarray that can be obtained such that the value of all elements in the subarray is zero after applying at most X operations of Type 1 and Y operations of Type 2. **Approach:** Binary search and using sets to maintain the top Y elements. *Question 2:** We are given 2 integers N and K and we have N queries of the form L, R, X where we add X to every element in the range L to R (both inclusive). We had to find the longest subsequence that is lexicographically minimum and the subsequence should also be an increasing Arithmetic Progression with common difference as K (Z, Z+K, Z+2*K, ... so on). **Approach:** I used a map to store the query values and DP. -- ## Interview Round 1 (Virtual) We started off with each other’s introductions before jumping into Google Docs for the DSA question. There were no questions related to core subjects at all, which was expected. The round was scheduled to be 45 minutes long. The question was based on a binary tree and the structure of the tree was similar to this problem: [Minimum Flips in Binary Tree to Get Result](https://leetcode.ca/2022-07-24-2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/). The tree structure involves AND, NOT, XOR, OR at nodes and True/False at the leaves. The given tree evaluates to some boolean value. *Question:** Find out the values if we flip each leaf node (True -> False / False -> True) individually. We had to return a boolean vector with size equal to the number of leaves. **Initial Approach:** I started with the brute force approach that uses 1 DFS to find out the answer for every leaf node flip where the DFS function returns the evaluated value for the current subtree. **Optimization:** The interviewer asked me to optimize it. I struggled for some time and needed hints before coming up with an approach involving storing the evaluated value for every subtree. For example, if a node has an OR operator and we get True from the left subtree and False from the right subtree, flipping any leaf node in the right subtree won’t affect our final answer (since the left side is already True). Thus, we don't continue DFS for the right side but do it for the left side since a flip there can have an effect. **Coding:** Once the approach was done, I was asked to code it up during the last 10 minutes, including the `TreeNode` struct and the DFS functions. -- ## Interview Round 2 (Virtual) The second round took place around 30-45 minutes after the first round and was conducted for most candidates who cleared the first round. *Question 1:** After introductions, he gave me a standard problem based on 2D prefix sums. I had to find the minimum sum submatrix of size `a * b` in a matrix of size `n * m`. (Similar to: [Find maximum sum submatrix](https://www.techiedelight.com/find-maximum-sum-submatrix-in-given-matrix/)) **Approach:** I started with the brute force solution and optimized it using 2D prefix sums. Once the interviewer was satisfied, I was asked to code it and perform a dry run for a sample matrix. *Question 2:** Since we still had time left, we moved to another question similar to [City with the smallest number of neighbors](https://www.geeksforgeeks.org/problems/city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/0). *Exact Question:** We have N locations, some of which are Google data centers. We want to pick a location such that its distance from any data center is as large as possible. **Approach:** I initially suggested Floyd-Warshall to find distances between all pairs, then a Dijkstra-based solution running from every data center. **Optimization:** The interviewer mentioned that the weight of every edge was 1, so I proposed a multi-source BFS solution. I had to prove why it would work. Once satisfied, I coded it up. -- ## General Advice Importance was given to the thought process and why a particular solution works. Ensure code is readable as you will be coding on Google Docs. Be thorough with time and space complexities. Keep track of time; interviewers stick to the 45-minute limit.