Received an interview invitation email after completing the written test on the third day. The requirements for the front-end position are not high.
- 1 Essay Question (10 bonus points)
- Asked about design patterns, write two structural/behavioral design patterns, including principles, use cases, and personal understanding.
- 4 Programming Questions
- Monster Fight (AC 100%)
- Maximum Score of a String (25 points, AC 37.5%)
- Construct Complete Binary Tree (25 points, not done yet, 0%)
- Shortest Time to Exit the Map (30 points, AC 100%)
Monster Fight (20 points, AC 100%)#
There are two monsters with life values a and b. You have two skills:
- One is a single-target attack with damage x.
- The other is an area-of-effect attack with damage y.
Given a, b, x, and y, find the minimum number of skills required to kill both monsters.
Input example: 5 3 3 2
Output example: 3
Input example 2: 20 20 5 2
Output example 2: 8
Input example 3: 20 20 1 2
Output example 3: 10
Approach#
DFS pruning can solve the problem. Alternatively, a greedy approach can be used (.
#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 consisting of only lowercase letters, if two adjacent letters in the string are equal or have adjacent positions in the alphabet, they can contribute to the 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 there are no adjacent letters that are adjacent in the alphabet or equal.
Input "abb" Output 4 because the score for "ab" is 3 and the score for "bb" is 4, but each letter can only be used once, so "bb" is chosen.
Approach#
Well, my approach was completely wrong, so I won't include the code. Here's the approach from the expert:
dp[0][i]represents the maximum score without marking the i-th letter.dp[1][i]represents the maximum score with marking the i-th letter.- The transition equations are as follows:
dp[0][i] = max(dp[0][i-1], dp[1][i-1])If not marked, it is the maximum score of the previous state.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 is the maximum score of the previous marked state or the maximum score of the previous unmarked state plus the score after marking these two letters.
Construct Complete Binary Tree (25 points, not done yet)#
Given an integer n, use the numbers 1, 2, 3, ..., n to construct a complete binary tree, where the product of each node and its parent is even (except for the root node, as it has no parent). Output the result of the level order traversal of the constructed binary tree. The answer is not unique.
Input 4 Output 1 2 4 3
Approach#
Some approaches suggest that it is a simulation problem, where odd numbers are placed in leaf nodes and the remaining numbers can be placed randomly.
Shortest Time to Exit the Map (30 points, AC 100%)#
Given two integers m and n, representing an m x n map composed of 0s and 1s, where 0 represents land and 1 represents a swamp:
- Moving from land to land or from swamp to swamp takes 1 unit of time.
- Moving from land to swamp or from swamp to land takes 2 units of time.
- In other words, the same terrain takes 1 unit of time, while different terrains take 2 units of time.
- You can only move down, left, or right at a time. Find the minimum time required 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, or right, and moving left does not reduce the time, there is no need to move left at all. Therefore, we only need dynamic programming (DP) to record the minimum time from the upper side and the left side 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;
}