---
# System prepended metadata

title: '2023/02/12 mock interview Candidate: 阿呀呀'
tags: [Tag(mock interview)]

---

# 2023/02/12 mock interview Candidate: 阿呀呀 
###### tags: `Tag(mock interview)`
---

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="700" height="400" style="display: block; margin: 0px auto; border: 0px;" src="http://zbryikt.github.io/quick-timer"></iframe>




# 題目講解
//time: 20:31  
//end: 20:36 (louis), 20:40
       
length = n, m tokens
 
each get 
   v
A ai ...              tokens
B bi ...                get bi coins pay bi tokens


tokens we hold can't greater than m
finally find the maximum coins


5 10
5 6 0 10 2  tokens
2 3 10 0 3  coins

0 tokens
5 6 -> 10 + 3

coins = 10

// 0 token
1) 1th get 5 tokens
2) 2th get 6 tokens => tokens = 11 > 10 (greater than m tokens) keep m tokens
   pay 3 tokens, can get 3 coins 
4) 3th day, get 10 coins, current tokens is 0, get 10 coins
6) pay 3 token to get 3 coins, current token is 10 - 3 => 7




ans = 13 (coins)



two array A, B , and int 
go through 

A[i]: tokens
B[i]: coins


for each day, we can get tokens or pay tokens to get coins.


# 作法講解
// time: 20:43

if current tokens bigger than m tokens, 
we must change token to coins.


5 10
5 6 0 10 2  tokens
2 3 10 0 3  coins

1: 5 token
2: case 1: 5 + 6 > 10,   

   case 2: 3 token to get 3 coin
   
   
3: 10 token => 10 coins


for each day, we can get more tokens, 
  v
5 6 0 10 2  tokens
2 3 10 0 3  coins
  
day 2: 3 coins, 2 token  
day 3: 5 coins



      v v  v 
5 [6] 0 10 2  tokens
2 [3] 0 0  0  coins

how we can get maximum coins


  
5 6 0 10 2  tokens
2 3 10 0 3  coins

day 1: 5 token
day 2: 11 token -> 10 token
day 3: 
5 6 0
2 3 10
we can't get any tokens, but we can change 10 coins

maximum count of change is length of array (len - 1).

10 0 0 0 0 0 tokens
2  1 1 1 1 1  coins

dp[i][j] = x
i = token, j = coins
f
          v
| {x x x} x x |
|         y
first: get token, dp[last_toke + x][last_coins] = dp[last_toke][last_coins]

second: change token, dp[last_token - y][last_coins + y] = dp[last_token][last_coins]



define: dp[i] = x, i means count of tokens, x means coins, 
first: get token, dp[last_token + x] = dp[last_token];

second: change token, dp[last_token - y] = dp[last_token] + y;

TC: O(n * max(token)) SC: O(max(token))

# coding
//time: 

```cpp=
```
# 完成
//time: 21:03



# comment
這場花太長時間在描述題目Ｑ
不過整體來說想法上一開始小歪，不過最後還是有想到正確解法





把句子說完整, 可以說得慢一點.













# Temp

5 6 0 10 2  tokens
2 3 10 0 3  coins

// each day,
// we just try to do either first or second 
// operation

// maximum coins we can get
// starting from index i, current we hold x tokens 
//     Func(int i, int x)

// final ans = Func(0, 0); // starting from index 0, and current token 0 


// operation 1: obtain ai tokens
// Func(int i, int x) -> Func(i+1, x+ai)

// operation 2: pay bi tokens to get bi coins
// Func(int i, int x) -> bi + Func(i+1, x-bi)


// recurrence
// TC: O(2^N) -> no memoration
Func(i, x) = max(Func(i+1, x+ai), bi+Func(i+1, x-bi))

// TC: O(NX)
// top-down dp -> recursive function + memo

// record the ans in each function in a hashtable (array)

// dp[i][x] 
Func(i, x) = max(Func(i+1, min(x+ai, m)), bi+Func(i+1, x-bi))
    
    
// all function will calculate only once
```
i=0 -> 0,1,2,3,...m
i=1 -> ...
...
i=n
Func(i, x): O(n*m) -> product each parameter range
    if (i == n) return 0;
    if (dp[i][x] != -1) return dp[i][x]; // calculate
    
    // operation1
    dp[i][x] = Func(i+1, min(x+ai, m));
    
    // operation2
    if (x >= bi)
        dp[i][x] = max(dp[i][x], bi+Func(i+1, x-bi)));
    return dp[i][x];
```

// dp[n], O(n)
// O(n * 1)
F(int n): possible F() n個
    // O(m)
    if (n == 1 || n == 2) return 1;
    if (dp[n] > 1) return dp[n];
    dp[n] = F(n-1)+F(n-2);
    return dp[n];