// 2024/08/14
// interviewer: Alisha
// interviewee: Ted

// Q1 ----------------------------------

start 11:10

a = [1, 2, 4, 3]
b = [1, 3, 2, 3]

c = [1, 3, 4, 3]

Our goal is to obtain an array C such that the smallest positive integer not present in C is as small as possible.

ans : 2

1. a.length = b.legth
2. a.length > 0
3. return int

a = [1, 2, 1, 3]
b = [1, 3, 2, 3]

c = [1, 3, 2, 3]

a = 12345
b = 12345
c = 12345
-> 6

// A = 1314, B = 1122 -> 2

1. sort(a + b)
1. find a[i] = b[i], 0<=i<= a.length, x -> unordered_set
2. find a[i] != b[i], 選看過的 or 選最大的

TC: O(nlogn)
SC: O(n)

// 11:25

// a = [1, 2, 4, 3]
// b = [1, 3, 2, 3]

// seen: {1,3}
// c: [1, 3, 4, 3]
// c: [1,3,3,4]
// d: [1,1,1,2,2,3,3,3,4]


int findMin(vector<int>& a, vector<in>& b) {
    unorderd_set<int> seen;
    for (int i = 0; i < a.length; i++) {
        if (a[i] == b[i]) {
            seen.insert(a[i]);
        }
    }
    
    vector<int> c;
    for (int i = 0; i < a.legnth; i++) {
        if (a[i] != b[i]) {
            if (seen.count(a[i])) {
                c.push_back(a[i]);
            } else if (seen.count(b[i])) {
                c.push_back(b[i]);
            } else {
                c.push_back(max(a[i], b[i]));
            }
        } else {
            c.push_back(a[i]);
        }
    }
    sort(c.begin(), c.end());
    
    vector<int> d;
    for (int i = 0; i < a.length; i++) {
        d.push_back(a[i]);
        d.push_back(b[i]);
    }
    sort(d.begin(), d.end());
    
    
    // c: [1,3,3,4]
    //       p
    // d: [1,1,1,2,2,3,3,3,4]
    //           p
    int pc = 0;
    int pd = 0;
    for (int i = 0; i < d.size(); i++) {
        if (d[pd] == c[pc]) {
            while (pd < d.size() - 1 && d[pd] = d[pd + 1]) {
                pd++;
            }
        } else {
            return d[pd];
        }
        pc++;
        pd++;
    }
}

// 11:25

// a = [1, 2, 4, 3]
// b = [1, 3, 2, 3]

// seen: {1,3}
// c: {1,3,4}
// ans: 2


TC: O(n)
SC: O(n)

int findMin(vector<int>& a, vector<int>& b) {
    unorderd_set<int> seen;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == b[i]) {
            seen.insert(a[i]);
        }
    }
    
    unorderd_set<int> c;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            if (seen.count(a[i])) {
                c.insert(b[i]);
            } else if (seen.count(b[i])) {
                c.insert(a[i]);
            } else {
                c.insert(max(a[i], b[i]));
            }
        } else {
            c.insert(a[i]);
        }
    }
    
    int ans = INT_MAX;
    for (int i = 0; i < a.size(); i++) {
        if (c.count(a[i]) == 0) {
            ans = min(ans, a[i]);
        }
        if (c.count(b[i]) == 0) {
            ans = min(ans, b[i]);
        }
    }
    return ans;
}

// finish 12:00

feedback
- problem statement clarify
- approach 敘述完整到產出答案

// Q2 ----------------------------------