Microsoft Interview Problem Set Summary


  • 0
    F

    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;
        }
    };
    

  • 0
    P

    @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


Log in to reply
 

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