[关闭]
@skysbjdy 2016-12-08T22:57:48.000000Z 字数 11969 阅读 3830

亚马逊2

Interview

Coding

  1. Right Rotation
    Example: waterbottle -> erbottlewat

    1. bool rightRotation(string s1, string s2) {
    2.     if (s1.size() == 0 || s1.size() != s2.size()) {
    3.         return false;
    4.     }
    5.     s1 = s1 + s1;
    6.     return s1.find_first_of(s2) == string::npos ? false : true;
    7. }

  2. Gray Code 判断byte1和byte2是不是相邻的Gray Code
    两个bytes 异或, 然后检查是不是只有一个1!!

    1. bool gray(int byte1, int byte2) {
    2.     int temp = byte1 xor byte2;
    3.     int count = 0;
    4.     while(temp != 0) {
    5.         temp = temp & (temp - 1);
    6.         count++;
    7.     }
    8.     return count == 1 ? true : false;
    9. }

  3. Remove Vowel 去元音

    1. string vowel(string s) {
    2.     string temp = "aeiouAEIOU";
    3.     string res = "";
    4.     for(int i = 0; i < s.size(); i++) {
    5.         if (temp.find_first_of(s[i]) != string::npos) continue;
    6.         res = res + s[i];
    7.     }
    8.     return res;
    9. }

  4. Valid Parenthesis 检验括号
    一个str,里面只有 '('和‘)’,让你数valid pairs一共有多少,如果不是valid就返回-1. (判断是不是valid的parenthesis string，不是的话返回-1，是的话返回valid pair个数，即String.length() / 2 )

    1. int parentheses(string s) {
    2.     stack<char> stc;
    3.     for(char c: s) {
    4.         if (c == '(') {
    5.             stc.push(c);
    6.         } else {
    7.             if (stc.empty()) return -1; //invalid
    8.             else stc.pop();
    9.         }
    10.     }
    11.     return stc.empty() ? s.size() / 2 : -1;
    12. }

  5. Longest Palindromic substring

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

  6. Merge Two Sorted List

    1. ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    2.     ListNode dummy(0);
    3.     ListNode* cur = &dummy;
    4.     while (l1 != NULL && l2 != NULL) {
    5.         if (l1->val < l2->val) {
    6.             cur->next = l1;
    7.             l1 = l1->next;
    8.             cur = cur->next;
    9.         } else {
    10.             cur->next = l2;
    11.             l2 = l2->next;
    12.             cur = cur->next;
    13.         }
    14.     }
    15.     cur->next = l1 != NULL ? l1 : l2;
    16.     return dummy.next;
    17. }

  7. Reverse Second Half of Linked List
    [] -> []
    [1] -> [1]
    [1,2] -> [1,2]
    [1,2,3] -> [1,2,3]
    [1,2,3,4] -> [1,2,4,3]
    [1,2,3,4,5] -> [1,2,3,5,4]

    1. ListNode* reverseList(ListNode* head) {
    2.     if (head == NULL || head->next == NULL) return head;
    3.     ListNode* slow = head;
    4.     ListNode* fast = head;
    5.     while(fast->next && fast->next->next) {
    6.         fast = fast->next->next;
    7.         slow = slow->next;
    8.     }
    9.     ListNode* cur = slow->next;
    10.     ListNode* pre = NULL;
    11.     while (cur) {
    12.         ListNode* nxt = cur->next;
    13.         cur->next = pre;
    14.         pre = cur;
    15.         cur = nxt;
    16.     }
    17.     slow->next = pre;
    18.     return head;
    19. }

  8. SubTree
    LeetCode

    1. bool isSubtree(TreeNode *T1, TreeNode *T2) {
    2.     // write your code here
    3.     if (T2 == NULL) return true;
    4.     if (T1 == NULL) return false;
    5.     return (isSame(T1, T2) || isSubtree(T1->left, T2) || isSubtree(T1->right, T2));
    6. }
    8. bool isSame(TreeNode* t1, TreeNode* t2) {
    9.     if (t1 == NULL && t2 == NULL) return true;
    10.     if (t1 == NULL || t2 == NULL) return false;
    11.     if (t1->val == t2->val) {
    12.         return isSame(t1->left, t2->left) && isSame(t1->right, t2->right);
    13.     } else {
    14.         return false;
    15.     }
    16. }

  9. Two Sum

    1. vector<int> twoSum(vector<int>& nums, int target) {
    2.     unordered_map<int, int> map;
    3.     vector<int> res;
    4.     for(int i = 0; i < nums.size(); i++) {
    5.         if (map.find(target - nums[i]) != map.end()) {
    6.             res.push_back(map[target - nums[i]]);
    7.             res.push_back(i);
    8.             break;
    9.         }
    10.         else {
    11.             map[nums[i]] = i;
    12.         }
    13.     }
    14.     return res;
    15. }

  10. Find K Nearest Point

    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.     //priority_queue<point, std::vector<point>, bool (&)(point a, point b, point origin)> pq;
    30.     for (point p : points) {
    31.         pq.push(p);
    32.         if (pq.size() > k) {
    33.             pq.pop();
    34.         }
    35.     }
    36.     vector<point> res;
    37.     while (!pq.empty()) {
    38.         res.push_back(pq.top());
    39.         pq.pop();
    40.     }
    41.     return res;
    42. }

  11. 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. }

    (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. }

  12. 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.     }

  13. GCD Greatest Common Divisor

    1. int solution(vector<int> array) {
    2.     if (array.size() == 0) return 0;
    3.     int res = array[0];
    4.     for (int i = 1; i < array.size(); i++) {
    5.         res = gcd(res, array[i]);
    6.     }
    7.     return res;
    8. }
    10. int gcd(int a, int b) {
    11.     a = a < 0 ? -a : a;
    12.     b = b < 0 ? -b : b;
    13.     if (a == 0 || b == 0) return a + b;
    14.     while (a != 0 && b != 0) {
    15.         if (a < b) swap(a, b); //make sure a is larger than b
    16.         int temp = a % b;
    17.         a = b;
    18.         b = temp;
    19.     }
    20.     return a + b;
    21. }

  14. LRU Cache count miss

    1. int lruMiss(vector<int> nums, int capacity) {
    2.     list<int> ls;
    3.     int cnt = 0;
    4.     for (int num : nums) {
    5.         if(find(ls.begin(), ls.end(), num) != ls.end()) { //hit
    6.             ls.remove(num);
    7.             ls.push_back(num);
    8.         } else { //cache miss
    9.             cnt++;
    10.             if (ls.size() >= capacity) {
    11.                 ls.pop_front();
    12.             }
    13.             ls.push_back(num);
    14.         }
    15.     }
    16.     return cnt;
    17. }

    Leetcode

  15. Round Robin

    1. class process {
    2. public:
    3.     int arrTime;
    4.     int exeTime;
    5.     process(int arr, int exe) {
    6.         arrTime = arr;
    7.         exeTime = exe;
    8.     }
    9. };
    11. float roundRobin(vector<int> Atime, vector<int> Etime, int q) {
    12.     if (Atime.size() == 0 || Etime.size() == 0 || Atime.size() != Etime.size()) return 0.0;
    13.     queue<process> jobs;
    14.     int index = 0;
    15.     int curTime = 0;
    16.     int waitTime = 0;
    17.     while (!jobs.empty() || index < Atime.size()) {
    18.         if (!jobs.empty()) {
    19.             process curJob = jobs.front();
    20.             jobs.pop();
    21.             waitTime += curTime - curJob.arrTime;
    22.             curTime += curJob.exeTime < q ? curJob.exeTime : q;
    23.             //加入所有到达的job
    24.             for (; index < Atime.size() && Atime[index] <= curTime; index++) {
    25.                 jobs.push(process(Atime[index], Etime[index]));
    26.             }
    27.             //注意顺序!! 最后把没有执行完的当前任务放在队列最后面!!!
    28.             if (curJob.exeTime > q) {
    29.                 jobs.push(process(curTime, curJob.exeTime - q));
    30.             }
    31.         } else {
    32.             //只加入第一个 没有for循环
    33.             jobs.push(process(Atime[index], Etime[index]));
    34.             curTime = Atime[index]; //设置时间
    35.             index++;
    36.         }
    37.     }
    38.     return (float)waitTime / Atime.size();
    39. }

  16. Rotation Matrix

    1. vector<vector<int>> rotation(vector<vector<int>> matrix, int flag) {
    2.     int m = matrix.size();
    3.     if (m == 0) return matrix;
    4.     int n = matrix[0].size();
    5.     vector<vector<int>> res(n, vector<int>(m, 1));
    6.     for (int i = 0; i < m; i++) {
    7.         for (int j = 0; j < n; j++) {
    8.             res[j][i] = matrix[i][j];
    9.         }
    10.     }
    12.     if (flag == 0) { // turn right -> left right flip
    13.         for (int i = 0; i < n; i++) {
    14.             for (int j = 0; j < m / 2; j++) {
    15.                 swap(res[i][j], res[i][m - 1 - j]); //注意减一
    16.             }
    17.         }
    18.     } else { //turn left -> upside down flip
    19.         for (int i = 0; i < m; i++) {
    20.             for (int j = 0; j < n / 2; j++) {
    21.                 swap(res[j][i], res[n - 1 - j][i]); //注意减一, i j的位置是颠倒的
    22.             }
    23.         }
    24.     }
    25.     return res;
    26. }

  17. Insert into cycle linked list

    1. ListNode Solution(ListNode head, int val) {
    2.     if (head == null) {
    3.         ListNode rvalue = new ListNode(val);
    4.         rvalue.next = rvalue;  //自己跟自己形成环
    5.         eturn rvalue;
    6.     }
    8.     ListNode cur = head;
    10.     do {
    11.         //一般情况: 直接找到正确的位子
    12.         if (val <= cur.next.val && val >= cur.val) break;
    13.         //特殊情况: 正好在首尾连接处
    14.         if (cur.val > cur.next.val && (val < cur.next.val || val > cur.val)) break;
    15.             cur = cur.next;
    16.     } while (cur != head);
    18.     ListNode newNode = new ListNode(val);
    19.     newNode.next = cur.next;
    20.     cur.next = newNode;
    21.     return newNode;
    22. }

  18. Loop in linked list

    1. ListNode *detectCycle(ListNode *head) {
    2.     if (head == NULL || head->next == NULL) return NULL;
    3.     ListNode* slow = head->next;
    4.     ListNode* fast = head->next->next;
    5.     while (slow != fast && fast) {
    6.         slow = slow->next;
    7.         fast = fast->next;
    8.         if (fast) fast = fast->next;
    9.     }
    10.     if (fast == NULL) return NULL;
    11.     slow = head;
    12.     while (slow != fast) {
    13.         slow = slow->next;
    14.         fast = fast->next;
    15.     }
    16.     return fast;
    17. }

  19. Round Robin Shortest First

    1. class Process {
    2. public:
    3.     int arrTime;
    4.     int exeTime;
    5.     Process(int aTime, int eTime) {
    6.         arrTime = aTime;
    7.         exeTime = eTime;
    8.     }
    9. };
    11. bool comp(Process a, Process b) {
    12.     if (a.exeTime == b.exeTime) return a.arrTime > b.arrTime;
    13.     return a.exeTime > b.exeTime;
    14. }
    16. float roundRobin(vector<int> aTime, vector<int> eTime) {
    17.     if (aTime.size() == 0 || eTime.size() == 0 || aTime.size() != eTime.size()) return 0.0;
    18.     //pq comp的写法 取函数地址, 而且声明的时候要传参数!!!
    19.     priority_queue<Process, vector<Process>, decltype(&comp)> jobs(&comp);
    20.     int index = 0;
    21.     int curTime = aTime[0];
    22.     int waitTime = 0;
    23.     while (index < aTime.size() || (!jobs.empty())) {
    24.         if (!jobs.empty()) {
    25.             Process curJob = jobs.top();
    26.             jobs.pop();
    27.             waitTime += curTime - curJob.arrTime;
    28.             curTime += curJob.exeTime;
    29.         } else {
    30.             for (; index < aTime.size() && aTime[index] <= curTime; index++) {
    31.                 jobs.push(Process(aTime[index], eTime[index]));
    32.             }
    33.         }
    34.     }
    35.     return (float) waitTime / aTime.size();
    36. }

  20. Binary Search Tree Minimum Sum From Root to Leaf

    1. int minSum(TreeNode* root) {
    2.     if (root == NULL) return 0;
    3.     if (root->left == NULL && root->right == NULL) return root->val;
    4.     if (root->left != NULL && root->right == NULL) {
    5.         return root->val + minSum(root->left);
    6.     } else if (root->left == NULL && root->right != NULL) {
    7.         return root->val + minSum(root->right);
    8.     } else {
    9.         return root->val + min(minSum(root->left), minSum(root->right));
    10.     }
    11. }

  21. Day change(cell growth)

    1. vector<int> cellGrowth(vector<int> cells, int n) {
    2.     int len = cells.size();
    3.     cells.insert(cells.begin(), 0);
    4.     cells.push_back(0);
    5.     for (int i = 0; i < n; i++) {
    6.         int pre = 0;
    7.         for (int j = 1; j <= len; j++) {
    8.             int temp = cells[j];
    9.             cells[j] = pre == cells[j + 1] ? 0 : 1;
    10.             pre = temp;
    11.         }
    12.     }
    13.     cells.erase(cells.begin());
    14.     cells.pop_back();
    15.     for (int cell : cells) {
    16.         cout << cell << endl;
    17.     }
    18.     return cells;
    19. }

  22. Maze

    1. bool mazePath(vector<vector<int>> maze) {
    2.     int m = maze.size();
    3.     if (m == 0) return true;
    4.     int n = maze[0].size();
    5.     if (maze[0][0] == 0) return false; //0 means block
    6.     if (maze[0][0] == 9) return true;  //corner case
    7.     vector<int> dx = {0, 1, 0, -1};
    8.     vector<int> dy = {1, 0, -1, 0};
    9.     queue<pair<int, int>> q;
    10.     q.push({0, 0});
    11.     while (!q.empty()) {
    12.         int x = q.front().first;
    13.         int y = q.front().second;
    14.         q.pop();
    15.         maze[x][y] = -1;
    16.         for (int index = 0; index < 4; index++) {
    17.             int i = x + dx[index];
    18.             int j = y + dy[index];
    19.             if (i >= 0 && i < m && j >= 0 && j < n) {
    20.                 if (maze[i][j] == 9) return true; //check if it is the end
    21.                 if (maze[i][j] == 1) q.push({i, j});
    22.             }
    23.         }
    24.     }
    25.     return false;
    26. }

  23. Min Window
    LeetCode

    1. vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    2.     deque<int> q;
    3.     vector<int> res;
    4.     for(int i = 0; i < nums.size(); i++) {
    5.         while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back(); //q永远保持降序
    6.         q.push_back(i);
    7.         if (i - q.front() + 1 > k) q.pop_front();//确保他还在范围内!!!
    8.         if(i >= k - 1) res.push_back(nums[q.front()]);
    9.     }
    10.     return res;
    11. }

  24. Four Integer

    1. int comp(const void* a, const void* b) {
    2.     return (*(int*)a) - (*(int*)b);
    3. }
    5. vector<int> fourInt(int a, int b, int c, int d) {
    6.     vector<int> res = {a, b, c, d};
    7.     qsort(&res[0], res.size(), sizeof(int), comp);
    8.     swap(res[0], res[1]);
    9.     swap(res[2], res[3]);
    10.     swap(res[0], res[3]);
    11.     return res;
    12. }

  25. Arithmetic Sequence
    给一个数组，返回可能的等差数列个数

    1. int numberOfArithmeticSlices(vector<int>& A) {
    2.     if (A.size() < 3) return 0;
    3.     int diff = 0;
    4.     int start = 0;
    5.     int cnt = 0;
    6.     int res = 0;
    7.     for (int i = 1; i < A.size(); i++) {
    8.         int curDiff = A[i] - A[i - 1];
    9.         if (curDiff == diff) {
    10.             cnt += (i - start - 1) > 0 ? i - start - 1 : 0; //注意 为什么是加上这个多个??
    11.         } else {
    12.             start = i - 1;
    13.             diff = A[i] - A[i - 1];
    14.             res += cnt;
    15.             cnt = 0;
    16.         }
    17.     }
    18.     res += cnt;
    19.     return res;
    20. }

  26. Tree Amplitude

    1. int TreeAmplitude(TreeNode* root) {
    2.     if (root == NULL) return 0;
    3.     return helper(root, root->val, root->val);
    4. }
    6. int helper(TreeNode* root, int& max, int& min) {
    7.     if (root == NULL) return max - min;
    8.     if (root->val < min) min = root->val;
    9.     if (root->val > max) max = root->val;
    11.     return max(helper(root->left, max, min), helper(root->right, max, min));
    12. }

  27. Maximum Minimum Path

    1. int mmPath(vector<vector<int>>& matrix) {
    2.     if (matrix.size() == 0) return 0;
    3.     int max = INT_MIN;
    4.     int min = INT_MAX;
    5.     helper(matrix, max, min, 0, 0);
    6.     return max;
    7. }
    9. void helper(vector<vector<int>>& matrix, int& max, int min, int i, int j) {
    10.     if (i >= matrix.size() || j >= matrix[0].size()) {
    11.         return;
    12.     }
    13.     if (i == matrix.size() - 1 && j == matrix[0].size() - 1) {
    14.         min = min < matrix[i][j] ? min : matrix[i][j];
    15.         max = max > min ? max : min;
    16.         return;
    17.     }
    18.     min = min < matrix[i][j] ? min : matrix[i][j];
    19.     helper(matrix, max, min, i + 1, j);
    20.     helper(matrix, max, min, i, j + 1);
    21.     return;
    22. }

  28. Search in 2D matrix

    1. bool searchMatrix(vector<vector<int>>& matrix, int target) {
    2.     int m = matrix.size();
    3.     if (m == 0) return false;
    4.     int n = matrix[0].size();
    5.     int i = 0;
    6.     int j = m * n - 1;
    7.     while (i <= j) { //考虑最后一个步  
    8.         int mid = i + (j - i) / 2;
    9.         if (matrix[mid / n][ mid % n] == target) return true;
    10.         if (matrix[mid / n][mid % n] < target) {
    11.             i = mid + 1;
    12.         } else {
    13.             j = mid - 1;
    14.         }
    15.     }
    16.     return false;
    17. }

  29. Search in 2D matrix II

    1. bool searchMatrix(vector<vector<int>>& matrix, int target) {
    2.     int m = matrix.size();
    3.     if (m == 0) return false;
    4.     int n = matrix[0].size();
    5.     int i = 0;
    6.     int j = n - 1; //从右上角开始
    7.     while (i < m && j >= 0) {
    8.         if (matrix[i][j] == target) return true;
    9.         if (matrix[i][j] < target) {
    10.             i++;
    11.         } else {
    12.             j--;
    13.         }
    14.     }
    15.     return false;
    16. }

  30. Close Two Sum

    1. import java.util.Arrays;
    2. public class Main {
    3.     public static void main(String[] args) {
    4.         double capacity = 35;
    5.         double[] weights = {10,24,30,9,19,23,7};
    6.         double maxWei = 0;
    7.         double maxSmall = 0;
    8.         double maxLarge = 0;
    10.         Arrays.sort(weights);
    11.         int i = 0;
    12.         int j = weights.length-1;
    13.         while (i < j) {
    14.             if ((weights[i] + weights[j]) < capacity) {
    15.                 if (weights[i] + weights[j] > maxWei) {
    16.                     maxWei = weights[i] + weights[j];
    17.                     maxSmall = weights[i];
    18.                     maxLarge = weights[j];
    19.                 }
    20.                 i += 1;
    21.             } else if (weights[i] + weights[j] == capacity) {
    22.                 maxSmall = weights[i];
    23.                 maxLarge = weights[j];
    24.                 maxWei = capacity;
    25.                 break;
    26.             } else {
    27.                 j -= 1;
    28.             }
    29.         }
    30.         System.out.println("The maximum weights is" + maxWei + ", the index are" + maxSmall + "and" + maxLarge);
    31.     }
    32. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注