# info2021-homework4
> 作者: 滿天星 Stars

### Google
[Software Engineer, Computer Vision, Pixel Camera](https://careers.google.com/jobs/results/109652188784927430-machine-learning-software-engineer-cloud-retail-industry-solutions/?distance=50&q=Software%20Engineer,%20Computer%20Vision)

Minimum qualifications:

* Experience programming in one of more of the following languages: C++, Java, and other object oriented languages.
> 會寫C++
* Experience in developing machine learning (ML) solutions, and in software development.
> 目前有用過一些 ML 得東西，但要 develop 可能到碩班比較有機會
* Experience in statistics and data analysis.
> 統計、資料分析這學期的專案碰過一些
* Ability to speak and write in English fluently.
> 英語能力不是很好，這方面希望在進碩班前能有所進步

<br />

Preferred qualifications:

* Master's degree in Machine Learning or equivalent industry experience.
> 符合
* Experience with TensorFlow.
> 目前有使用過 pyTorch, TensorFlow 則還沒
* Experience in developing highly available cloud services.
> 沒有這方面的經驗
* Experience in computer science, data structures, algorithms, and software design.
> 碩班應該會一直接觸到

<br />

### Nvidia
[System Software Engineer - Autonomous Vehicles](https://nvidia.wd5.myworkdayjobs.com/en-US/NVIDIAExternalCareerSite/job/China-Shanghai/System-Software-Engineer---Autonomous-Vehicles_JR1937904)

What we need to see:

* PhD or MS in EE/CS or closely related field (or equivalent experience)
> 符合
* Possess a deep understanding of programming languages in C, C++ and Python.
> 會寫 C, C++, Python，若要到 deep understanding 還需要加強
* 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
> 會寫 verilog，但目前還沒有動過 kernel 相關，希望之後可以透過修課補足相關經驗
* Deep understanding of system programming, threading, mutex, synchronization, communication, and parallel computing to build highly scalable and efficient applications
> 目前沒有相關經驗，希望之後可以透過修課補足相關經驗
* More than familiar with underlying hardware architecture for CPU/GPU and memory, and understand performance from bottom up
> 應該算是 familiar
* Prior experience working in the following areas: Kernel development, Autonomous Vehicles, Robotics, Self-Driving-Cars, GPU technology, Computer Vision, Deep Learning
> 碩班會接觸到自駕車、Robotic, CV, DL 相關應用，但 kernel development 則還沒有相關經驗
* 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
> 可以

<br />

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.
> 沒有這部分的經驗，希望之後可以透過修課補足相關經驗
* Background with Computer Vision, Machine Learning, Deep Learning or other Artificial Intelligence paradigms
> 碩班會接觸到 CV, ML, DL 等
* Experience in Automotive Vehicle or Robotic System Building
> 碩班正好聚焦在這些

<br />

### 面試題目

1.Efficiently implement 3 stacks in a single array.
> One of the stack grow from the left, another stack grow from right, and the other grow from middle. If the middle one reach the right one, left shift it.

2.Given an array of integers which is circularly sorted, how do you find a given integer.
> binary search

3.Write a program to find depth of binary search tree without using recursion.
> Use iterative way to traverse a tree and use a variable to store the max depth.

4.Find the maximum rectangle (in terms of area) under a histogram in linear time.
> use two pointer

def maxArea(self, height: List[int]) -> int:
    length = len(height)
    maxi = 0
    l = 0
    r = length - 1
    while(r > l):
        maxi = max(maxi, min(height[r], height[l]) * (r - l))
        if (height[r] > height[l]):
            l += 1
        else:
            r -= 1
    return maxi

5.Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
> merge uses the technique of divide and conquer. It divides problem to subproblem so that it may take advantage of the structure(only consider the first elelment in an array every time). Its runtime is O(nlgn).

6.How would you determine if someone has won a game of tic-tac-toe on a board of any size?
> Check every row & column, in O case, break the loop when X is shown. Finally, check diagonal.

7.Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    res = [1 for i in range(n)]
    temp = nums[0]
    for i in range(1, n):
        res[i] = temp
        temp *= nums[i]
    temp = nums[-1]
    for i in reversed(range(0, n-1)):
        res[i] *= temp
        temp *= nums[i]
    return res

8.Create a cache with fast look up that only stores the N most recently accessed items.
> 娃

9.How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices?
> Use a hash table that uses keyword as key, array address as value. Each array contain documents with specific keyword and sorted with numeric value, once we need to search by numeric value, use binary search.

10.Given two files that has list of words (one per line), write a program to show the intersection.
> use hash table

11.What kind of data structure would you use to index annagrams of words? e.g. if there exists the word “top” in the database, the query for “pot” should list that.
> use hash table with key sorted by ascii table