You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

解法1： 找规律 + Memorization, One pass O(N) Time

这题需要多写几个数出来找一下规律:
如果我们把0到15的二进制表达式写出来，并且把对应的set bit的个数写出来，我们可以得到如下：

0 0000 0

1 0001 1

2 0010 1

3 0011 2

4 0100 1
5 0101 2
6 0110 2

7 0111 3

8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4

观察后联系hint,发现偶数X的bit数是X/2的bit数，奇数X的bit数是X/2的bit数+1，于是可以得到一个O(N)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int[] countBits(int num) {
   int[] dp = new int[num + 1];
   // dp[0] is 0
   for (int i = 1; i <= num; i++) {
        if (i % 2 == 0) {
            dp[i] = dp[i / 2];
        } else {
            dp[i] = dp[i / 2] + 1;
        }
    }
    return dp;
}

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Hint:

You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?

解法1： 找规律 + Memorization, One pass O(N) Time

这题需要多写几个数出来找一下规律:
如果我们把0到15的二进制表达式写出来，并且把对应的set bit的个数写出来，我们可以得到如下：

0 0000 0

1 0001 1

2 0010 1

3 0011 2

4 0100 1
5 0101 2
6 0110 2

7 0111 3

8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4

观察后联系hint,发现偶数X的bit数是X/2的bit数，奇数X的bit数是X/2的bit数+1，于是可以得到一个O(N)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int[] countBits(int num) {
   
   int[] dp = new int[num + 1];
   // dp[0] is 0
   for (int i = 1; i <= num; i++) {
        if (i % 2 == 0) {
            dp[i] = dp[i / 2];
        } else {
            dp[i] = dp[i / 2] + 1;
        }
    }
    
    return dp;
}

解法2： 找规律 + Memorization, One pass O(N) Time

另一种规律，我们使用i & (i - 1) 来看对应的结果。

0 0000 0 N/A

1 0001 1 0000

2 0010 1 0000

3 0011 2 0010

4 0100 1 0000
5 0101 2 0100
6 0110 2 0100

7 0111 3 0110

8 1000 1 0000
9 1001 2 1000
10 1010 2 1000
11 1011 3 1010
12 1100 2 1000
13 1101 3 1100
14 1110 3 1100
15 1111 4 1110

更加简化的一个规律是dp[i] = dp[i & (i - 1)] + 1, 比如15, 15 & 14 = ‘1110’， ’1110‘的bits是3，所以15的bits是4
那么就可以得到如下的程序。这个程序更简短。

1
2
3
4
5
6
7
8
9
10

public int[] countBits(int num) {
   
   int[] dp = new int[num + 1];
   // dp[0] is 0
   for (int i = 1; i <= num; i++) {
        dp[i] = dp[i & (i - 1)] + 1;
    }
    
    return dp;
}

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

解法1：DP O(N^2) with O(N) 空间

如果用暴力的方法想：对于一个数字N，我们可以从1开始试， 因为1是一个perfect square,那么求出N - 1的解，假设为X，则N的解就是X+1
我们从1开始尝试所有可能的组合，然后求出了一系列的解之后挑选最小的值。但这样做的话复杂率特别高，应该是指数级的
实际上可以发现，这里有很多overlapping的问题，比如我们求12的最小值，那么如果第一个选择的值是4，则剩下的为8.
当我们在前面选择第一个值为2时，子问题变为寻找10 - 2 = 10的最小值，而当我们求10的最小值的时候可能已经求过了8的最小平方数。
所以我们可以想到用dp/memorization的方法去解决这个问题。

1. 建立dp数组dp[N], N是要求的数字，dp数组中存储的是对应的这个数字n，他的最小平方和数。
2. 初始化,将所有perfect square的数字都设为1
3. 对于非perfect square的数字，dp[i] = Min(dp[j] + dp[i - j], j = 1 … i / 2),也就是说,dp[12] = Min of (dp[1] + dp[11], dp[2] + dp[10], …)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

   public int numSquares(int n) { if (n < 0) { return 0; } if (n == 0 ) { return 1; } int[] dp = new int[n + 1]; for (int i = 1; i*i <= n; i++) { dp[i*i] = 1; } for (int i = 2; i <= n; i++) { if (dp[i] != 1) { int res = Integer.MAX_VALUE; for (int j = 1; j <= i/2; j++) { int temp = dp[j] + dp[i - j]; res = Math.min(temp, res); } dp[i] = res; } } return dp[n]; }

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

解法1：DP O(N^2) with O(N) 空间

