# Microsoft Interview Problem Set Summary

• Regular Expression

``````class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*')  dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
else dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
}
return dp[m][n];
}
};
``````

Wildcard Matching

``````class Solution {
public:
bool isMatch(string s, string p) {
int m=s.size(), n=p.size();
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));

dp[0][0]=true;
for(int i=1; i<=m; i++){
dp[i][0] = false;
}
for(int i=1; i<=n; i++){
dp[0][i] = (p[i-1]=='*') && dp[0][i-1];
}

for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(p[j-1]!='*')
dp[i][j]=(p[j-1]=='?'||p[j-1]==s[i-1]) && dp[i-1][j-1];
else
dp[i][j]=dp[i-1][j]||dp[i][j-1];
}
}
return dp[m][n];
}
};
``````

Populating Next Right Pointers in Each Node II

``````class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
TreeLinkNode* head = nullptr, *prev = nullptr, *cur = root;
while (cur != nullptr) {
while (cur != nullptr) {
if (cur->left) {
if (prev) prev->next = cur->left;
else head = cur->left;
prev = cur->left;
}

if (cur->right) {
if (prev)  prev->next = cur->right;
else head = cur->right;
prev = cur->right;
}
cur = cur->next;
}
cur = head;
head = nullptr;
prev = nullptr;
}
}
};
``````

In-order Successor

``````class Solution {
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* result = nullptr;
while (root) {
if (root->val > p->val) {
result = root;
root = root->left;
}
else
root = root->right;
}
return result;
}
};

``````

Closest Binary Search Tree Value

``````class Solution {
int closestValue(TreeNode* root, double target) {
int result = root->val;
while (root) {
if (abs(result - target) >= abs(root->val - target))
{
result = root->val;
}
root = target < root->val ? root->left : root->right;
}
return result;
}
};
``````

Closest Binary Search Tree Value 2

``````class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
inorder(root, target, k, res);
return res;
}
void inorder(TreeNode *root, double target, int k, vector<int> &res) {
if (!root) return;
inorder(root->left, target, k, res);
if (res.size() < k) res.push_back(root->val);
else if (abs(root->val - target) < abs(res[0] - target)) {
res.erase(res.begin());
res.push_back(root->val);
} else return;
inorder(root->right, target, k, res);
}
};
``````

Find Celebrity

``````class Solution {
public:
int findCelebrity(int n) {
int res = 0;
for (int i = 0; i < n; ++i) {
if (knows(res, i)) res = i;
}
for (int i = 0; i < n; ++i) {
if (res != i && (knows(res, i) || !knows(i, res))) return -1;
}
return res;
}
};

``````

Rotate Image

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

``````class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
/**
* clock rotate : rotate[j][n-1-i]=a[i][j]
**/
reverse(matrix.begin(), matrix.end());   /** a[n-1-i][j]=a[i][j] **/
for(int i=0; i<matrix.size(); i++){   /** a[i][j]=a[j][i] **/
for(int j=i+1; j<matrix[i].size(); j++)
swap(matrix[i][j], matrix[j][i]);
}
}
};
``````

Number of Islands 1 & 2

Island Count 1

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m=grid.size();
if(m==0)    return 0;
int n=grid[0].size();

int result=0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]=='1'){
help(i, j, grid);
result++;
}
}
}
return result;
}

void help(int i, int j, vector<vector<char>>& grid){
/*** make sure the corner condition is OK ***/
if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0')
return;
grid[i][j]='0';
help(i+1, j, grid);
help(i-1, j, grid);
help(i, j+1, grid);
help(i, j-1, grid);
}
};
``````

Island Count 2

``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> res;
if (m <= 0 || n <= 0) return res;
vector<int> roots(m * n, -1);
int cnt = 0;
vector<vector<int> > dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
for (auto a : positions) {
int id = n * a.first + a.second;
roots[id] = id;
++cnt;
for (auto d : dirs) {
int x = a.first + d[0], y = a.second + d[1];
int cur_id = n * x + y;
if (x < 0 || x >= m || y < 0 || y >= n || roots[cur_id] == -1) continue;
int new_id = findRoots(roots, cur_id);
if (id != new_id) {
roots[id] = new_id;
id = new_id;
--cnt;
}
}
res.push_back(cnt);
}
return res;
}

int findRoots(vector<int> &roots, int id) {
while (id != roots[id]) {
roots[id] = roots[roots[id]];
id = roots[id];
}
return id;
}
};

``````

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

``````class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummy = new ListNode(-1), *pre = dummy;
dummy->next = head;
while (pre->next && pre->next->next) {
ListNode *t = pre->next->next;
pre->next->next = t->next;
t->next = pre->next;
pre->next = t;
pre = t->next;
}
return dummy->next;
}
};
``````

Reverse Nodes in K groups

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *cur = head;
for (int i = 0; i < k; ++i) {
if (!cur) return head;
cur = cur->next;
}
//current is the k-nodes-groud's next node
//so we reverse the from head to the previous node of cur
ListNode *new_head = reverse(head, cur);
head->next = reverseKGroup(cur, k);
return new_head;
}
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = head;
while (cur->next && cur->next != tail) {
ListNode* next = cur->next;
cur->next = next->next;
next->next = dummy->next;
dummy->next = next;
}
return dummy->next;
}
};
``````

