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.

JD.com written exam review. A frontend development exam with 30 multiple-choice questions and two programming problems (happened to be on the same day as the 360 exam. Two written exams in one day, what a pain.)

Multiple Choice (30 questions)

Covered everything — databases, calculus, equations, with more frontend questions in the second half.

Programming Problem 1 - Xiao Ming’s Maximum Value (AC 100%)

Xiao Ming has a machine. Each time you input a number, it returns a non-negative integer. After many experiments, Xiao Ming discovered that if you give the machine a number x, it returns the remainder of x divided by P, denoted as y. P is engraved on the bottom of the machine and Xiao Ming can see it.

For example, when P=5, inputting x=9 returns 4, and inputting 15 returns 0.

Xiao Ming can now input all integers in the closed interval [L,R]. What is the maximum return value Xiao Ming can get from the machine?

Input Description Multiple test cases. The first line contains a number T indicating the number of test cases.

The next three lines each contain T integers L[i], R[i], P[i], representing the left endpoint, right endpoint, and machine parameter P for the i-th test case.

Output Description Output one line with T numbers, each representing the answer for the corresponding test case.

Sample Input

2
5 1
6 2
5 7

Sample Output

1 2

Hint First test case: inputting 5 gives 0, inputting 6 gives 1, so the answer is 1.

Second test case: inputting 1 gives 1, inputting 2 gives 2, so the answer is 2.

Approach

Obviously, the problem asks to find an x in the range L~R that maximizes x%p. Check whether L/p equals R/p. If they’re equal, the answer is definitely R%p. Otherwise, a full remainder cycle has already occurred, so the maximum remainder is p-1.

Code

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 70005;
int T;
int L[maxn], R[maxn], P[maxn];
vector<int> ans;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    for(int i = 0; i < T; ++i)
        cin >> L[i];
    for(int i = 0; i < T; ++i)
        cin >> R[i];
    for(int i = 0; i < T; ++i)
        cin >> P[i];
    for(int i = 0; i < T; ++i) {
        int l = L[i], r = R[i], p = P[i];
        if(l/p == r/p) ans.push_back(r%p);
        else ans.push_back(p-1);

    }
    for(int i = 0; i < T; ++i) {
        if(i == 0) cout << ans[i];
        else cout << ' ' << ans[i];
    }
    cout << endl;
    return 0;
}

Programming Problem 2 - Splitting Eggs (AC 73%)

In plain English: Starting value x. Each step allows one of two operations:

• ++x
• if(x%3 == 0) x /= 3 Find the minimum number of steps to transform x into y. Here are some custom test cases: Sample 1

3
102 1
312 12
23 10

10
5
4

Sample 2

4
210 4
121 3
312 102
281 200

8
10
70
108

Sample 3

4
299 298
31 100
8 1
900100000000000000 20000200000100000

200
69
3
8887854321087664

Alright, let’s analyze.

Approach

Each time, try to do x/=3 as much as possible. If x/3 would be less than y, add up to the target number. If after x/=3 the result is not divisible by 3 and is greater than y, add 1~3 to make it divisible by 3, then continue dividing. In the end it wasn’t TLE but WA. I couldn’t figure out where the boundary issue might be. Passed 73%.

Code

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 70005;
typedef long long ll;
int T;
ll x, y;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> x >> y;
        ll cnt = 0;
        while(x != y) {
            while (x != y && x % 3 == 0 && x/3 >= y) {
                x /= 3;
                ++cnt;
            }
            if(x == y) break;

            if(x % 3 == 0) x /= 3,++cnt;
            if(x < y) { // 加到目标数
                cnt += y-x;
                break;
            } else {
                while(x != y && x % 3 != 0) {   // 最多加三次
                    ++x, ++cnt;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}