也是很直接的dp, dp[i][j]表示的是到(i,j)点的最小路径和。dp[i][j] = Min(dp[i - 1][j], dp[i][j -1]) + A[i][j]
最后的结果便是dp[n - 1][m - 1], 用滚动数组节省内存空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public int minPathSum(int[][] grid) {
    
    if (grid == null || grid.length == 0) {
        return 0;
    }
    
    int nrow = grid.length;
    int ncol = grid[0].length;
    
    int[] dp = new int[ncol];
    dp[0] = grid[0][0];
    
    // Initialize the dp array
    for (int j = 1; j < ncol; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
        
    for (int i =  1; i < nrow; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < ncol; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    
    return dp[ncol - 1];
}

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

解法1：DP O(N^2) with O(N) 空间

是Unique Path的扩展，唯一区别是对于任意一个格子，要先判断是否为1，如果是1则有障碍物，在这种情况下，则到达这个
点的办法为0。其他地方的计算还是依照dp[i][j] = dp[i -1][j] + dp[i][j - 1]，这里同样用了滚动数组节省空间。
这题的坑是在： 一开始初始化数组的时候，对[0][i]的判断取决于[i][i - 1] 和那个格子是否有障碍物两个条件。不能仅根据当个格子来判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
    if (obstacleGrid == null || obstacleGrid.length == 0) {
        return 0;
    }
    
    int nrow = obstacleGrid.length;
    int ncol = obstacleGrid[0].length;
    
    int[] dp = new int[ncol];
    dp[0] = obstacleGrid[0][0] == 0?1:0;
    for (int j = 1; j < ncol; j++) {
        dp[j] = obstacleGrid[0][j] == 0?dp[j - 1]: 0;
    }
    
    for (int i = 1; i < nrow; i++) {
        dp[0] = obstacleGrid[i][0] == 0?dp[0] : 0;
        for (int j = 1; j < ncol; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[j] += dp[j - 1];
            } else {
                dp[j] = 0;
            }
        }
    }
    
    return dp[ncol - 1];    
}

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Note: m and n will be at most 100.

解法1：DP O(N^2) with O(N^2) 空间

很直接的2维dp问题，对于任意一个点i,j,到达它的办法可以从上面过来，也可以从左面过来。
所以总的办法数是dp[i][j] = dp[i - ][j] + dp[i][j -1]
结果就是dp[m - 1][n - 1]

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    
    int[][] dp = new int[m][n];
    
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i -1][j] + dp[i][j - 1];
        }
    }
    
    return dp[m - 1][n - 1];
}

解法2：DP O(N^2) with O(N) 空间

和triangle相类似的思路，dp的过程是自上而下自左而右，那么可以用滚动数组来减少内存的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    
    int[] dp = new int[n];  
    for (int j = 0; j < n; j++) {
        dp[j] = 1;
    }
        
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1]; // dp[j] initially stores the previous row's calculation
        }
    }
    
    return dp[n - 1];
}

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解法1：DP O(N^2) with O(N^2) 空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public int minimumTotal(List(List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }
    
    int n = triangle.size();    // number of rows
    
    int[][] dp = new int[n][n];
    
    for (int[] temp : dp) {
        Arrays.fill(temp, Integer.MAX_VALUE);
    }
    
    dp[0][0] = triangle.get(0).get(0);
    
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        for (int j = 1; j <=i; j++) {
            dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
        }
    }
    
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.min(res, dp[n - 1][i]);
    }
    
    return res;
}

解法2：DP O(N^2) with O(N) 空间

观察上面的解法可以看到，我们的2维数组实际上只用到了上一行的信息，由此我们可以对内存做一个小优化而达到O(N)的空间。
我们只保留上一行的每一个位置的最小值，需要一个大小为N的数组，N是总的行数，然后在计算中只要反复更新这个数组。
也就是说dp[i] = Math.min(dp[i - 1], dp[i]) + A[j][i] j是现在计算到的行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }
    
    int n = triangle.size();    // number of rows
    
    int[] dp = new int[n];
    
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = triangle.get(0).get(0);
    
    for (int i = 1; i < n; i++) {
        // i is the current row number
        for (int j = i; j >= 0; j--) {
            // 这里比较容易出错，j要从后往前更新，因为下一行的计算用到了上一行的[i - 1] 和[i]，
            // 需要先更新后面的才不会override前面的数据
            // 同时下标使用的是j以此来模拟不同column的计算
            dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
        }
    }
    
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.min(res, dp[i]);
    }
    
    return res;
}

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

解法1：DP O(N) with O(1) 空间

典型DP, dp数组表示前i个数字的# of decode ways. 那么对于dp[i], 他存在decode的办法有两种：

1. 单独一个数字decode, 这种情况实际是dp[i -1]
2. 和嵌挤一个数字拼成一个10 ~ 26 的数字decode, 这种情况的办法是dp[i - 2]
   但是要注意的是对于每一种可能的decode办法，有corner case需要考虑：
