# Microsoft

## Interview Questions

Sergey Kharagorgiev
What to expect at Microsoft?

Be able to discuss the big-O complexity of your approaches. Don't forget to brush up on your data structures like lists, arrays, hash tables, hash maps, stacks, queues, graphs, trees, heaps. Also sorts, searches, and traversals(BFS, DFS). Also review recursion and iterative approaches.
Use the programming language you're best at. It's important to write your solution correctly and in time, so use the language you are most familiar with.
Find and fix the bugs by yourself: Don't wait for the interviewer to find them for you.
Use the hints you are given: Usually, the interviewer knows the question well enough to know which hints will help you next if you get stuck.

Majority Element

Given an array of size `n`, find the majority element. The majority element is the element that appears more than `floor(n/2)` times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example :

``````Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2.
``````

Distribute Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Sample Input :

``````Ratings : [1 2]
``````

Sample Output :

``````3
``````

The candidate with 1 rating gets 1 candy and candidate with rating cannot get 1 candy as 1 is its neighbor. So rating 2 candidate gets 2 candies. In total, `2+1 = 3` candies need to be given out.

Max Rectangle in Binary Matrix

Given a 2D binary matrix filled with `0`’s and `1`’s, find the largest rectangle containing all ones and return its area.

Bonus if you can solve it in O(n^2) or less.

Example :

``````A : [  1 1 1
0 1 1
1 0 0
]

Output : 4

As the max area rectangle is created by the 2x2 rectangle created by (0,1), (0,2), (1,1) and (1,2)

``````

Max Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Return an integer corresponding to the maximum product possible.

Example :

``````Input : [2, 3, -2, 4]
Return : 6

Possible with [2, 3]
``````

Regular Expression Match

Implement wildcard pattern matching with support for `'?'` and `'*'`.

• `'?'` : Matches any single character.
• `'*'` : Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:

``````int isMatch(const char *s, const char *p)
``````

Examples :

``````isMatch("aa","a") → 0
isMatch("aa","aa") → 1
isMatch("aaa","aa") → 0
isMatch("aa", "*") → 1
isMatch("aa", "a*") → 1
isMatch("ab", "?*") → 1
isMatch("aab", "c*a*b") → 0
``````

Return 1/0 for this problem.

Edit Distance

Given two words `A` and `B`, find the minimum number of steps required to convert `A` to `B`. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example :
edit distance between
`"Anshuman"` and `"Antihuman"` is 2.

• Operation 1: Replace s with t.
• Operation 2: Insert i.

Regular Expression II

Implement regular expression matching with support for `'.'` and `'*'`.

`'.'` Matches any single character.
`'*'` Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

``````int isMatch(const char *s, const char *p)
``````

Some examples:

``````isMatch("aa","a") → 0
isMatch("aa","aa") → 1
isMatch("aaa","aa") → 0
isMatch("aa", "a*") → 1
isMatch("aa", ".*") → 1
isMatch("ab", ".*") → 1
isMatch("aab", "c*a*b") → 1
``````

Return `0 / 1` ( 0 for false, 1 for true ) for this problem

Swap List Nodes in pairs

For example,
Given `1->2->3->4`, you should return the list as `2->1->4->3`.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given `1->2->3->3->4->4->5`, return `1->2->5`.
Given `1->1->1->2->3`, return `2->3`.

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists, and should also be sorted.

For example, given following linked lists :

``````  5 -> 8 -> 20
4 -> 11 -> 15
``````

The merged list should be :

``````4 -> 5 -> 8 -> 11 -> 15 -> 20
``````