// 2024/08/28
// interviewer: Jay
// interviewee: Ted

### Q1 ----------------------------------
start time: 14:34

1 .. n bulbs -> all off

return number of bulbs on(int)

n = 3 => 1
n = 5 => 2
n = 7 => 2
n = 9 => 3

1 2 3 4 5 6 7 8 9
- - - - - - -
1: + + + + + + +
2: + - + - + - +
3: + - - - + + +
4: + - - + + + +
5: + - - + - + +
6: + - - + - - +
7: + - - + - - - - +

TC: O(1)
SC: O(1)

int lightBulbsCnt(int bulbs) {
    return sqrt(bulbs);
}

finish time: 14:47

### Q2 ----------------------------------
start time: 14:47

n, vector<vector<int>> edges
3, edges: {{0, 1}, {0, 2}, {2, 3}}
0 0
/ \
2 1 1
/
3 2

graph: [0: [1, 2], 1: [], 2: [3]]
q: [3]
height = 3

TC: O(edges.length)
SC: O(edges.length)

int treeHeight(int n, vector<vector<int>> edges) {
    vector<vector<int>> graph(n);
    for (vector<int>& edge) {
        graph[edge[0]].push(edge[1]);
    }
    
    queue<int> q;
    q.push(0);
    int height = -1;
    while(!q.empty()) {
        height++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int node = q.front();
            q.pop();
            for (int& nextLevelNode: graph[node]) {
                q.push(nextLevelNode);       
            }
        }
    }
    return height;
}

finish time: 15:02
https://atcoder.jp/contests/dp/tasks/dp_c
### Q3 ----------------------------------

start time: 15:02

N, vector<vector<int>>
3, {{10, 20, 30}, {40, 5, 70}, {30, 8, 10}}

sol1: brute force: TC: O(2^n)

{10, 20, 30}, {100, 99, 0}, {5, 1, 0}
30 + 99 + 5
sol2:
3, {{10, 20, 30}, {100, 99, 0}, {5, 1, 0}}
highCnt: [134, 131, 130]
tmp0: 130
tmp1: 129
tmp3: 20

return -> int

TC: O(days)
SC: O(1)

int maxHigh(int days, vector<vector<int>> activities){
    vector<int> highCnt(3, 0);
    highCnt[0] = activities[0][0];
    highCnt[1] = activities[0][1];
    highCnt[2] = activities[0][2];
    for (int i = 1; i < activities.size(); i++) {
        int tmp0 = highCnt[0], tmp1 = highCnt[1], tmp2 = highCnt[2];
        highCnt[0] = max(tmp1, tmp2) + activities[i][0];
        highCnt[1] = max(tmp0, tmp2) + activities[i][1];
        highCnt[2] = max(tmp0, tmp1) + activities[i][2];
    }
    return max({highCnt[0], highCnt[1]}, highCnt[1]);
}

finish time: 15:44

### feedback
1. Q1 Q2 came up with a solution fast, good coding.
2. Q3 solved after giving hints, but overall pretty good.