Microsoft Corporation SDE-2 Interview Questions, Process, and Tips

Round duration - 60 Minutes
Round difficulty - Easy

Q1. 
Next Greater Element Problem Statement
Given a list of integers of size N, your task is to determine the Next Greater Element (NGE) for every element. The Next Greater Element for an element X is the firs...read more
Ans. 
I solved this via stack

1. Push the first node to stack.

2. Pick the rest of the node one by one and follow the following steps in the loop: 

3. Mark the current node as next node.

4. If the stack is not empty, compare the top node value of the stack with next node value.

5. If next node value is greater than the top node value then, Pop the top node from the stack and next is the next greater element for the popped no...read more
Answered Anonymously
Add your answer
Q2. 
Clone Linked List with Random Pointer
Your task is to create a deep copy of a linked list, where each node has two pointers: one that points to the next node in the list, and a 'random' pointer which can ...read more
Ans. 
This is bit tricky because if you you create entire nodes and then copy value of original linked list node then you will shallow copy the references.
I tried to deep copy from end node to head node, but yeah you need to store prev references as those are lost because of previous problem I mentioned above.
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Smallest Window Problem Statement
Given two strings S and X containing random characters, the task is to find the smallest substring in S which contains all the characters present in X.
Input:
The first...read more
Ans. 
1. First check if the length of the string is less than the length of the given pattern, if yes then “no such window can exist “.

2. Store the occurrence of characters of the given pattern in a hash_pat[].
we will be using two pointer technique basically

3. Start matching the characters of pattern with the characters of string i.e. increment count if a character matches.

4. Check if (count == length of pattern ) this means...read more
Answered Anonymously
Add your answer
Q2. 
Connect Nodes at Same Level Problem Statement
Given a binary tree, connect all adjacent nodes at the same level by populating each node's 'next' pointer to point to its next right node. If there is no nex...read more
Ans. 
I tried multiple approaches like storing direct child in queue and then retrieving and connecting in them and also adding further direct child in queue.

I was not able to solve this completely and some corner case was missing like when there is no right or left child.
But interviewer told me that you tried it nicely.
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Q1. 
Closest Palindrome Problem Statement
You are given a string 'S' that represents a number. Your task is to find the closest palindromic number to this integer represented by 'S'. The closest number is defi...read more
Ans. 
I solved it with below steps
1. Break the string into half.
2. Take first half and then reverse this first half and append.
e.g
3745, its first half is 37 and then reversing the first half I will get 73. So next largest no which is palindrome is 3773.

3. Consider a case when you get no. less than the given no. e.g 3796
Following #2 approach you will get 3769 which is less than 3796.
In this case I incremented the first half b...read more
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Minimum Operation Needed to Convert to the Given String
You are given two strings str1 and str2. Determine the minimum number of operations required to transform str1 into str2.
Explanation:
An operatio...read more
Ans. Greedy Approach
1. We will do the two-pointer approach, Initialize the first pointer to the start of str1 and the second pointer to the start of the str2.
2. Now increase the first pointer till the character pointed by the first pointer in str1 matches the character at the second pointer in str2. And the number of character which did not match should be placed at the end of str1. Therefore increase our answer by how many times...read more
Answered Anonymously
Add your answer
Q2. 
Snake and Ladder Problem Statement
Given a Snake and Ladder Board with 'N' rows and 'N' columns filled with numbers from 1 to N*N starting from the bottom left of the board, and alternating direction each...read more
Ans. 
It is very similar to the above problem

The idea is to consider the given snake and ladder board as a directed graph with number of vertices equal to the number of cells in the board. The problem reduces to finding the shortest path in a graph. Every vertex of the graph has an edge to next six vertices if next 6 vertices do not have a snake or ladder. If any of the next six vertices has a snake or ladder, then the edge ...read more
Answered Anonymously
Add your answer
Q3. Can you provide a high-level design of a web crawler?
Ans. 
Tip 1: Take Queues for background processes, Use bloomfilter to reduce DB query while checking if same URL is already processed, Use different services for page parsing and download pages. You can have separate queues based on domain so that you can parse all pages of same domain once. Use reddis cache to store latest pages.

Tip 2: Use Distributed systems, HDFS for storage large unstructured content and analytical jobs

T
Answered Anonymously
Add your answer

Round duration - 70 Minutes
Round difficulty - Medium

Q1. Design a system that can efficiently handle millions of requests to save or update a key-value pair, as well as millions of requests to read the value of a key.
Ans. 
Some of the tips are here.
Tip 1 : Think about CAP theorem. You have to be consistent here bit of latency is fine.
Tip 2 : Ask about dirty reads are allowed or not. if allowed , you can think on making system faster. Keep the data in cache so that if some old value is fine you can refresh cache after some period of time.
Seperate DB for write and read. Readers can sync from write DB asynchronously.
Answered Anonymously
Add your answer