This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Received the interview invitation three days after the exam. Frontend requirements aren’t too high.

• Short answer: 1 question (10 bonus points)
  • Asked about design patterns. Write two structural/behavioral design patterns, including principles, use cases, and personal understanding.
• Programming: 4 problems
  • Monster Fighting (AC 100%)
  • Maximum Score of a String (25 points, AC 37.5%)
  • Constructing a Complete Binary Tree (25 points, not attempted, 0%)
  • Shortest Time to Exit the Map (30 points, AC 100%)

Monster Fighting (20 points, AC 100%)

Two monsters with health values a and b. You have two skills:

• Single target attack with damage x
• AoE attack with damage y
• Given a, b, x, y, find the minimum number of skills needed to kill both monsters.

Sample Input: 5 3 3 2 Sample Output: 3

Sample Input 2: 20 20 5 2 Sample Output 2: 8

Sample Input 3: 20 20 1 2 Sample Output 3: 10

Approach

DFS with pruning and it passes. Alternatively, greedy works too.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a, b, x, y;
int dfs(int a, int b, int cnt) {
    if(a <= 0 && b <= 0) return cnt;
    else if(a <= 0) a = 0;
    else if(b <= 0) b = 0;
    int higher = max(a, b);
    if(y >= x) return higher%y == 0? higher/y: (higher/y)+1;
    int minx;
    if(a <= 0) minx = dfs(a, b-x, cnt+1);
    else if(b <= 0) minx = dfs(a-x, b, cnt+1);
    else minx = min(dfs(a-x, b, cnt+1), dfs(a, b-x, cnt+1));
    int miny = dfs(a-y, b-y, cnt+1);
    return min(minx, miny);
}
int main() {
    cin >> a >> b >> x >> y;
    cout << dfs(a, b, 0) << endl;
    return 0;
}

Maximum Score of a String (25 points, AC 37.5%)

Given a string of all lowercase letters, if two adjacent letters are equal or adjacent in the alphabet, they can contribute a score. ‘a’ contributes 1 point, ‘b’ contributes 2 points… ‘z’ contributes 26 points. Each letter can only be used once. Input “aca” Output 0, because adjacent letters are neither adjacent in the alphabet nor equal. Input “abb” Output 4, because ab scores 3, bb scores 4, but each letter can only be used once, so choose bb.

Approach

Alright, my approach was completely wrong so I won’t post my code. Here’s the approach from others:

• dp[0][i] represents the maximum score without marking the i-th letter.
• dp[1][i] represents the maximum score when marking the i-th letter.
• Transition equations:
  • dp[0][i] = max(dp[0][i-1], dp[1][i-1]) — if not marked, it’s the max score from the previous position.
  • dp[1][i] = max(dp[1][i-1], (dp[0][i-1]+ s[i]-'a'+1 +s[i-1]-'a'+1)*(abs(s[i]-s[i-1]) <= 1)) — if marked, it’s the max of (previous marked max score, previous unmarked max score + score from marking these two letters).

Constructing a Complete Binary Tree (25 points, not attempted)

Given an integer n, use the numbers 1, 2, 3…n to construct a complete binary tree such that the product of every node and its parent is even (except the root, which has no parent). Output the level-order traversal result of the constructed tree. The answer is not unique. Input 4, Output 1 2 4 3

Approach

Saw an approach that said it’s just simulation: put all odd numbers at the leaf nodes, then fill in the rest anywhere.

Shortest Time to Exit the Map (30 points, AC 100%)

Given two integers m and n representing a map with m rows and n columns. The map contains 0s and 1s, where 0 represents land and 1 represents swamp.

• Moving from land to land or swamp to swamp costs 1 unit of time
• Moving from land to swamp or swamp to land costs 2 units of time
• Same type costs 1, different type costs 2
• You can only move down, left, or right. Find the minimum time to move from the top-left corner to the bottom-right corner. Example: Input

3 3
1 0 0
1 1 1
0 0 1

Output

4

Approach

• Since you can only move down, left, and right, and moving left never reduces time (so there’s no reason to go left), just use DP. Record the minimum time from the top and left of the current position.

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 510;
int n, m;
int map[maxn][maxn];
int dp[maxn][maxn];
int main() {
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j)
            cin >> map[i][j];
    }
    for(int i = 1; i < n; ++i)
        dp[i][0] = dp[i-1][0] + (map[i-1][0] == map[i][0] ? 1: 2);
    for(int i = 1; i < m; ++i)
        dp[0][i] = dp[0][i-1] + (map[0][i-1] == map[0][i] ? 1: 2);
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            int top = dp[i-1][j] + (map[i-1][j] == map[i][j] ? 1: 2);
            int left = dp[i][j-1] + (map[i][j-1] == map[i][j] ? 1: 2);
            dp[i][j] = min(top, left);
        }
    }
    cout << dp[n-1][m-1] << endl;
    return 0;
}