info2022-homework1
===

面試官：蔡想想🐱
應徵者：沉石中👨

## [884. Uncommon Words from Two Sentences](https://leetcode.com/problems/uncommon-words-from-two-sentences/)

🐱：希望**沉石中**可以找到兩個句子中的「uncommon words」。
🐱：而 uncommon word 的意思是這個單字在這兩個句子中，只出現一次，而每個單字都是全小寫由空白鍵分隔的單字。

👨：想法是用一個 hash map 把所有的 word 都用一個計數器，如果沒看過的 word 就註冊到 hash table 裡面。
👨：如果有看過（也就是在 Hash table 裡面的話），就把 hash table 的計數器加一。

🐱：聽起來蠻合理得，就像本喵的罐罐。
🐱：可以請你演示一下這個範例嗎？

👨：如果是

s1 = "this apple is sweet"
s2 = "this apple is sour"

👨：那麼我的操作就會像是：

this↑ apple is sweet 
this apple↑ is sweet 
this apple is↑ sweet 
this apple is sweet↑

👨：像這邊 ↑ 一樣，去切割字串，每次都會拿到一個 word 的 token。
👨：所以我的 Hash table 經過 s1 與 s2 時就會紀錄：

this: 2
apple: 2
is: 2
sweet: 1
sour: 1

🐱：看起來蠻合理的，那你會如何去用 C++ 實現呢？
👨：像這樣

#include <ranges>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<std::string> f(const std::string &s1, const std::string &s2) {
  std::unordered_map<std::string, int> table;
  std::vector<std::string> res;

  auto register_in_table = [&table](const auto &tok) -> void { ++table[tok]; };

  for (const auto &tok : s1 | std::ranges::views::split(' '))
    register_in_table(std::string(tok.begin(), tok.end()));

  for (const auto &tok : s2 | std::ranges::views::split(' '))
    register_in_table(std::string(tok.begin(), tok.end()));

  for (const auto &[key, value] : table)
    if (value == 1)
      res.emplace_back(key);

  return res;
}

這邊技術面可以討論的有：
1. constexpr
2. C++20 ranges in FP
3. constexpr hash_map
4. std::string_view to replace std::string
5. compile time memory allocation
6. small string optimization
7. C\+\+14 generic lambda and C\+\+20 template lambda

不過主要應該是要以互動面檢討，技術面的部份應該留到其他地方說明。

### 互動面檢討

> todo here

## [7. Reverse Integer](https://leetcode.com/problems/reverse-integer/)

🐱：這是一個要把 32 位元整數反轉的問題。
🐱：輸入是一個 32 位元的整數，你應該回傳給我這個整數的反轉，並且保留正負號於前方；但如果反轉之後的結果是超過 32 位元能夠表示的數值，那你要回傳 0。

👨：所以舉例來說， -123 要回傳 -321，而 123 要回傳 321 對嗎？

🐱：對，也要注意說如果是 12300 要回傳 321，而不是 00321。應該要把前綴的 0 移除掉。

👨：好的

🐱：你能告訴我，你的想法嗎？

👨：我想我會這樣處理：
1. 紀錄下正負號
2. 把正負號移除
3. 把多餘的 0 輕掉
4. 反覆 mod 10 取各位數，紀錄
5. 搭配前面紀錄得正負號，輸出該紀錄

🐱：聽起來蠻合理的。
🐱：麻煩你實做看看相關的程式碼。

👨：好的

int f(int x) {
    bool is_neg = x < 0;
    x = std::abs(x);
    
    while(x % 10 == 0)
        x /= 10;
    
    int res = 0;
    while(x) {
        res = res * 10 + x % 10;
        x /= 10;
        
        if (res <= 0)
            return 0;
    }
    
    return (is_neg) ? (-1) * res : res;
}

🐱：請問你有沒有辦法把這應用上 `constexpr` 讓這個函式能夠**確定**在 compile time 被 evaluation？

👨：（面試過程中有嘗試，但仍沒有給出具體解答）

事後想一下：
其實還是可以保留 signed bit 搭配 bitwise 運算，判斷是否發生 overflow。

#include <cmath>
#include <iostream>

consteval int f(int x) {
	bool is_neg = x < 0;
	x = std::abs(x);

	while(x % 10 == 0)
		x /= 10;

	// Suppose there is not existing any 64-bit register.
	unsigned int res = 0;
	while(x) {
		res = res * 10 + x % 10;
		x /= 10;

		bool is_overflow = !!(res & (1 << 31));
		if(is_overflow)
			return 0;
	}

	return (is_neg) ? (-1) * res : res;
}

### 互動面檢討

> todo here