# 方晨（Zergling）info2021-homework4
## 符合自身規劃的工作
### Google
Software Engineer, Computer Vision, Pixel Camera
- https://careers.google.com/jobs/results/122520332381627078-software-engineer-computer-vision-pixel-camera/?distance=50&q=image%20processing
### Nvidia
System Software Engineer - Autonomous Vehicles
- https://nvidia.wd5.myworkdayjobs.com/en-US/NVIDIAExternalCareerSite/job/China-Shanghai/System-Software-Engineer---Autonomous-Vehicles_JR1945947

## 需要能力以及自身專業匹配度
:::info
個人背景
- 四中電資相關研究所畢業
- 碩士論文結合深度學習影像分割和辨識，並於國際期刊發表
- 曾擔任嵌入式系統及 FPGA 課程助教
- 曾於新創公司擔任軟體工程師，進行影像變形校正之評估
- 個人專題：
1. 影像處理相關
* [SRCNN-cpp]([SRCNN-cpp](https://github.com/Cuda-Chen/SRCNN-cpp))
* [vface-server-cpp](https://github.com/Cuda-Chen/vface-server-cpp)
* [SLIC.jl](https://github.com/Cuda-Chen/SLIC.jl)
2. 機器學習相關
* [fish-yolo-grabcut](https://github.com/Cuda-Chen/fish-yolo-grabcut)
* [SRCNN-cpp](https://github.com/Cuda-Chen/SRCNN-cpp)
:::
### Google
Minimum qualifications:
* Bachelor's degree in Computer Science, a related technical field, or equivalent practical experience.
> 完全契合
* 2 years of work or educational experience in Machine Learning or Artificial Intelligence.
> 目前沒有，不過我認為可用發表論文、研究所及個人專題。
* 1 year of relevant experience, including software development.
> 會使用研究所及個人專題來頂。
* Experience with one or more general purpose programming languages (Java, C/C++, Python, etc.).
> 我的主力語言是 C 和 Python，OK der。

Preferred qualifications:
* Master's degree or equivalent practical experience in electrical engineering, computer science, or related field.
> 完全契合。
* Experience with Machine Learning in the context of image processing.
> 碩士論文，沒問題。
* Experience with Software/Hardware ISP pipeline optimization.
> 完全沒有。
* Experience with building infrastructure and tools for adjusting and rating images (i.e. web front-end development).
> 之前工作的資料分享平台。
### Nvidia
What we need to see:
* MS or PhD in EE/CS or closely related field (or additional equivalent experience) with 3+ year of relevant work and lab experience
> 研究所專題、個人專題、實習經驗來頂。
* Deep understanding of programming languages in C, C++ and Python
> 主力程式語言是 C 和 Python
* Familiar with source control tools (git, Perforce, etc.)
> 我平常用 Git
* Experienced in developing system software mostly in user space but also feel no big deal in digging deep into kernel space and even low-level hardware
> 拿個人專題來說。
* You know too much about system programming, threading, mutex, synchronization, communication, and parallel computing to build highly scalable and efficient applications
> 拿個人專題。
* You are more than familiar with underlying hardware architecture for CPU/GPU and memory, and understand performance from bottom up
> 拿個人專題。
* Prior experience working in the following areas: Kernel development, Autonomous Vehicles, Robotics, Self-Driving-Cars, GPU technology, Computer Vision, Deep Learning
> 拿個人專題和研究所論文。
* Display outstanding communication and collaboration skills, as we work as a tightly-knit team, always discussing and learning from each other and driving things forward and making solid progress
> Behavior questions response needs more practicing.

Ways to stand out from the crowd:

* Deep understanding of system architecture, CPU/GPU/Memory/Storage, everything related to performance optimization
> 拿個人專題。
* Solid working experience in kernel developing, Linux/QNX, and all too familiar with OS scheduling, event handling, real-time requirements
> 完全沒有。
* Experience with Computer Vision, Machine Learning, Deep Learning or other Artificial Intelligence paradigms
> 個人專題、研究所論文。
* Experience in Automotive Vehicle or Robotic System Building
> 完全沒有。
## 面試題目
### [Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
Given an array of integers `nums` contain `n + 1` integers where each integer is in range `[1, n]`.
There is only **one repeated number** in `nums`, return *this repeated number*.
You must solve the problem **without** modifying the array `nums` and uses only constant extra space.
### [Strange Printer](https://leetcode.com/problems/strange-printer/)
There is a strange pointer which can only do two operations:
* The printer can only print a sequence of **the same character** each time.
* At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string `s`, return *the minimum number of turns the printer needed to print it*.
### [Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/)
Given a 2D matrix `matrix`, handle multiple queries of the following type:

Calculate the sum of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.
Implement the NumMatrix class:
* `NumMatrix(int[][] matrix)` Initializes the object with the integer matrix `matrix`.
* `int sumRegion(int row1, int col1, int row2, int col2)` Returns the sum of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.
## 面試題目擬答
### [Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
We can use bit operation to find the repeated number.
* `cnt1` stores the length of `nums`
* `cnt2` stores the count of `nums[k]` in certain bit position
* if `cnt2` is bigger than `cnt1`, it means the bit position has the repeat numbers. We add the `bit` to `ans`.
* At last, `ans` will restore the repeated number.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int ans = 0, n = nums.size();
        for(int i = 0; i < 32; i++) {
            int bit = (1 << i), cnt1 = 0, cnt2 = 0;
            for(int k = 0; k < n; k++) {
                if((k & bit) > 0) ++cnt1;
                if((nums[k] & bit) > 0) ++cnt2;
            }
            if(cnt2 > cnt1) ans += bit;
        }
        return ans;
    }
};

### [Strange Printer](https://leetcode.com/problems/strange-printer/)
For s = `a`, it is obiviously that we need one operation (print character `a`).
For s = `aaabbb`, we first print `aaaaaa` then print `bbb` to overwrite the latter three `a`, therefore two operations.
For s = `aba`, we first print `aaa` then print `b` in the second position, there tow oerations.

As such, we use $s$ to denote string S, $dp[i][j]$ to denote the minimum operations if we want to print the string from position $i$ to position $j$.
We can conclude the following equations:
1. $dp[i][j] = 0$ if $i > j$.
2. $dp[i][j] = dp[i + 1][j] + 1$ if $i = j$
3. $dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j])$ for $s[k] = s[i]$ and $i < k \le j$

DP (bottom-up)

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                dp[i][j] = (i == j) ? 1 : (1 + dp[i + 1][j]);
                for(int k = i + 1; k <= j; k++) {
                    if(s[k] == s[i])
                        dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
};

DP (top-down)

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        dp = vector<vector<int>>(n, vector<int>(n));
        return helper(s, 0, n - 1);
    }
    
private:
    vector<vector<int>> dp;
    
    int helper(string &s, int i, int j) {
        if(i > j) return 0;
        if(dp[i][j]) return dp[i][j];
        
        dp[i][j] = 1 + helper(s, i + 1, j);
        for(int k = i + 1; k <= j; k++) {
            if(s[k] == s[i])
                dp[i][j] = min(dp[i][j], helper(s, i + 1, k - 1) + helper(s, k, j));
        }
        
        return dp[i][j];
    }
};

### [Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/)
As such, we can use a 2D array $dp[i][j]$ to represent the range sum, where $dp[i][j]$ denotes the sum from $(0, 0)$ to $(i, j)$.
Also we can get the following formula:
$$
dp[i][j] = matrix[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
$$

For the range sum from $(a, b)$ to $(c, d)$:
$$
sumRegion(a, b, c, d) = dp[c + 1][d + 1] - dp[a][d + 1] - dp[c + 1][b] + dp[a][b]
$$

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        dp = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = matrix[i - 1][j - 1] +
                    dp[i - 1][j] +
                    dp[i][j - 1] -
                    dp[i - 1][j - 1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] -
            dp[row1][col2 + 1] -
            dp[row2 + 1][col1] +
            dp[row1][col1];
    }
    
private:
    vector<vector<int>> dp;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */