3 questions were asked after some introductions.

https://leetcode.com/problems/squares-of-a-sorted-array . Was asked to write pseudocode. https://www.geeksforgeeks.org/dsa/maximize-sum-of-k-elements-in-array-by-taking-only-corner-elements/ . Gave a recursive brute force solution of O(2^k). Was asked to optimise. Started to think of a DP solution when I remembered O(k) solution. Explained and wrote the code for it. https://leetcode.com/discuss/interview-question/309656/google-reorder-array-according-to-the-given-indexes. Quickly explained the constant solution. Seemed satisfied with the solution and didn't ask to code. Then, he extended the same question to repeat the same process ‘k’ times that too without any extra space. Time was running out and after just giving me 2 mins to think, he told me we are out of time. Couldn't give him any solution for this.

This time no introduction, straight to coding questions.

Find the row with the maximum number of 1s. First he gave me this question, for which I gave him 3 approaches. One with naive searching O(m * n), another with a binary search on each row with O(mlogn), and another O(m+n) approach. He asked about the 2nd solution and changed the question to https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ He wanted me to write the working code for this and even loaded some test cases into the IDE which my code needed to pass. First gave him an O(n * klogk) brute force solution. Tried to build from the median in an integer stream solution. Told him will have to keep a left max heap and right min-heap. After each slide of the window, removal will be O(logk) if we keep value vs index hashmap and addition is also O(logk). Analysed time complexity and it came out to be O(nlogk) and he was satisfied with the approach and no code was needed. It was kind of a generic string grouping question, but since there wasn't much time left, he wanted me to find a hash function to distinguish each group. Gave a string-based hash, but he wanted an integer one. After a few minutes, I couldn't come up with anything so gave a prime number based hash solution, where each number is mapped to a corresponding prime number and then multiply all the prime numbers to avoid collisions. He didn't seem satisfied, but there was no time left. He ended the interview after I asked some questions about the inner workings of Flipkart. Got the mail for the managerial round within 40 mins after the interview.