Yelp Onsite 21-30

P21 面的Backend的SDE职位。Oncampus投的简历然后就有HR联系给了oncampus的interview。面了45分钟。主要是resume + 白板 + backend设计。面试官是个三哥manager, 人很nice。问的题也很简单。就是给一个只有0, 1的矩阵。0只在1前面出现。求出现1最多的行数。优化到O(m + n)就可以了。

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int findMax1(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return -1;
        int idx = matrix[0].size()-1, res = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            while (idx >= 0 && matrix[i][idx] == 1) {
                --idx;
                res = i;
            }
        }
        return res;
    }
};

int main() {
    Solution s;
    vector<vector<int>> matrix = {{0,0,0,1},{0,0,1,1},{0,1,1,1},{1,1,1,1},{1,1,1,1}};
    cout << s.findMax1(matrix) << endl;
}

P22 有一轮题是multiplyString, 说完思路以后，并没有白板写题，而是小哥是让我在他的mac book上写code然后直接跑的。

43 Multiply Strings

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    string multiply(string str1, string str2) {
        reverse(str1.begin(), str1.end());
        reverse(str2.begin(), str2.end());
        int sign = 1;
        if (str1.back() == '-') {
            sign *= -1;
            str1.pop_back();
        }
        if (str2.back() == '-') {
            sign *= -1;
            str2.pop_back();
        }

        int s1 = str1.size(), s2 = str2.size();
        vector<int> tmp(s1+s2+1, 0);

        for (int i = 0; i < s1; ++i) {
            for (int j = 0; j < s2; ++j) {
                tmp[i+j] += (str1[i]-'0')*(str2[j]-'0');
                tmp[i+j+1] += tmp[i+j]/10;
                tmp[i+j] %= 10;
            }
        }

        while (tmp.size() > 1 && tmp.back() == 0) tmp.pop_back();

        string res;
        if (sign == -1) res += '-';
        for (int i = tmp.size()-1; i >= 0; --i) res += tmp[i]+'0';

        return res;
    }
};

int main() {
    Solution s;
    cout << s.multiply("99999999", "9999999999") << endl;
    cout << s.multiply("99999999", "0") << endl;
    cout << s.multiply("0", "0") << endl;
    cout << s.multiply("-8744375", "-43547389276") << endl;
}

P23 给一个String，全是小写或者数字，输出他的所有大小写组合。例如输入a2c，输出就是a2c, a2C, A2c, A2C.

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
    void dfs(string& word, int pos, vector<string>& res) {
        if (pos == word.size()) {res.push_back(word); return;}
        if (word[pos] >= '0' && word[pos] <= '9') dfs(word, pos+1, res);
        else {
            word[pos] = tolower(word[pos]);
            dfs(word, pos+1, res);
            word[pos] = toupper(word[pos]);
            dfs(word, pos+1, res);
        }
    }
public:
    vector<string> combination(string word) {
        vector<string> res;
        dfs(word, 0, res);
        return res;
    }
};

int main() {
    Solution s;
    for (auto& a: s.combination("a2bc")) cout << a << endl;
}

P24 251. Flatten 2D Vector

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d): x(0), y(0), v(vec2d) {

    }

    int next() {
        return v[x][y++];
    }

    bool hasNext() {
        while (x < v.size() && y == v[x].size()) {
            ++x;
            y = 0;
        }
        return x < v.size();
    }
private:
    int x, y;
    vector<vector<int>> v;
};

P25 88. Merge two sorted Arrays

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* l = new ListNode(-1), *cur = l;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        cur->next = l1 ? l1:l2;

        return l->next;

    }
};

P26 two sum 变形题，返回所有pairs,可重复 （我居然在这上卡了）

#include <vector>
#include <unordered_set>
#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<int>> twoSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        unordered_set<int> m;
        for (auto& n: nums) {
            if (m.count(target-n)) res.push_back({n, target-n});
            m.insert(n);
        }
        return res;
    }
};

int main() {
    vector<int> nums = {1,2,3,4,5,6,7};
    Solution s;
    vector<vector<int>> res = s.twoSum(nums, 8);
    for (auto& a: res) cout << a[0] << " " << a[1] << endl;
    return 0;
}

P27 valid anagram, 然后group anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        vector<int> m(26,0);
        for (int i = 0; i < s.size(); ++i) {
            ++m[s[i]-'a']; --m[t[i]-'a'];
        }

        for (auto& a: m) {
            if (a) return false;
        }
        return true;
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string& s: strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            m[tmp].push_back(s);
        }
        vector<vector<string>> res;
        for (auto& a: m) res.push_back(a.second);
        return res;
    }
};

P28 两个文本的Cosine Similarity，简单的version

P29 这道题面筋没看过，management pair,<a, b>, <b, c>, <b, d>, 建造一个general tree，return root是最大的boss，这个没写完，但思路蛮简单的说了

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
using namespace std;

struct Node {
    Node(string x): val(x) {}
    string val;
    vector<Node*> children;
};

class Solution {
public:
    vector<Node*> buildTree(vector<vector<string>>& relations) {
        vector<Node*> res;
        unordered_map<string, Node*> m;
        unordered_set<string> c_set;
        for (auto& a: relations) {
            if (!m.count(a[0])) m[a[0]] = new Node(a[0]);
            if (!m.count(a[1])) m[a[1]] = new Node(a[1]);
            m[a[0]]->children.push_back(m[a[1]]);
            c_set.insert(a[1]);
        }
        for (auto& a: m) {
            if (!c_set.count(a.first)) res.push_back(m[a.first]);
        }
        return res;
    }
};

int main() {
    Solution s;
    vector<vector<string>> relations = {{"a","b"},{"b","c"},{"b","d"},{"e","f"}};
    for (auto& a: s.buildTree(relations)) cout << a->val << endl;
    return 0;
}

P30 Regular Expression 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 = 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];
    }
};