Position: SDE 2
Location: Bengaluru
Date: May 23
Education: BTech from Tier 1 college
YOE: 2 years as SDE at Top Investment bank.

Application: I applied via a referral.

Round 1 - Coding

Question: Given an array of size n, return the maximum difference of the maximum and minimum of each window of size k. Time allotted - 90 mins.

During the coding round, I had an interview with a member from the bizops team who had transitioned away from the technical domain about a year ago. Although he was not well-versed in the technical aspects of the problem, he was expecting an O(n) solution without explicitly mentioning it. Initially, I started with a brute force solution of O(n^2) complexity and later optimized it to O(nlogn). However, the interviewer requested that I implement the solution without using any libraries.

Since my initial solution involved using a binary search tree (BST), the interviewer specifically asked me to implement a self-balancing binary search tree, such as an AVL Tree or Red-Black Binary Search Tree. Initially, there was some confusion as the interviewer did not believe that AVL Trees and self-balancing binary search trees were the same thing. I took the opportunity to explain and demonstrate that they are indeed the same concept. This explanation took approximately 40 minutes, leaving me with limited time to implement the AVL Tree.

However, despite not being able to fully implement the AVL Tree, I eventually arrived at an O(n) solution using a deque. If I had not spent significant time on the AVL Tree implementation, I could have reached this optimal solution earlier.

It can be puzzling at times how interviewers may ask questions that they themselves do not have a complete understanding of.

Verdict: Reject
(Reason: Took a considerable amount of time to reach the O(n) solution and couldn't fully implement the requested solution without using inbuilt libraries.)