Merge K sorted lists

``````struct compare {
bool operator() (ListNode* a, ListNode* b) {
return a->val > b->val;
}
};

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
for (int i = 0; i < lists.size(); i++) if (lists[i]) pq.push(lists[i]);
ListNode* head = nullptr, *pre = nullptr, *temp = nullptr;
while (!pq.empty()) {
temp = pq.top();
pq.pop();
if (!pre) head = temp;
else pre->next = temp;
pre = temp;
if (temp->next) pq.push(temp->next);
}
return head;
}
};
``````

Intersection of Two Linked Lists

``````class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
ListNode *a = headA, *b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};
``````

Encode and Decode String

``````class Codec {
public:
// Encodes a list of strings to a single string.
string encode(vector<string>& strs) {
string res = "";
for (auto a : strs) {
res.append(to_string(a.size())).append("/").append(a);
}
return res;
}
// Decodes a single string to a list of strings.
vector<string> decode(string s) {
vector<string> res;
int i = 0;
while (i < s.size()) {
auto found = s.find("/", i);
int len = atoi(s.substr(i, found).c_str());
res.push_back(s.substr(found + 1, len));
i = found + len + 1;
}
return res;
}
};
``````

Simplify Path

``````class Solution {
public:
string simplifyPath(string path) {
string result, t;
stringstream ss(path);
vector<string> v;
while (getline(ss, t, '/')) {
if (t == "" || t == ".") continue;
if (t == ".." && !v.empty()) v.pop_back();
else if(t != "..") v.push_back(t);
}
for (auto a : v) result += "/" + a;
return result.empty() ? "/" : result;
}
};
``````

Jump Game

``````class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.empty()) return false;
int reach = 0;
for (int i = 0; i <= reach && i < nums.size(); i++) {
reach = max(reach, nums[i] + i);
}
if (reach < nums.size() - 1)
return false;
return true;
}
};
``````

Jump Game 2

``````class Solution {
public:
int jump(vector<int>& nums) {
if (nums.empty()) return 0;
int start = 0, end = 0, limit = 0;
int result = 0;
while(limit < nums.size() - 1) {
result++;
for (int j = start; j <= end; j++) {
limit = max(limit, nums[j] + j);
if (limit >= nums.size() - 1) return result;
}
start = end + 1;
end = limit;
}
return result;
}
};

``````

Longest Palindromic Sub-string

DP solution :

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int result = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
result = max(result, dp[i]);
}
return result;
}
};
``````

Binary Search Solution

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i = 0; i < nums.size(); ++i) {
int left = 0, right = dp.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[mid] < nums[i]) left = mid + 1;
else right = mid;
}
if (right >= dp.size()) dp.push_back(nums[i]);
else dp[right] = nums[i];
}
return dp.size();
}
};

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> lis;
lis.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < lis[0]) lis[0] = nums[i];
else if (nums[i] > lis.back()) lis.push_back(nums[i]);
else { int pos = binary_search(lis, nums[i]); lis[pos] = nums[i]; }
}
return lis.size();
}

int binary_search(vector<int>& v, int target) {
int left = 0, right = v.size() - 1;
while (right > left) {
int mid = left + (right - left) / 2;
if (v[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
};
``````

House Robber 3

``````class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = dfs(root);
return max(result[0], result[1]);
}

vector<int> dfs(TreeNode* root) {
if (!root) return vector<int>(2, 0);
vector<int> left = dfs(root->left);
vector<int> right = dfs(root->right);
vector<int> result(2, 0);
result[0] = max(left[0], left[1]) + max(right[0], result[1]);
result[1] = left[0] + right[0] + root[val];
return result;
}
};
``````

Decode Ways

``````class Solution {
public:
int numDecodings(string s) {
int len = s.size();
if (len == 0) return 0;
vector<int> dp(len + 1, 0);
dp[0] = 1;
dp[1] = (s[0] != '0');
for (int i = 2; i <= len; i++) {
dp[i] = (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) ? dp[i-2] : 0;
if (s[i-1] != '0') dp[i] += dp[i-1];
}
return dp[len];
}
};
``````

String to Integer

``````class Solution {
public:
int myAtoi(string str) {
if (str.empty()) return 0;
int base = 0, sign = 1, i = 0;
while (str[i] == ' ') i++;
if (str[i] == '+') i++;
else if (str[i] == '-') { sign = -1; i++; }
while (str[i] >= '0' && str[i] <= '9') {
if (base > INT_MAX / 10 || (base == INT_MAX/10 && str[i] - '0' > 7)) {
if (sign == 1) return INT_MAX;
else return INT_MIN;
}
base = 10 * base + (str[i++] - '0');
}
return base * sign;
}
};
``````

• @fight.for.dream Nice. Wonder if you can give a bit of background bout these problems. Were these the interview questions you were asked?
If so I'm curious about the process and your interview experience with them, because there are A LOT of problems here. Did they cram all these in one interview for you?
Thanks

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.