Posted on

刷题刷的什么能力？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=510527&page=1#pid6345290
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=510527&page=2#pid6348448
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=510527&page=3#pid6354044

900+刷题经验贴
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=469710

new grad 刷刷刷题怎么刷（真正的菜鸡变正常人）
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=441415

投出简历之前尽量做好算法数据结构方面的积累，2月／8月联系内推投出简历，2-4月／8-10月面试。越早面试head count越充足，通过标准有可能逐渐提高。

面试不要害怕向面试官索取hint，可以说明当前卡在哪里，出难题有可能就是来考察实际工作中遇到卡壳情况如何有效沟通解决。

面试解题框架：

  1. 拿到题目后跟面试官确认自己对题意的理解，问清数据范围， 考虑corner case
  2. 思考， 提出并描述解法， 分析复杂度， 与面试官讨论
  3. 征得面试官同意后， 使用有意义的变量名，清晰的代码结构， bug free实现解法
  4. 跟面试官讨论测试样例， 并测试。 尝试进一步优化解法

Posted on

Morris Traversal for tree traversal. Time complexity O(n), Space complexity O(1)
Data structure definition.

1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

Preorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        while (p) {
            if (!p->left) {
                ans.emplace_back(p->val);
                p = p->right;
            } else {
                auto prev = p->left;
                while (prev->right and prev->right != p) {
                    prev = prev->right;
                }
                if (!prev->right) {
                    ans.emplace_back(p->val);
                    prev->right = p;
                    p = p->left;
                } else {
                    prev->right = nullptr;
                    p = p->right;
                }
            }
        }
        return ans;
    }
};

Inorder (The difference between Inorder and Preorder is only one line)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        while (p) {
            if (!p->left) {
                ans.emplace_back(p->val);
                p = p->right;
            } else {
                auto prev = p->left;
                while (prev->right and prev->right != p) {
                    prev = prev->right;
                }
                if (!prev->right) {
                    prev->right = p;
                    p = p->left;
                } else {
                    ans.emplace_back(p->val);   \\ diff
                    prev->right = nullptr;
                    p = p->right;
                }
            }
        }
        return ans;
    }
};

Postorder (The visiting order is a mirror reflection of Preorder, and the results should be reversed)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        while (p) {
            if (!p->right) {
                ans.insert(ans.begin(), p->val);
                p = p->left;
            } else {
                auto post = p->right;
                while (post->left and post->left != p) {
                    post = post->left;
                }
                if (!post->left) {
                    ans.insert(ans.begin(), p->val);
                    post->left = p;
                    p = p->right;
                } else {
                    post->left = nullptr;
                    p = p->left;
                }
            }
        }
        return ans;
    }
};

Posted on

#
We use two pointers to find the mid of linked list named as slow = head, fast = head, given head of the linkedList, now conclude the condition of the while loop

  • ceil mid
    fast and fast->next

  • floor mid
    fast->next and fast->next->next

Posted on

Title: R-FCN: Object Detection via Region-based Fully Convolutional Networks

Contribution:

  • introduce the ROI pooling layer at proper location for share computation
  • position sensitive score maps to alleviate the dilemma translation invariance for cls vs translation variance for det
  • ps roi pooling: (precondition: project rois to feature maps by using conv layer with k^2 * (C + 1) channels where k is the number each ROI divided by and C is the number of classes) abstract information in each bin then all k^2 bins vote for a C+1 channel vector

Experiment:

  • used ResNet-101 as backbone network followed by k^2(C+1) channel conv layer
  • reduce stride 32->16 pixel, used dilated conv on conv5
  • 83.6% mAP PASCAL VOC 2007, 82.0% 2012, test-time 170ms per image

Future works:

  • apply extensions of FCNs

Posted on

Title: Light-Head R-CNN: In Defense of Two-Stage Object Detector

Contribution:

  • proposed a 2-stage detector with good accuracy and promising speed compare with single-stage detector
  • investigate the problems with Faster-RCNN (global avg pooling harmful for spatial loc with out sharing compution) & RFCN (with a large score map for ROI pooling which is costly)
  • proposed thin feature maps for generating small channel ROI feature maps, improving accuracy, save mem/ computation
  • detailed hyper-param setting & experiments give strong results, also show techs which improved mAP

Experiment:

  • evaluated on COCO
  • adopt dilated conv & OHEM
  • R-FCN as baseline
  • with ResNet as backbone, achieve 41.5 mmAP
  • with Xception achieve 30.7 mmAP, 102 FPS

Posted on

Title: Mask R-CNN

Contribution:

  • extend Faster R-CNN by adding a mask branch, which could be used for seg and also improves accuracy
    • the mask branch is a small FCN applied to each ROI
    • a mask encodes an input object’s spatial layout
    • extracting the spatial structure of masks can be addressed naturally by the pixel-to-pixel correspondence provided by convolutions
    • the fully conv needs fewer params and is more accurate
  • illustrates that decouple mask and class prediction is essential, so that the loss of the mask branch is the avg binary cross-entropy loss
  • proposed ROI Align for better predicting pixel-accurate masks
    • avoid quantization of the boundaries or bins
    • insensitive to max/avg pool
  • shows ablation experiments and analysis of improvements

Posted on

Title: Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks

Contribution:

  • (motivation: break the bottleneck in 2 stage detection which is the generating procedure of proposals)
  • propose Region Prososal Networks (RPN) for generating proposals who shares conv layers with afterward detection networks
    • RPN: several conv layers - regress region bounds and objectness scores at each location on a grid
    • used nms on proposal regions based on cls scores
  • introduce anchor boxes as references at multi-scales/-aspect ratios
    • could be thought as pyramid of filters
    • key component for effectively sharing features
  • propose an alternating training scheme for the 2 stage detection
  • evaluated with different param/structure setting comprehensively (PASCAL VOC/ COCO)

Pros: end-to-end, provided code & detailed hyper-parameters for reimplement

Posted on

Title: Fully Convolutional Networks for Semantic Segmentation

Contribution:

  • use fully convolution to get heatmap as output which can provide pixelwise information
  • use skip structure to fuse low level precision feature with high level coarse spatial (semantic) feature
  • investigated shift-and-stitch (deprecated), patchwise training (deprecated) in training phase
  • upsampling as backwards strided convolution, effective for learning dense prediction

Experiment:

  • used VGG16 as backbone network
  • measured with: pixel accuracy, mean accuracy, mean Intersection over Union, frequency weighted IU, time of inference
  • datasets: PASCAL VOC, NYUDv2, SIFT Flow, achieve the state-of-the-art (contrasted to r-cnn, SDS), also with faster inference speed

Pros: end-to-end, could make use of classification nets with little modification on architecture

Future work:

  • some more dedicated way instead of bilinear upsampling
  • why add depth information improved insignificant?