3. 如果第i个数是0，那么只可能是dp[i - 2],并且要检查i - 1 和i拼成的数是否在10 ~ 26范围内, 比如120只可能是[1, 20]的分割
4. 检查数是否在10 ~ 26范围内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int numDecodings(String s) {
	
    if (s == null || s.length() == 0) {
        return 0; // empty string has no way of decoding
    }
    
    int[] dp = new int[s.length()];
    
    dp[0] = s.charAt(0) == '0'?0: 1;
    
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) != '0') {
            dp[i] = dp[i - 1];
        }
        
        int temp = Integer.parseInt(s.substring(i - 1, i + 1));
        if (temp >= 10 && temp <= 26) {
            if (i == 1) {
                dp[i] += 1;
            } else {
                dp[i] += dp[i - 2];
            }
        }
        if (dp[i] == 0) {
            return 0;
        }
    }
    return dp[s.length() - 1];    
}

问题来源于一份Top 50 Questions related to Market Risk. 试着回答了一部分问题，希望对准备面试有所帮助。

Risk Measures

1. How would you calculate Value at Risk (VaR)?

   There are three methods to calculate VaR.

   1. Delta-Normal Method (Parametric Method)

      • Assume the distribution of underlying asset returns.
      • Go back on time for over N years and collect asset returns’ data.
      • Fit the data into the assumed distribution and calculate the VaR as the Xth percentile.
      • For example, a one-day 5% VaR is just the 5th percentile of the underlying return’s distribution.

   2. Historical-Simulation Method

      • Assume historical path will be a guidence of what will happen in the future
      • Go back on time for over N years and collect portfolio’s data (close price).
        • Each historical period is considered a scenario
      • Given current portfolio’s value, forecast the next period’s value based on each scenario
      • Once portfolio’s value is calculated for each period, calculate the sample Nth percentile as the VaR

   3. Monte-Carlo Method

      • Assume a stochastic process for each market variable (distribution and parameters)
        • parameters can be estimated from historical data
      • Simulate the data path for all variables of interest
      • Revalue the portfolio by the new market variables and calculate the value difference

      • Calculate the Nth percentile as the VaR value.

      • For example, we can assume all market variables changes are generated from a multivariate normal distribution

      • Then each step will involve generating data from the multivariate distribution and revalue the portfolio based on that

2. What’s wrong with VaR as a measurement of risk?

   • It does not describe the loss on the left tail. When the return distribution is far from a normal distribution, it does not face real risk
     • Example: short CDS of a 3% default rate with 0 recovery rate bond, 95% VaR is 0 (which doesn’t reflect the risk at all)
   • It is not a coherent measure and is not sub-additive.
     • It means when we combine two positions, we do not always have VaR(C) <= VaR(A) + VaR(B)
     • Example: two short CDS positions with 3% default rate and 0 recovery rate bond:
       one of the bond default rate is 1 - (1 - 3%)*(1 - 3%) = 5.9%, so VaR(C) > Var(A) + VaR(B)
       This contradicts the idea that diversification reduces risks.

3. What is non-Linear VaR? How would you calculate it?
   Non-linear VaR reflects that the portfolio contains nonlinear derivatives which the payoff or the response to the risk factor is non-linear.
   It is often calculate by using the monte carlo simulation of pricing model.

4. What is the parametric method of calculating VaR? What are its advantages?
   The parametric method is the delta-normal method described in Q1.
   The advantage is it is simple to calculate. It just need to estimate the joint distribution and
   calculate the portfolio return’s distribution using either linear or nonlinear model.

   • Non-linear model is called: Cornish-Fisher expansion (P448 on John Hull)

5. What is the historical method of calculating VaR? What are its advantages?
   Second Method described in Q1.
   Advantage is it is a nonparametric method and the historical data determines the joint probability distribution of market variables.

6. Why would you calculate VaR using Monte Carlo simulations?
   If the portfolio is consisting nonlinear derivatives, such as options, the return profile of the portfolio is non symmetric.
   VaR is very sensitive to the left tail of the distribution so in this case we need to use monte carlo simulation to better model the nonlinear characterics.

7. What are the challenges in calculating VaR for a mixed portfolio?
   Nonlinearity? [NOT finished yet]

8. What’s GVAR? How can you calculate it?
   GVAR = Global vector autoregression Model

9. What is the one-day VaR of a $50m portfolio with a daily standard deviation of 2% at a 95% confidence level? What is the annualized VaR?

   • One day VaR = 50m * 0.02 * 1.96 ~= 2m
   • Annualized VaR = sqrt(252) * 2m = 16 * 2m = 32m

10. What do you know about extreme value theory?

    • A framework to study the tail behavior of a distribution
    • https://en.wikipedia.org/wiki/Extreme_value_theory

