Microsoft | SDE-2 | Pune

Interview 1 Initially, the interview asked me about my current work experience and explained the technical challenges which I face daily.

Part 1

Given an array containing stock prices, find the maximum profit that can be made by trading a single stock. For eg : input = [2, 4,6,9,12] output = 10 . Max profit can be achieved by Buying the stock at 2 and selling at 12

Part 2

Modification to the above question. Now multiple stocks can be bought and sold. However, before buying a new stock, you have to sell the previous stock. For eg: input = [4,1,10, 2,8] Output = 15 . Buy @1 and Sell @10. Buy @2 and Sell @8

Interview 2

You are given a N* N chess board and a list of co-ordinates which denote the rook position. You need to return the number of non-attacking positions on the chess board.

[ 0 1 0 1 0 0 0 0 0 ]

In the above configuration, the rook is present at (0,1) and (1,0). The total non-attacking positions would be 1 i.e only the point (2,2). Since the rook can attack vertically and horizontally, the rook at (0,1) covers all boxes in row 0 and column 1. Similarly, for the rook at (1,0) column 0 and row 1 is covered. So, the only left position is (2, 2). I was asked to derive the formula and write the code.

The interviewer further asked me to code a singleton class. I completed the implementation and he asked me for the flaw in the code. I had to design a singleton for a multi-threaded program. Further, the discussion was related to the race condition between two threads. He gave me the following code snippet :- i =0 ; { i++; i++; i++; print i; } The above snippet was accessed by two threads T1 and T2. You need to find the maximum & minimum value of the variable i printed. There is no synchronization between the two threads

Interview 3

1. The interviewer first asked me to design an interface for the queue data structure which contains the methods enQueue and DeQueue. Further, the dequeue call should block when there are no elements present in the queue. After designing the interface, the interviewer asked me what were the shortcomings in the code. For eg: - I had implemented the code in C++, and the enqueue method was public void enqueue(T enqueue). Basically, he wanted public void enqueue(const T& enqueue). There was a discussion surrounding the usage of Copy Constructors, exception handling, etc

2. A binary search tree is given and Add, Read, Update, Delete operations are performed. Every operation results in a new version of the BST. Given a version, you need to return the full tree in O(1).

Interview 4

A Sudoku board is given. The user enters numbers and coordinates of the position where the number is to be placed. In case of an invalid configuration, the code needs to return an error. Complete the below function :-

public boolean isValidSudoku(int number, int row, int column)

I suggested having a set of 9 integers for all rows and columns and for the box. However, he suggested optimizing the solution for space. I recommended using short int and using bit shift operations to determine whether a number is already added or not.

Overall Verdict :- Rejected