# 趨勢考古題

## 線上

1. 時鐘處理
* 給定數字串，輸出排列最大的時間數字，不合法也要挑掉

基本上只能硬解，把排序全跑一次，取最大並且符合規則的。

2. 票價問題
* 票類型有一天，七天，三十天的。 給定旅行日期取最小買票價格

用 dp 解，把不用的天數設為 INT_MAX ，要用的設為 0 ，第零天也設為 0
然後從第一天開始推，推出來的其實是到第幾天，如果這一天是不用旅行的，就直接把前一天的總票價 copy 過來。如果這一天要旅行，就把前面扣掉票價天數的 min 移過來，最後一天就是答案

coin problem 也可以用這個邏輯去解，只是改成該數字組成的最小硬幣數。

3. Graph 問題

[來自這裡](https://blog.little.tw/2018/09/26/%E6%96%B0%E9%AE%AE%E4%BA%BA%E9%9D%A2%E8%A9%A6part-ii-%E6%9E%9C%E5%AF%A6%E5%A4%A5%E4%BC%B4%EF%BC%8C%E8%B6%A8%E5%8B%A2%E7%A7%91%E6%8A%80/)

用 BFS 刷過去就可以

先建表，建表的部份要練習一下

4. 字串處理
無相關資料

## 現場筆試

[來自這裡](https://hackmd.io/@8ZS5TqpSS268IuLnUjTnyg/r1RugSvp-?type=view)

1. 搜尋 List 的時間複雜度 O(N) N = length
搜尋 Binary Tree 的時間複雜度 O(logN) N = Node conut
搜尋 Hash Table 的時間複雜度 O(1) ~ O(N) N = conflict time

2. 講出以下輸出

using namespace std;
class A{
public:
    A() { print(); }
    virtual void print() { cout << "in A" << endl; }
};
class B : public A{
public:
    B() { print(); }
    virtual void print() { cout << "in B" << endl; }
};
void main(void)
{
    B b;
}

output
in A
in B

如果不加 public 會不能跑，建構子必須是 public 的但 class 預設所有東西都是 private 的

3. 給一段程式碼裡面包含一個 function(string *path) 此 function 的目的為將 Path 字串最尾端的”\\”刪除,然後問此段程式碼有何問題。(25%)

還沒試過

4. Link List 反轉, 不能使用任何額外記憶體 (25%)
我覺得應該是指 space complexity(1)

如果 link list 是雙向跑的，跑到底然後用 xor 一路雙指標轉回來就好
如果是單向的，

1 -> 2 -> 3 -> 4

或是
curNext = cur -> Next
cur -> next = prev
prev = cur
cur = curNext

5. 寫一個函數, int findPosition (Node *root, int value),root 為一個二元搜尋樹, value 為 Node 的鍵值,這函數要回傳 value 在二元搜尋樹的中序追蹤為第幾個。

同綠皮書解答，必須要有往回的

## 上場

### Q1

// 太簡單沒留

### Q2

// you can use includes, for example:
// #include <algorithm>
#include <vector>
#include <string>
#include <iostream>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

std::string solution(std::string &S, std::string &T) {
    // write your code in C++14 (g++ 6.2.0)
    // 統計每個文字數量就好， 只能換一次...所以不相等的話我想想，字母數量相同且只有兩個地方不同
    // 反之插入 -> 只能在尾
    // 不然移除
    // 差距只能為 1 不然都是 IMPOSSIBLE
    // a = 0, z = 25
    using namespace std;
    vector<int> cntS(26, 0);
    vector<int> cntT(26, 0);
    for (const auto& v : S) {
        cntS[v - 'a']++;
    }
    for (const auto& v : T) {
        cntT[v - 'a']++;
    }

    if (cntS == cntT) {
        // 只能是 swap or IMPOSSIBLE
        auto target = 0;
        auto diff = 0;
        for (auto i = 0; i < S.size(); ++i) {
            if (S[i] != T[i]) {
                diff++;
                target = i;
            }
        }
        return(diff == 2 ? (string("SWAP ") + T[target] + " " + S[target]) : "IMPOSSIBLE");
    }

    if (S.size() == T.size() - 1) {
        const auto result = T.compare(0, S.size(), S);
        return (result == 0 ? (string("INSERT ") + T.back()) : "IMPOSSIBLE");
    }

    if (S.size() == T.size() + 1) {
        const auto result = S.compare(1, S.size(), T);
        return (result == 0 ? (string("REMOVE ") + S.front()) : "IMPOSSIBLE");
    }

    return "IMPOSSIBLE";
}

int main()
{
    std::string input1("nice");
    std::string input2("nicer");
    std::cout << solution(input1, input2) << std::endl;
    input1 ="will";
    input2 ="ill";
    std::cout << solution(input1, input2) << std::endl;
    input1 ="late";
    input2 ="tale";
    std::cout << solution(input1, input2) << std::endl;
    input1 = "o";
    input2 = "odd";
    std::cout << solution(input1, input2) << std::endl;
}

### Q3

#include <vector>
#include <iostream>
using namespace std;

int solution(int N) {
    // write your code in C++14 (g++ 6.2.0)
    // 開始推一下
    // 拆 10 + 1 * 10 + 1
    // 10 * 10 = 100 1 不變
    // 11 * 10 = 110 1 數量不變
    // 11 * 10 + 11 = 121 = -1 + 1
    // 121 * 10 + 121 = -2 +1 不能硬算最後會炸....
    // 用 digital 的數量推？用大數運算硬算嗎....好吧就這樣
    vector<int> cur{ 1,1 };
    if (N == 0) {
        return 1;
    }
    if (N == 1) {
        return 2;
    }

    while (--N) {
        const auto base = cur;
        cur.push_back(0);
        auto carry = 0;

        for (auto i = 0; i < base.size(); ++i) {
            *(cur.rbegin() + i) = *(cur.rbegin() + i) + *(base.rbegin() + i) + carry;
            carry = 0;
            if (*(cur.rbegin() + i) >= 10) {
                carry = 1;
                *(cur.rbegin() + i) = *(cur.rbegin() + i) % 10;
            }
        }
        *(cur.begin()) += carry;
        carry = 0;
        if (*(cur.begin()) >= 10) {
            *(cur.begin()) = *(cur.begin()) % 10;
            cur.insert(cur.begin(), 1);
        }
    }
    auto result = 0;
    for (const auto& v : cur) {
        if (v == 1) {
            result++;
        }
    }
    return result;
}

int main()
{
    for (auto i = 0; i < 101; ++i) {
        cout << solution(i) << ",";
    }
    cout << endl;
}

現場看了一下，一百分XDDD