11. What is Expected Shortfall? How is it calculated? Why is it considered better than VaR? What are the disadvantages?

    • Expected shortfall is also called conditional value at risk
    • It measures the expected loss under a certain amount.
    • It can be calculated by a list of scenarios.
      • Each scenarios has the probability of occurrence and the return
      • Given a threshold, calculate the probablity of each scenario that happen with odds less than the threshold
      • Cacluate the expected (averaged) loss.
    • Advantage：
      1. It is a coherent measure and a more complete measure of downside risk
         • Reflect the sknewness (asymmetry) and kurtosis (fat tail)
    • Disadvantage:
      1. It treats a large probability of small loss as equivalent to a small probability of large loss
      2. Difficult to forecast

12. What is incremental default risk?
    Default risk incremental to what is calculated through the Value-at-risk model,
    which often does not adequately capture the risk associated with illiquid products.

Yield Curve

1. What are the uses of the yield curve?
   Yield curve depicts the relationship between bond yield and its maturities. It is used to:

   1. Forecasting interest rate
   2. Pricing bond
   3. Create strategies to boost total returns

2. What’s the riskiest part of the yield curve?
   The riskiest part is either a flattening or steepening of the yield curve.
   It reflects yield changing among comparable bonds with different maturities.

3. What does it mean for risk when the yield curve is inverted?
   When the yield curve is inverted, it is often viewed as an pending economic recession.
   In this case, people tend to have negative view in long term so the price of long term bond is bidding up.

4. What is the discount factor? How would you calculate it?
   Discount factor is the present value of a unit of currency delivered at a future time T.

5. What is convexity? How would you calculate it? Why is it important?
   Convexity is the second derivatives of bond price relative to the interest rate.
   Convexity measures the curvature of price-yield curve. It is a key aspect when measure interest rate risk.

6. What’s the relationship between coupon rate and convexity?
   convexity decrease as coupon rate increase.
   Zero-coupon bond have the highest convexity compared to other bond with the same duration and yield to maturity.

7. What’s the meaning of duration? Is it constant for all yields?
   Duration is the sentivity of bond price relative to interest rate. (First derivative)
   It is not constant for all yield since price-yield curve has curvature.

8. What’s the meaning of partial duration?
   It’s also called key rate duration. It measures the bond price change relative to a set of rates with specific maturities.
   It does not assume parallel shift in yield curve.

9. What are the limits of duration as a risk measure?
   It assumes the parallel shift in yield curve and it ignores the curvature.

10. How would you decide which discount curve to use to value future cash flows from interest rate swaps?

Questions on quantitative concepts:

1. Can you explain the assumptions behind Black Scholes?

2. What’s a volatility smile? Why does it occur? What are the implications for Black Scholes?

3. What are the Greeks?

4. How are the main Greeks derived?

5. What do you know about jump processes?

6. Should you use implied standard deviation or historical deviation to forecast volatility? Explain your choice.

Hedging

1. What is delta hedging?

2. How would you hedge against a particular equity/bond under current market conditions?

3. When can hedging an options position mean that you take on more risk?

4. An option is at the money. How many shares of stock should you hold to hedge it?

Questions on particular products:

1. What is interest rate risk?
   The effect on your portfolio value when interest rate changes.

2. What is reinvestment risk?
   If you have cash flow generated from your portfolio and the market interest rate is changing, you have the reinvestment risk.
   That means you may have to reinvest your proceedings at a lower/higher market preceding rate.

3. How do interest rate risk and reinvestment risk interact?
   Reinvestment risk is more likely when interest rates are declining.
   Reinvestment risk affects the yield-to-maturity of a bond,
   which is calculated on the premise that all future coupon payments will be reinvested at the interest rate in effect when the bond was first purchased.

4. Which bond has the greatest associated interest rate risk? A five year zero coupon bond? Or a five year bond that pays coupons?
   zero coupon bond has the highest duration and thus has the greatest interest rate risk.

5. Which is more volatile, a 20-year zero coupon bond or a 20-year 4.5% coupon bond?
   20-year zero coupon bond.

6. What are the risks inherent in an interest rate swap?

Regulation

1. How has Basel III changed the treatment of market risk?

2. What the implications of Basel IIIs new trading book rules for market risk professionals?

3. How could the Basel III treatment of trading books be improved?

4. How will trading businesses change as a result of Basel III capital rules for banks’ trading books?

5. What are the key requirements of the Basel stress testing framework? Are they sufficiently stringent?

6. Which extreme events should stress tests be taking into consideration now?

7. Why is Basel II blamed for precipitating the 2008 financial crisis?

折腾了一晚上，还是没有搞定，研究了一下似乎是我用的theme: maupassant-hexo 暂时不支持mathjax.
搜索了一圈发现这篇文章有解决办法，并且指出了一个人fork了maupassant-hexo并对它加入了支持。暂时还没有尝试，先记录下来。