[关闭]
@skysbjdy 2016-12-24T06:41:53.000000Z 字数 7548 阅读 3479

亚马逊 9

Interview

  1. Copy List with Random Pointer
    LeetCode

    1. RandomListNode *copyRandomList(RandomListNode *head) {
    2.     map<RandomListNode*, RandomListNode*> hash;
    3.     RandomListNode* cur = head;
    4.     RandomListNode dummy(0);
    5.     RandomListNode* newCur = &dummy;
    6.     while(cur) {
    7.         //只能new一个指针, 而不能声明一个局部对象
    8.         newCur->next = new RandomListNode(cur->label);
    9.         hash[cur] = newCur->next;
    10.         newCur = newCur->next;
    11.         cur = cur->next;
    12.     }
    13.     cur = head;
    14.     newCur = dummy.next;
    15.     while(cur) {
    16.         if (cur->random != NULL)  //不一定每个都有哦!!!
    17.             newCur->random = hash[cur->random];
    18.         cur = cur->next;
    19.         newCur = newCur->next;
    20.     }
    21.     return dummy.next;
    22. }

  2. Order Dependency

    1. class Order {
    2. public:
    3.     string orderName;
    4.     Order(){orderName = "NoName";}
    5.     Order(string name) {
    6.         orderName = name;
    7.     }
    8. };
    10. class OrderDependency {
    11. public:
    12.     Order cur;
    13.     Order pre;
    14.     OrderDependency(Order pre, Order cur) {
    15.         this->pre = pre;
    16.         this->cur = cur;
    17.     }
    18. };
    20. map<string, vector<string>> makeGraph(vector<OrderDependency> depends);
    21. map<string, int> makeIndegree(vector<OrderDependency> depends);
    22. map<string, Order> makeOrders(vector<OrderDependency> depends);
    24. vector<Order> findOrder(vector<OrderDependency> depends) {
    25.     map<string, vector<string>> graph = makeGraph(depends); //是vector而不是set, 就是需要他重复
    26.     map<string, int> indegree = makeIndegree(depends);
    27.     map<string, Order> nameToOrder = makeOrders(depends);
    28.     int num = nameToOrder.size();
    29.     vector<Order> res;
    30.     queue<string> q;
    31.     for (std::map<string, int>::iterator it = indegree.begin(); it != indegree.end(); it++) {
    32.         if (it->second == 0) {
    33.             q.push(it->first);
    34.         }
    35.     }
    36.     while (!q.empty()) {
    37.         string name = q.front();
    38.         q.pop();
    39.         res.push_back(nameToOrder[name]);
    40.         for(string neighbor : graph[name]) {
    41.             indegree[neighbor]--;
    42.             //cout << neighbor << " == " << indegree[neighbor] << endl;
    43.             if (indegree[neighbor] == 0) {
    44.                 q.push(neighbor);
    45.             }
    46.         }
    47.     }
    48.     if (res.size() != num) {
    49.         res.clear();
    50.         cout << "invalid: there is a cycle" << endl;
    51.     }
    52.     return res;
    53. }
    55. map<string, Order> makeOrders(vector<OrderDependency> depends) {
    56.     map<string, Order> orders;
    57.     for (int i = 0; i < depends.size(); i++) {
    58.         orders[depends[i].pre.orderName] = depends[i].pre;
    59.         orders[depends[i].cur.orderName] = depends[i].cur;
    60.     }
    61.     return orders;
    62. }
    64. map<string, vector<string>> makeGraph(vector<OrderDependency> depends) {
    65.     map<string, vector<string>> graph;
    66.     for (int i = 0; i < depends.size(); i++) {
    67.         graph[depends[i].pre.orderName].push_back(depends[i].cur.orderName);
    68.     }
    69.     return graph;
    70. }
    72. map<string, int> makeIndegree(vector<OrderDependency> depends) {
    73.     map<string, int> indegree;
    74.     for (int i = 0; i < depends.size(); i++) {
    75.         if (indegree.find(depends[i].pre.orderName) == indegree.end()) {
    76.             indegree[depends[i].pre.orderName] = 0;
    77.         }
    78.         indegree[depends[i].cur.orderName]++;
    79.     }
    80.     return indegree;
    81. }

  3. Minimum Spanning Tree

    1. class Connection{
    2. public:
    3.     string node1;
    4.     string node2;
    5.     int cost;
    6.     Connection(string a, string b, int c){
    7.         node1 = a;
    8.         node2 = b;
    9.         cost = c;
    10.     }
    11. };
    13. int comp(const void* a, const void* b);
    14. int comp2(const void* a, const void* b);
    15. bool unionFind(Connection con, map<string, string>& parent);
    16. string find(string node, map<string, string>& parent);
    19. vector<Connection> getLowCost(vector<Connection> connections) {
    20.     vector<Connection> res;
    21.     map<string, string> parent;
    22.     set<string> nodes;
    23.     qsort(&connections[0], connections.size(), sizeof(Connection), comp);
    24.     for(int i = 0; i < connections.size(); i++) {
    25.         parent[connections[i].node1] = connections[i].node1;
    26.         parent[connections[i].node2] = connections[i].node2;
    27.         nodes.insert(connections[i].node1);
    28.         nodes.insert(connections[i].node2);
    29.     }
    31.     for (int i = 0; i < connections.size(); i++) {
    32.         if (unionFind(connections[i], parent)) {
    33.             res.push_back(connections[i]);
    34.         }
    35.     }
    36.     if (res.size() != nodes.size() - 1) {
    37.         res.clear();
    38.         return res;
    39.     }
    40.     qsort(&res[0], res.size(), sizeof(Connection), comp2);
    41.     return res;
    42. }
    44. int comp(const void* a, const void* b) {
    45.     return ((Connection*)a)->cost - ((Connection*)b)->cost;
    46. }
    48. int comp2(const void* a, const void* b) {
    49.     Connection con1 = *((Connection*)a);
    50.     Connection con2 = *((Connection*)b);
    52.     if (con1.node1 < con2.node1) {
    53.         return -1;
    54.     } else if (con1.node1 > con2.node1) {
    55.         return 1;
    56.     } else {
    57.         if (con1.node2 <= con2.node2) {
    58.             return -1;
    59.         } else {
    60.             return 1;
    61.         }
    62.     }
    63. }
    65. bool unionFind(Connection con, map<string, string>& parent) {
    66.     string p1 = find(con.node1, parent);
    67.     string p2 = find(con.node2, parent);
    68.     if (p1 == p2) {
    69.         return false;
    70.     }
    71.     parent[p1] = p2;
    72.     return true;
    73. }
    75. string find(string node, map<string, string>& parent) {
    76.     if (node == parent[node]) return node;
    77.     return find(parent[node], parent);
    78. }

  4. High Five

    1. class Result{
    2. public:
    3.     int id;
    4.     int value;
    5.     Result(int id, int value){
    6.         this->id = id;
    7.         this->value = value;
    8.     }
    9. };
    11. map<int, double> highFive(vector<Result> results) {
    12.     map<int, double> res;
    13.     map<int, priority_queue<int>> scoreTable;
    14.     for (Result rs: results) {
    15.         scoreTable[rs.id].push(rs.value);
    16.     }
    17.     for (map<int, priority_queue<int>>::iterator it = scoreTable.begin(); it != scoreTable.end(); it++) {
    18.         int sum = 0;
    19.         for (int i = 0; i < 5; i++) {
    20.             sum += it->second.top();
    21.             it->second.pop();
    22.         }
    23.         //注意是float!!!
    24.         res[it->first] = (float)sum / 5;
    25.     }
    26.     return res;
    27. }

  5. Maximum Subtree of Average

    1. class Node { //这个是题目给好的
    2. public:
    3.     int val;
    4.     vector<Node> children;
    5.     Node(int val){
    6.         this->val = val;
    7.         children = vector<Node>();
    8.     }
    9. };
    11. //自己创建的class 方便保存结果
    12. class sumCount {
    13. public:
    14.     int sum;
    15.     int count;
    16.     sumCount(int a = 0, int b = 0) {
    17.         sum = a;
    18.         count = b;
    19.     }
    20. };
    22. sumCount dfs(Node root, Node& res, float& aver);
    24. Node subtree(Node root) {
    25.     Node res(0);
    26.     float aver = 0;
    27.     dfs(root, res, aver);
    28.     return res;
    29. }
    32. sumCount dfs(Node root, Node& res, float& aver) {
    33.     sumCount sc(root.val, 1);
    34.     //如果是叶子节点 不能去替换res 和 aver!!!!!!!
    35.     if (root.children.size() == 0) {
    36.        return sc;
    37.     }
    38.     //做了两个事情! 1. dfs遍历孩子, 2. 计算当前root的sum, count
    39.     for (Node child: root.children) {
    40.         sumCount childSC = dfs(child, res, aver);
    41.         sc.sum += childSC.sum;
    42.         sc.count += childSC.count;
    43.     }
    44.     float curAver = (float)sc.sum / sc.count;
    45.     if (curAver > aver) {
    46.         aver = curAver;
    47.         res = root;
    48.     }
    49.     return sc;
    50. }

  6. Find K Nearest Point

    k <= 0 return new Point[0]是一个test case
    k > size算是返回原数组，但是里面的points要sort一边，距离最近的点是第一个，第二近的是 第二个and so on

    1. class point {
    2. public:
    3.     int x;
    4.     int y;
    5.     point(int x_value, int y_value):x(x_value), y(y_value) {};
    6. };
    8. float distance(const point& a, const point& b = {0, 0}) {
    9.     int dx = a.x - b.x;
    10.     int dy = a.y - b.y;
    11.     return sqrt(dx * dx + dy * dy);
    12. }
    14. bool comp(const point& a, const point& b) {
    15.     point origin(0, 0);
    16.     return distance(a, {0, 0}) < distance(b, {0, 0});
    17. }
    19. struct mycomp {
    20.     bool operator()(const point& a, const point& b) {
    21.         point origin(0, 0);
    22.         return distance(a, origin) < distance(b, origin);
    23.     }
    24. };
    26. vector<point> KNearestPoint(vector<point> points, point origin, int k) {
    27.     priority_queue<point, std::vector<point>, decltype(&comp)> pq(&comp);
    28.     //priority_queue<point, std::vector<point>, mycomp> pq;
    29.     for (point p : points) {
    30.         pq.push(p);
    31.         if (pq.size() > k) {
    32.             pq.pop();
    33.         }
    34.     }
    35.     vector<point> res;
    36.     while (!pq.empty()) {
    37.         res.push_back(pq.top());
    38.         pq.pop();
    39.     }
    40.     return res;
    41. }

  7. Longest Palindromic substring
    LeetCode

    1. string longestPalindrome(string s) {
    2.     int max = 0;
    3.     string res = "";
    4.     for (int i = 0; i < s.size(); i++) {
    5.         int left = i; 
    6.         int right = i;
    7.         while(left - 1 >= 0 && right + 1 < s.size() && s[left - 1] == s[right + 1]) {
    8.                 left--;
    9.                 right++;
    10.         }
    11.         if (right - left + 1 > max) {
    12.             max = right - left + 1;
    13.             res = s.substr(left, right - left + 1);
    14.         }
    15.         if (i + 1 < s.size() && s[i] == s[i + 1]) {
    16.             left = i;
    17.             right = i + 1;
    18.             while(left - 1 >= 0 && right + 1 < s.size() && s[left - 1] == s[right + 1]) {
    19.                     left--;
    20.                     right++;
    21.             }
    22.             if (right - left + 1 > max) {
    23.                 max = right - left + 1;
    24.                 res = s.substr(left, right - left + 1);
    25.             }
    26.         }
    27.     }
    28.     return res;
    29. }

  8. Overlap Rectangle

    1. //这个题目是左上角和右下角!!
    2. bool doOverlap(Point l1, Point r1, Point l2, Point r2)
    3. {
    4.     // If one rectangle is on left side of other
    5.     if (l1.x > r2.x || l2.x > r1.x)
    6.         return false;
    8.     // If one rectangle is above other
    9.     if (l1.y < r2.y || l2.y < r1.y)
    10.         return false;
    12.     return true;
    13. }
    15. //预处理, 不管是左上角+右下角 还是 左下角+右上角
    16. //都统一为左上角+右上角
    17. bool overlap(Point l1, Point r1, Point l2, Point r2) {
    18.     int a = min(l1.x, r1.x);
    19.     int b = max(l1.y, r1.y);
    20.     int c = max(l1.x, r1.x);
    21.     int d = min(l1.y, r1.y);
    23.     int e = min(l2.x, r2.x);
    24.     int f = max(l2.y, r2.y);
    25.     int g = max(l2.x, r2.x);
    26.     int h = min(l2.y, r2.y);
    28.     if (d > f || h > b) return false;
    29.     if (c < e || g < a) return false;
    30.     return true;
    31. }

    (LeetCode计算面积)[https://leetcode.com/problems/rectangle-area/]

    1. //!!注意这个题目给出的点是 左下角和右上角!!!! 而不是左上角和右下角
    2. int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
    3.     int area1 = (C - A) * (D - B);
    4.     int area2 = (G - E) * (H - F);
    5.     int left = max(A, E);
    6.     int right = min (C, G);
    7.     int bottom =  max(B, F);
    8.     int top = min(D, H);
    10.     int overlap = 0;
    11.     if (right > left && top > bottom)
    12.         overlap = (right - left) * (top - bottom);
    13.     return area1 + area2 - overlap;
    14. }

  9. Window Sum

    1. vector<int> windowSum(vector<int> vect, int k) {
    2.     vector<int> res;
    3.     if (vect.size() == 0 || k <= 0) return res;
    4.     int sum = 0;
    5.     for (int i = 0; i < k; i++) {
    6.         sum += vect[i];
    7.     }
    8.     res.push_back(sum);
    9.     for (int i = 0; i < vect.size() - k; i++) { //注意这里的个数, 前面以及把第一项加进去了!!  所以不是size - k + 1
    10.         sum = sum - vect[i] + vect[i + k];
    11.         res.push_back(sum);
    12.     }
    13.     return res;
    14. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注