Microsoft Interview Experience[SE, Hyderabad]

Round 1 1. Cousins in Binary Tree

Microsoft Interview Experience[SE, Hyderabad]

Round 1
1. Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins

Practise: https://leetcode.com/problems/cousins-in-binary-tree/

2. All Nodes Distance K in Binary Tree

Round 2

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Practise: https://leetcode.com/problems/squares-of-a-sorted-array/

2. Max and Min stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.

Practise: https://leetcode.com/problems/min-stack/

Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.

Implement the MaxStack class:

MaxStack() Initializes the stack object.
void push(int x) Pushes element x onto the stack.
int pop() Removes the element on top of the stack and returns it.
int top() Gets the element on the top of the stack without removing it.
int peekMax() Retrieves the maximum element in the stack without removing it.
int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Practise: https://leetcode.com/problems/max-stack/

Round 3
1. Given an `m x n` matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Practise: https://leetcode.com/problems/set-matrix-zeroes/

2. Designing Typeahead Suggestion

Services: Auto-suggestions, Cover following things in discussion

1. What is Typeahead Suggestion?
2. Requirements and Goals of the System
3. Basic System Design and Algorithm
4. Permanent Storage of the Trie
5. Scale Estimation
6. Data Partition
7. Cache
8. Replication and Load Balancer
9. Fault Tolerance
10. Typeahead Client
11. Personalization

Round 4: (Try to think about answers)

1. How Do You Deal With Difficult Employees?

For ex: Suppose you want one of your team member to do particular task(Modularisation), How will you approach it?