Microsoft | Software Engineer | Hyderabad | Dec 2020 [Offer]

Process of Applying:

I applied on the career website many times and also asked several LinkedIn connections for referrals. One day, I received an email confirming my profile was shortlisted for the Software Engineer position, and interviews would be scheduled soon. Notably, I received a referral-based interview call.

Interview Process:

Round 1: Data Structure & Algorithm based + System Design + Project Discussion (1 hour)

This round began with a brief introduction, followed by a discussion on the projects I had worked on and was currently involved with. The interviewer then presented some feature enhancement scenarios for one of my projects, which we discussed in detail.

Q1) Design a Dynamic Questionnaire
I was asked to design a dynamic questionnaire with different difficulty levels, where each level contained a set of questions. The level was to increase or decrease based on the correctness of the answer. We had a comprehensive discussion on its High-Level Design (HLD) and Low-Level Design (LLD), system readiness checks, and the appropriate tech-stack to be used.

Q2) Print Sorted Distinct Elements then Remaining Duplicates
Given an unsorted array with duplicates, the task was to print the sorted distinct elements first, followed by the remaining duplicates. For example, for an input `[34,12,2,1,67,89,5,67,8,76,12]`, the output should be `[1,2,5,8,12,34,67,76,89,12,67]`. I initially proposed a naive O(N^2) approach, then an O(N log N) sorting-based solution. The interviewer then challenged me to code an O(N) solution without extra space, given that the range of array values was [0-1000]. I explained my approach and proceeded to code it.

Round 2: Data Structure & Algorithm based + Project Discussion (1 hour)

This round involved an in-depth discussion about my project, including the tech-stack used, my roles, and responsibilities. The interviewer thoroughly reviewed my resume, specifically noting my competitive programming profiles and discussing aspects related to competitive programming.

The interviewer provided HackerRank problem links, explicitly stating that there would be two DSA-based questions. The expectations were clear: the first question needed to be solved within 20 minutes with all test-cases passed, and the second within 15 minutes with at least all basic test-cases passed. Both solutions were expected to be highly optimized and production-ready code.

Q1) Longest Increasing Subsequence (Medium) with Variations
This was a Longest Increasing Subsequence problem, described as Medium difficulty, with specific variations such as how to print the sequence and how to modify the same code to print the sequence without adding an extra loop. The link provided was for the 'common-child' problem. I approached this using Dynamic Programming for the most optimized solution; for printing the sequence, only the approach was required.

Q2) Difference Array Update (Medium-Hard)
I was presented with a Difference Array Update problem, described as Medium-Hard. I explained my approach and then coded the solution.

Q3) Confidential Data Transfer Puzzle
The interviewer asked me a puzzle: I have a bag containing confidential data that I need to send to a friend. The constraints were: the bag can hold two locks at a time, but one lock is sufficient for safety; I have one lock and key, and my friend has one lock and key; I cannot share my key with anyone, not even my friend. I was asked to describe how to parcel the bag to my friend ensuring the safety of the confidential data inside it.

Round 3: Computer Science Fundamentals + Project Discussion (1 hour)

This round commenced with an extensive discussion about my previous company project. I was asked to explain the project, the algorithms used, and potential improvements or enhancements using the latest tech-stack. This discussion lasted for about 15-20 minutes.

Computer Science Fundamentals Questions:

• Operating System questions related to mutex-semaphore, deadlock, banker’s algorithm, Paging, and Page Replacement Algorithms.
• Difference between SQL and NoSQL.
• Questions on multithreading, synchronization, class-level and object-level locking.
• Memory management (Java memory structure), Garbage collection (popular garbage collection strategies and algorithms), Collection framework in Java, String class related concepts like SCP (String Constants Pool), and the `String.intern()` method.
• Java 8 features (Streams, Lambda, Functional programming, Method references).
• Regarding Android (I had done a boot camp course during college): What challenges did I face while working on it? Which Android application did I work upon? (A complete overview)

Q1) Unique Username Hashing
Given an input string (username), I had to append a hash value N number of times to it to make it unique. I was asked to write production-ready code for this, given the hash value and N. We discussed my approach using `StringBuilder` (mutable), `StringBuffer` (for multithreaded environments), and eventually considered using a `char[]` array. There was also a discussion on how time complexity would vary if the hash value to be appended was a single character versus a string of length N.

We concluded this round with a discussion about the work and tech stack of the team for which I was being interviewed.

Round 4: Behavioural Questions + Design Problem + Project Discussion (1 hour)

Again, my current project was discussed for 15-20 minutes, with questions designed to test my knowledge of load handling and system design aspects of the system.

Coding Questions:

Q1) Count Pairs (x^y > y^x)
Given two arrays X and Y of positive integers, I needed to find the number of pairs (x, y) such that x^y > y^x, where x is an element from X and y is an element from Y.
Input: M = 3, X[] = [2 1 6], N = 2, Y[] = [1 5]
Output: 3

Q2) Find Pairs with Sum X from Two Arrays
Given two unsorted arrays and a given number x, the task was to find all pairs (one from each array) that add up to X.
Input : A = [3 , 57 , 8 , 1 , 9], B = [0 , 2 , 6 , 11 , 25]
Output : [ [3,6] , [9,0] , [8,1] ]
We discussed how the code would change if duplicates were present, how time complexity would be affected if negatives were included, and the consequences of having unequal-sized arrays. I initially started with a `HashSet` approach for distinct elements, then moved to a `HashMap` for handling duplicates, and finally converged on a Two-pointer approach that required no extra space.

Behavioural Questions:

• What innovations have I done at my workplace apart from my assigned work?
• How do I handle conflicts between team members?
• How do I handle negative feedback?
• What are my strengths and weaknesses?
• How do I handle failures and setbacks?

Puzzle: Maximize White Ball Probability
There are two empty bowls in a room. I have 50 white balls and 50 black balls. After placing all the balls in the bowls, a random ball will be picked from a random bowl. I was asked to distribute all the balls into the bowls to maximize the chance of picking a white ball.

The round concluded with a discussion on roles and responsibilities, expectations, and the tech-stack related to the team and project I would potentially be joining.

Result:

The recruiter confirmed my selection the very next day and asked for details like my expected compensation and any existing offers. I officially received the offer letter today, a week later (15-12-2020).