---
title: info2021-homework1
---
# info2021-homework1
> 貢獻者: 艾睡覺
[TOC]
:::info
🧑💻: interviewer
👦: interviewee
:::
## 漢語
### Q1:
[LeetCode 53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)
#### 討論
* 👦 你好，我是艾睡覺
* 🧑💻 你好，我是面試官，那我們開始面試吧。
* 🧑💻 題目叫做 Maximum Subarray ，Input 會有一個 integer Array ，你要找到一個連續的 Subarray，那這個 Subarray 裡的數字總和要是最大的，把這個最大的數字 return。
* 👦 請問 array 裡的整數是有正有負嗎?
* 🧑💻 沒錯，有正有負。
* 👦 請問剛才有說到 連續的 `subarray` ，連續是指說他是 `array` 中連續的一段整數組成的 `subarray` 嗎。
* 🧑💻 沒錯，連續的一段整數
* 👦 最先想到的解法可能是暴力解，先算 subarray 第一個 item，再來是 subarray[1,2] 的數字和，再來是`[1,2,...,n]`，然後從第二個 item 開始，`subarray[2]`, `subarray[2,3]`。
* 🧑💻 你覺得暴力解的時間複雜度會到多少。
* 👦 時間複雜度會到 O(n^2)
* 🧑💻時間會花有點多，有沒有更好的方法。
* 👦 可能可以用條件判斷上一個 `Subarray` 的總和是否為負，若為負則直接捨棄。
#### code:
```cpp=
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
int ans = INT32_MIN;
int tmp = 0;
for (int i = 0; i < nums.size(); i++)
{
tmp += nums[i];
if (tmp > ans)
ans = tmp;
if (tmp <= 0) tmp = 0;
}
return ans;
}
};
```
---
### Q2
[LeetCode 461. Hamming Distance](https://leetcode.com/problems/hamming-distance/)
#### 討論：
* 🧑💻 題目叫做 Hamming Distance， input 是兩個整數，比較兩數對應的 bit ，output 出兩個整數有幾個位子的 bit 值是不一樣的。
* 👦 我想請問數字都是正整數嗎
* 🧑💻 沒錯，都是正整數
* 👦 好那我最開始的想法是，把兩個整數都轉成string。
* 🧑💻 這個方法可以，但你可以用 bitwise 操作來解決這個問題嗎。
* 👦 好 那我會先把兩個數做 xor ，這樣一來每個位子的 bit 值不一樣的話，就會得到 1，如果一樣則會得到 0。再來只要計算有幾個 1 就好了。再來要計算 每個 bit 有幾個1的話，時間複雜度會到 O(logn)
#### Code:
```cpp=
class Solution {
public:
int hammingDistance(int x, int y) {
int n = x^y;
int dist = 0;
while (n)
{
dist += n & 1;
n >>= 1;
}
return dist;
}
};
```
---
### Q3
[477. Total Hamming Distance
](https://leetcode.com/problems/total-hamming-distance/)
#### 討論：
* 👦 請問array裡面的數會有重複的嗎?
* 🧑💻 會的。
* 👦 那假設array裡面是 [4,14,4]，就會有 pair:(4, 14), (4, 4), (14, 4) 嗎？
* 🧑💻 沒錯。
* 👦 那想法是，找到 array 裡的每一個 pair ，分別計算他們的 hammin distance ，時間複雜度會到 $O(n^2)$
* 🧑💻 這是個好方法，那你想一下可不可以把時間壓到 Linear Time。
* 👦 好的，那就是一次只看一個 bit ，觀察 array 裡的每一個整數的第 i 個 bit，觀察一共有幾個 1 ，幾個 0，再來只要將 1 的個數乘上 0 的個數，即可得知第 i 個 bit 的 hammin distance，最後只要將每個 bit 的 hammin distance 加總後即為答案。
#### Code:
```cpp=
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int count = 0;
for (int i = 0; i < 32; i++) {
int k = 0;
for (int j = 0; j < nums.size(); j++) {
if ((nums[j] >> i) & 1) {
k++;
}
}
count += k * (nums.size() - k);
}
return count;
}
};
```
---
## 英語
### Q1
[LeetCode 70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
#### 討論：
* 👦 So, it means if input is one, i can only use 1 step to climb, if input is two, i can use double 1 step and only 2 step.
* 🧑💻 yes, it's right
* 👦 i think this problem is like fibonacci number, the fomula is `f(n) = f(n-1) + f(n-2) ， i can use this formula to solve this problem in linear time.
#### Code:
```cpp=
class Solution {
public:
int climbStairs(int n) {
vector<int> v(n+1);
if (n==1)
return 1;
else if (n==2)
return 2;
v[1] = 1;
v[2] = 2;
for (int i=3; i<=n; i++)
{
v[i] = v[i-1] + v[i-2];
}
return v[n];
}
};
```
---
### Q2
[LeetCode 88. Merge Sorted Array
](https://leetcode.com/problems/merge-sorted-array/)
#### 討論：
* 🧑💻 Ok let’s start the second question, the question is Merge Sorted Array
* 🧑💻 You are given two integer arrays nums1 and nums2, sorted in non-decreasing order
* 🧑💻 and two integers m and n, m is the number of elements in nums1, and n is number of elements in nums2
* 🧑💻 Merge nums1 and nums2 into a single array sorted in non-decreasing order.
* 👦 Should I create another array to stored final sorted array?
* 🧑💻 it’s no need .your final sorted array just stored inside array nums1, nums1 has length of m+n
#### Code:
```python=
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
nums1[:m+n] = nums1[:m] + nums2[:n]
nums1[:m+n] = sorted(nums1)
```
---
### Q3
[LeetCode 11. Container With Most Water
](https://leetcode.com/problems/container-with-most-water/)
#### 討論：
* 🧑💻 the third question is Container With Most Water, the input is non negative integers, the number of integers is n, the integers is noted as a1, a2, … an,
* 🧑💻 each integer denote a point at coordinate(i, ai), so if integer is a2, it means a point at coordinate (2, a2)
* 🧑💻 we have n points , and we draw the two endpoints of the line i is at (i, ai) and(i, 0) .
* 🧑💻 finally we get n lines, we need to find two line,which, together with the x-axis forms a container and we find the container contains the most water.
* 👦 ok, i think i can watch all pair of lines, and choose the pair of lines which contains most of water.
* 👦 The time complixity is $O(n^2)$
* 🧑💻 could solve the problem at linear time
* 👦 the idea is we will start at first line and last line, the widest container is a good container.
* 👦 we can see the first line and last line, if we fix the first line, no matter choose which line, it can’t contain more water, so we can simply consider second line and last line
* 🧑💻 ok you can start coding
#### Code:
```cpp=
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0;
int r = height.size() -1;
int water = 0;
while(l<r)
{
water = max(water, (r-l)*min(height[l],height[r]));
if (height[l] < height[r])
l += 1;
else
r -= 1;
}
return water;
}
};
```
## 檢討
### 針對 interviewee
* 需熟悉 REACTO 步驟：
* Repeat: 重複提問，確認自己理解原本的要求
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* Approach: 說明自己打算採用的方案
* Code: 撰寫程式
* Test: 若不能實際測試，那說明驗證程式的方案
* 在 Repeat 步驟時，需假設自己只能夠聆聽 interviewer 的口頭描述，實際思考可能會有的疑問。
* 應該使用 Google Docs 作答
* 在作答時都是使用 LeetCode 來檢查程式，並沒有使用到 REACTO 的 TEST 步驟。
### 針對 interviewer
* 其實對題目是描述得不夠清楚，如果 interviewee 沒有看到 LeetCode 的題目的話，其實不太能夠瞭解問題。
* 可能讓 interviewee 使用 Google Docs 作答。
---
# info2021-homework2
👦
## 漢語
### Q1:
[LeetCode 53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)
🧑💻 你好，我是面試官，那我們開始面試吧。
🧑💻 題目叫做 Maximum Subarray ，Input 會有一個 integer Array ，你要在這個 interger array 中找到一個連續的 Subarray，目標是要找到的數字總和最大的subarray，最後 return 這個最大的數字總和就可以了 。
👦 好的，那我想先問幾個問題
```
整數的正負？有正有負
array 大小最小是多少？ 至少一個整數
```
👦 好的，那第一個方法會是暴力解，把所有可能的 subarray 看過一次後，得出最大的值，時間複雜度會到 $O(n^2)$
```
e.g. [4, -1, 2, -3]
[4, -1]
[4, -1, 2]
[4, -1, 2, -3]
[-1, 2]
[-1, 2, -3]
[2, -3]
O(n^2)
```
🧑💻 那可不可以把時間壓在linear time呢？
👦 那會是用 dp 的方式，記錄每一個區間最大的數字總和，那在算每一個區間的時候，都會考慮前一個區間的數值，值不值得被加進來。
```
/*
dp
dp[0] : (0)
dp[1] : (0~1)
dp[2] : (0~2)
input: [2, -3, -7, 2, 4]
dp[0] = 2
dp[1] = -1
dp[2] = -7
dp[i] = dp[i-1] > 0? dp[i-1] + x_i : x_i
*/
```
🧑💻 好的，那請開始你的coding
👦 coding...
🧑💻 可不可以驗證你的程式碼呢
👦 （一步步地講解）
```
// nums = [-1, -2, 3, 7] -> 10;
int ans = INT32_MIN;
// if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
if (dp[0] > ans) ans = dp[0];
// ans = 10
// dp[0] = -1
// dp[1] = -2
// dp[2] = 3
// dp[3] = dp[2] + 7 = 10
// i =2
```
final code:
```cpp=
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
int ans = INT32_MIN;
vector<int> dp(nums.size());
dp[0] = nums[0];
if (dp[0] > ans) ans = dp[0];
for (int i = 1; i < nums.size(); i++)
{
if (dp[i-1] < 0)
dp[i] = nums[i];
else
dp[i] = dp[i-1] + nums[i];
if (dp[i] > ans)
ans = dp[i];
}
return ans;
}
};
```
### Q2
🧑💻 你好，我是你的主考官，那第二題的題目是這樣。
🧑💻 題目叫做 Total Hamming Distance，那我先講一下 hamming distance 是什麼，一個整數有32個bits，hamming distance 就是兩個整數，去觀察這兩個整數個字對應的bit中，要算出有幾個位子的 bit 值是不一樣的，那題目的 input 會是一個 array，要找到 array 裡頭，每兩個整數為一個 pair，要算出每個 pair 的 hamming distance 加總。
👦 那我想先確認一下 Hamming Distance 的想法
```
// hamming distance
// 2, 3-> 1
// 2: 0010
// 3: 0011
```
🧑💻 你舉的例子是對的
👦 先想到的方法是把每一個 pair 都算一次 hamming distance ，最後加總。
```
nums = [1,2,3,4]
(1,2)->O(1)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
n-1 + n-2+ n-3 -> O(n^2)
time complexity: O(n^2)
```
🧑💻 可不可以把時間壓在 linear time
👦 好那第二個方法會是一次只看一個位子的 bit，觀察每個數在這個位子的 bit值是多少，算出該位子總共有幾個 1 ，幾個 0，將兩數相乘即為該位子之 hamming distance，只要跑完32 個 bit 就完成了，時間複雜度可優化至 O(n)
👦 那我開始我的實作
```cpp
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int count = 0;
for (int i = 0; i < 32; i++) {
int k = 0;
for (int j = 0; j < nums.size(); j++) {
if ((nums[j] >> i) & 1) {
k++;
}
}
count += k * (nums.size() - k);
}
return count;
}
};
```
👦 再來我檢查我的程式碼
```
// 1: 0001
// 2: 0010
// 3: 0011
// 4: 0100
// 5: 0101
for (int i=0; i<32; i++)
{
int k=0;
for (int j=0; j<nums.size(); j++)
{
// 0101 & 1 = 1
if ((nums[j] >> i) & 1){
k++;
}
}
// k =2
// n-k = 3
// 0的個數＊1的個數
count += k*(nums.size() - k);
// count = 6 + 6 + 6
}
```
## 英語
👦 Hello my name is Sleep
🧑💻 Hi Sleep. I am your employer.
🧑💻 let’s start our first question, the first question is Climbing stairs.
🧑💻 the input is integer n, You are climbing a staircase. It takes n steps to reach the top.
🧑💻 Each time you can either climb 1 or 2 steps. Then, you should answer i n how many distinct ways can you climb to the top?
👦 ok, i have understand the question. To take an example. If input is one, i can only use 1 step to climb, if input n is two, i can use double 1 step and only 2 steps. Then i should return 2, because there is two distict way. Am I right?
```
integer: n
n = 1 -> 1step -> return 1
n = 2 -> 1step + 1step, 2step -> return 2
```
🧑💻 your example is right. then, do you have any idea to solve this problem.
👦 i think this problem is like fibanacci number.
```
n=3 third steps = second steps + one steps or first steps + two steps
n=4 forth steps = third steps + one steps or second steps + two steps
f(n=3) = f(2) + f(1)
f(n=4) = f(3) + f(2)
f(n) = f(n-1) + f(n-2)
```
👦 I am going to start my coding
```cpp
class Solution {
public:
int climbStairs(int n) {
vector<int> v(n+1);
if(n==1)
return 1;
else if (n==2)
return 2;
v[1] = 1;
v[2] = 2;
for (int i=3; i<= n; i++)
{
v[i] = v[i-1] + v[i-2];
}
return v[n];
}
};
```
👦 I am going to check my code.
### Q2
[LeetCode 11. Container With Most Water
](https://leetcode.com/problems/container-with-most-water/)
#### 討論：
🧑💻 let's start our second question. The question is Container With Most Water, the input is non negative integers, the number of integers is n, the integers is noted as a1, a2, … an,
🧑💻 each integer denote a point at coordinate(i, ai), so if integer is a2, it means a point at coordinate (2, a2)
🧑💻 we have n points , and the line i draw by the two endpoints (i, ai) and(i, 0) .
🧑💻 finally we get n lines, we need to find two line,which, together with the x-axis forms a container and we find the container contains the most water.
ok i have understand this question, let me take an example. I will get n integers, if n is three, we have three integers, [1, 3, 4]
👦 the first method is i can watch all pair of lines, and choose the pair of lines which contains most of water.
👦 The time complixity is $O(n^2)$
```
nums = [1, 2, 3, 4]
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
the total pairs : n-1 + n-2 + n-3
time complexity: O(n^2)
```
🧑💻 could solve the problem at linear time
👦 the second method is we will start at first line and last line, because the height will times width ,the widest container is a good container.
👦 we can see the first line and last line, we will record how many water it can contain, then we need to go to next step.
👦 Let's try if we fix the first line, no matter choose which line, it can’t contain more water
```
(1, 3) : width is 6: water 1x6
(1, 5) : width is 5: water 1x5
(1, 2) : width is 4: water 1x4
```
so we can simply consider second line and last line, and then each next time we don't consider the line which has the smaller height, then time complexity can improve to linear time.
```
nums = [1, 2, 3, 4, 2, 5, 3]
(1,3)->(2, 3)->(3, 3)->(4, 3)->(4, 5)
```
👦 I am going to start my coding
```cpp=
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0;
int r = height.size() -1;
int water = 0;
while(l < r)
{
water = max(water, (r-l) * min(height[l], height[r]));
if (height[l] < height[r])
l += 1;
else
r -= 1;
}
return water;
}
};
```
👦 I am going to check my code
```
vector<int> n = {1, 2, 3, 4, 2, 5, 3};
// l=4, r=4
// (1, 3) -> water 1x 6=6
// (2, 3) -> width =5, water is 2x5=10
// (3, 3) -> width = 4, water is 12
// (3, 5) -> width = 3, water is 9
// (4, 5) -> width = 2, water is 8
// (2, 5) -> width = 1, water is 2
// (5, 5) -> width = 0, water is 0
```
Sign in with Wallet
Connect another wallet