[Autumn Recruitment Breakthrough] 2024 Autumn Recruitment Written Examination-ByteDance Written Examination Questions-01-Three Language Questions (Java/Cpp/Python)

2024-07-12

🍭 大家好这里是Senior Qinglong , a programmer who loves algorithms

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

✨ This series intends to be continuously updated Autumn recruitment written test questions
👏 感谢大家的订阅➕ 和喜欢💗

📧 清隆这边最近正在收集近一年半互联网笔试题汇总，有需要的小伙伴可以关注 End of the article Princess number pick up

Final Thoughts
- 🎧 秋招陪伴刷题打卡
- ✈️ A comprehensive collection of written test questions

insert image description here

🎀 01.A先生的环形花圃

Title Description

Mr. A has a circular flower garden, which is divided into $n$ Initially, Mr. A selected three areas in the flowerbed to plant roses.

Now, Mr. A wants to move the flower garden toBalanced state。

Balanced state: The distance between any two rose planting areas is not less than $k$ (The distance between adjacent areas is $1$ ）。

Move operation: Exchange the states of adjacent regions (rose region becomes empty region, empty region becomes rose region).

At the same time, Mr. A is a person who pays great attention to efficiency, so he hopes that you can use the least number of moves to make the flower garden reach a balanced state.

Input Format

Enter a positive integer in the first line $t$ , indicating the number of inquiries.

Next Steps $t$ Lines, each containing five positive integers $n$ 、 $k$ 、 $a_1$ 、 $a_2$ 、 $a_3$ , which represent the number of flower bed areas, the required minimum distance, and the initial positions of the three rose areas.

Output Format

Output $t$ Each line outputs an integer, which represents the minimum number of exchanges required to make the garden reach equilibrium. If equilibrium cannot be reached, then output $- 1$ 。

Sample Input

Sample Output

data range

$10^4$
$10^9$
$a_1, a_2, a_3 leq n$

answer

This problem can be solved by analyzing the conditions of equilibrium.

First, if the minimum distance required $k$ Exceeds the number of flower garden areas $n$ One third of , the condition cannot be met anyway, and the output $- 1$ 。

Otherwise, we can first sort the positions of the three rose regions and then calculate the distances between adjacent rose regions. Next, for each distance, if it is less than $k$ , then a move operation is required, and the number of moves is $k$ The difference from this distance.

Finally, when all distances meet the requirements, the flower garden reaches a balanced state, and the total number of moves can be output.

The time complexity is $O (t lo g t)$ , the space complexity is $O (1)$ 。

Reference Code

Python

t = int(input())

for _ in range(t):
    n, k, *a = map(int, input().split())
    a.sort()

    if k * 3 > n:
        print(-1)
        continue

    b = [a[1] - a[0], a[2] - a[1], n - a[2] + a[0]]
    ans = sum(max(0, k - d) for d in b)

    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] a = new int[3];
            for (int i = 0; i < 3; i++) {
                a[i] = sc.nextInt();
            }

            Arrays.sort(a);

            if (k * 3 > n) {
                System.out.println(-1);
                continue;
            }

            int[] b = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
            int ans = 0;
            for (int d : b) {
                ans += Math.max(0, k - d);
            }

            System.out.println(ans);
        }
    }
}
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
31
32
33

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k, a[3];
        cin >> n >> k >> a[0] >> a[1] >> a[2];

        sort(a, a + 3);

        if (k * 3 > n) {
            cout << -1 << endl;
            continue;
        }

        int b[] = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
        int ans = 0;
        for (int d : b) {
            ans += max(0, k - d);
        }

        cout << ans << endl;
    }

    return 0;
}
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
31

🪐 02.卢小姐的音游金币

Problem Description

Miss Lu has recently become addicted to a piano-based music game. In the game, each piano tile has a number, with the smallest number being $1$ If you hit five piano tiles with increasing numbers in a row, you will get a gold coin.

For example, if Ms. Lu hits the numbered 1, 2, 3, 4, 5, 6 Piano tiles, then for1, 2, 3, 4, 5 If she gets five blocks with increasing numbers, she will get a gold coin.

When a level has been completed for a long time, the number will be reset. $1$ So for one level, there may be multiple piano tiles with the same number but different tiles.

Note that here you only need to have five piano tiles with increasing numbers in the same level to get gold coins.

Because Miss Lu is so strong, she has passed four levels. Now we give Miss Lu's four levels of difficulty. $A$ 、 $B$ 、 $C$ and $D$ According to the number of the piano tile hit, how many gold coins can Miss Lu get in these four levels?

Input Format

The first line contains a positive integer $n$ （ $10^5$ ), represents the total number of piano tiles hit by Miss Lu in the four levels.

Next $n$ Each line contains three parameters: $a_i$ 、 $b_i$ （ $a_i, b_i leq 10^9$ )and $c_i$ （ $c_i in {'A', 'B', 'C', 'D'}$ ), representing the number, quantity and level of each piano tile.

Output Format

Output an integer representing the total number of gold coins that Ms. Lu can obtain.

Sample Input

Sample Output

3
1

Sample Description

For levels $A$ ,first 1, 2, 3, 4, 5 You can get a gold coin, then2, 3, 4, 5, 6 You can get another gold coin.

For levels $B$ ，7, 8, 9, 10, 11 You can get a gold coin.

Therefore, the total $3$ gold coins.

Sample Input 2

Sample Output 2

0
1

Sample Description 2

In the level $C$ In the game, it is impossible to get five consecutive increasing numbers, so the number of gold coins is $0$ 。

data range

$10^5$
$a_i, b_i leq 10^9$
$c_i in {'A', 'B', 'C', 'D'}$

answer

This problem can be solved using hash tables and sorting. The specific ideas are as follows:

Using Hash Table cnt Record the number of times each number appears in each level. The key is a combination of the level character and the number, and the value is the number of times the number appears in the level.
Sort the input data by level letter and number, making sure the numbers of the same level are consecutive.
Traverse the sorted data, and for each number, determine whether the five consecutive numbers exist in the current level. If so, take the minimum number of occurrences of these five numbers, count it as the answer, and subtract the minimum number of occurrences of these five numbers from each number.
The final answer is the sum of all the gold coins that meet the conditions.

The time complexity is $O (n lo g n)$ , the space complexity is $O (n)$ 。

Reference Code

Python

from collections import defaultdict
import sys

def solve():
    n = int(input())
    cnt = defaultdict(int)
    vec = []

    for _ in range(n):
        a, b, c = input().split()
        a, b = int(a), int(b)
        cnt[c + str(a)] += b
        vec.append((c, a))

    vec.sort()

    ans = 0
    for v in vec:
        arr = [v[0] + str(v[1] + i) for i in range(5)]
        t = min(cnt[a] for a in arr)
        ans += t
        for a in arr:
            cnt[a] -= t

    print(ans)

if __name__ == '__main__':
    solve()
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

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Map<String, Integer> cnt = new HashMap<>();
        List<int[]> vec = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            String c = input[2];
            String key = c + a;
            cnt.put(key, cnt.getOrDefault(key, 0) + b);
            vec.add(new int[]{c.charAt(0), a});
        }

        vec.sort((x, y) -> {
            if (x[0] != y[0]) {
                return x[0] - y[0];
            }
            return x[1] - y[1];
        });

        long ans = 0;
        for (int[] v : vec) {
            String[] arr = new String[5];
            for (int i = 0; i < 5; i++) {
                arr[i] = (char) v[0] + String.valueOf(v[1] + i);
            }
            int t = Integer.MAX_VALUE;
            for (String a : arr) {
                t = Math.min(t, cnt.getOrDefault(a, 0));
            }
            ans += t;
            for (String a : arr) {
                cnt.put(a, cnt.get(a) - t);
            }
        }

        System.out.println(ans);
    }
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    map<string, ll> cnt;
    vector<pair<string, int>> vec;

    for (int i = 1; i <= n; i++) {
        int a, b;
        string c;
        cin >> a >> b >> c;
        cnt[c + to_string(a)] += b;
        vec.push_back({c, a});
    }

    sort(vec.begin(), vec.end());

    ll ans = 0;
    for (auto& v : vec) {
        vector<string> arr;
        for (int i = 0; i < 5; i++) {
            arr.push_back(v.first + to_string(v.second + i));
        }
        ll t = LLONG_MAX;
        for (auto& a : arr) {
            t = min(t, cnt[a]);
        }
        ans += t;
        for (auto& a : arr) {
            cnt[a] -= t;
        }
    }

    cout << ans << endl;

    return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

✨ 03. Miss Lu’s unique garden

Problem Description

Miss Lu has a length of $n$ The garden is planted with $n$ Different kinds of flowers. Each flower has a beauty value. $a_i$ 。

Miss Lu believes that a beautiful garden should be unique, that is, $n - 1$ The beauty value of the flowers planted is the same, only $1$ The beauty value of the planted flower is different from other flowers.

Each time, Ms. Lu can choose a flower and add its beauty value. $1$ or minus $1$ 。

Now, Miss Lu wants to know how many operations are needed to make the garden unique.

Input Format

The first line contains a positive integer $n$ , indicating the length of the garden.

The second line contains $n$ positive integer $a_1, a_2, ldots, a_n$ , indicating the beauty value of each flower.

Output Format

Output an integer representing the minimum number of operations required to make the garden unique.

Sample Input

Sample Output

2
1

data range

$10^5$
$a_i leq 10^9$

answer

The optimal solution is to become the median, enumerate all the costs of becoming the median

The time complexity is $O (n lo g n)$ , the space complexity is $O (n)$ 。

Reference Code

Python

def main():
    n = int(input())
    w = list(map(int, input().split()))
    w.sort()
    if w[0] == w[n - 1]:
        print("1")
        return
    s1, s2 = 0, 0
    m1, m2 = w[(n - 1) // 2], w[(n + 1) // 2]
    for i in range(n - 1):
        s1 += abs(m1 - w[i])
    for i in range(1, n):
        s2 += abs(m2 - w[i])
    print(min(s1, s2))

if __name__ == "__main__":
    main()

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

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++)
            w[i] = scanner.nextInt();
        Arrays.sort(w);
        if (w[0] == w[n - 1]) {
            System.out.println("1");
            return;
        }
        long s1 = 0, s2 = 0;
        int m1 = w[(n - 1) / 2], m2 = w[(n + 1) / 2];
        for (int i = 0; i < n - 1; i++)
            s1 += Math.abs(m1 - w[i]);
        for (int i = 1; i < n; i++)
            s2 += Math.abs(m2 - w[i]);
        System.out.println(Math.min(s1, s2));
    }
}

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 100010;

int main() {
    int n, w[N];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];
    sort(w, w + n);
    if (w[0] == w[n - 1]) {
        cout << "1" << endl;
        return 0;
    }
    ll s1 = 0, s2 = 0;
    int m1 = w[(n - 1) / 2], m2 = w[(n + 1) / 2];
    for (int i = 0; i < n - 1; i++)
        s1 += abs(m1 - w[i]);
    for (int i = 1; i < n; i++)
        s2 += abs(m2 - w[i]);
    cout << min(s1, s2) << endl;
    return 0;
}

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

🥝 04.LYA的字符画

Title Description

LYA has recently become fascinated by character paintings. She believes that the beauty of a character painting is equal to the number of consecutive identical symbols in the character painting. For example, the beauty of the character painting "aabbccddef" is $6$ 。

LYA's friend gave her a $0$ and $1$ LYA, who has become obsessed with character painting, wants to know all the characters in this string.SubstringWhat is the sum of the beauty of ?

Note: Total $C^{2}_{n+1}$ Substrings.

Input Format

Enter a positive integer in the first line $n$ , indicating the length of the string.

The second line has a length of $n$ of $01$ String.

Output Format

Output an integer representing the sum of the beauty of all substrings.

Sample Input

Sample Output

14
1

data range

$10^5$

answer

This problem can be solved by the idea of prefix sum.

First, we can calculate the total number of substrings of a string, that is $n ( n + 1 ) 2 frac{n(n+1)}{2}$ 。

Then, we loop through the string, using the variable $l$ Record the starting position of the current consecutive identical symbols, variable $r$ Record the current location. $s [r] \neq = s [r - 1]$ , indicating the appearance of a new symbol, we can calculate $[l, r)$ The number of substrings in the interval, i.e. $( r − l ) ( r − l + 1 ) 2 frac{(r-l)(r-l+1)}{2}$ , subtract it from the total number of substrings.

Finally, what's left is the number of all beautiful substrings, which can be output.

time complexity $O (n)$ , space complexity $O (1)$ 。

Reference Code

Python

def cal(length):
    return length * (length + 1) // 2

n = int(input())
s = input() + '#'

ans = 0
total = cal(n)
l = 0
for r in range(1, n + 1):
    if s[r] != s[r - 1]:
        ans += total - cal(l) - cal(n - r)
        l = r

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next() + "#";
        
        long ans = 0;
        long total = cal(n);
        int l = 0;
        for (int r = 1; r <= n; r++) {
            if (s.charAt(r) != s.charAt(r - 1)) {
                ans += total - cal(l) - cal(n - r);
                l = r;
            }
        }
        System.out.println(ans);
    }
    
    private static long cal(int len) {
        return (long) len * (len + 1) / 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

#include <iostream>
#include <string>

using namespace std;

using ll = long long;

ll cal(int len) {
    return (ll) len * (len + 1) / 2;
}

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s += "#";
    
    ll ans = 0;
    ll total = cal(n);
    int l = 0;
    for (int r = 1; r <= n; r++) {
        if (s[r] != s[r - 1]) {
            ans += total - cal(l) - cal(n - r);
            l = r;
        }
    }
    cout << ans << endl;
    
    return 0;
}
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
31

🌸 05.卢小姐的数组删除计划

Title

Problem Description

Miss Lu has a very grand plan, she wants to delete all the arrays in the world! But her ability is limited, she can only select two identical elements in the array at a time and delete all the elements between them (including the two elements themselves).

Now, Miss Lu has a length of $n$ Array $a$ , she wants to know the maximum number of elements she can delete from the array.

Input Format

The first line contains a positive integer $n$ , which represents an array $a$ length.

The second line contains $n$ Space-separated positive integers $a_1, a_2, ldots, a_n$ , which represents an array $a$ Elements.

Output Format

Output an integer representing the maximum number of elements that Ms. Lu can delete.

Sample Input

Sample Output

1
1

data range

$10^5$
$a_i leq 10^9$

answer

This problem can be solved using the idea of sorting and double pointers.

First, we can transform the array $a$ The elements in are sorted by value, and the original position of each element in the array is recorded. The purpose of this is to facilitate us to find the position range of the same elements.

Next, we can iterate over the sorted array and, for each element, find the range of positions of all elements with the same value as it. $[L, R]$ . All elements in this range can be deleted because they are between two identical elements in the original array. We can calculate the range $[L, R]$ The number of elements in $R - L - 1$ , compare it with the current maximum number of deleted elements and update the maximum value.

Finally, just output the maximum number of deleted elements.

The time complexity is $O (n lo g n)$ , mainly the time complexity of sorting. The space complexity is $O (n)$ , used to store the original position of the element.

Reference Code

Python

n = int(input())
a = list(map(int, input().split()))

idx = sorted(range(n), key=lambda x: a[x])

ans = 0
i = 0
while i < n:
    j = i
    L, R = n, -1
    while j < n and a[idx[j]] == a[idx[i]]:
        L = min(L, idx[j])
        R = max(R, idx[j])
        j += 1
    ans = max(ans, R - L - 1)
    i = j

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

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            idx[i] = i;
        }

        Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));

        int ans = 0;
        for (int i = 0; i < n;) {
            int j = i;
            int L = n, R = -1;
            while (j < n && a[idx[j]] == a[idx[i]]) {
                L = Math.min(L, idx[j]);
                R = Math.max(R, idx[j]);
                j++;
            }
            ans = Math.max(ans, R - L - 1);
            i = j;
        }

        System.out.println(ans);
    }
}
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
31
32

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> idx(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        idx[i] = i;
    }

    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return a[i] < a[j];
    });

    int ans = 0;
    for (int i = 0; i < n;) {
        int j = i;
        int L = n, R = -1;
        while (j < n && a[idx[j]] == a[idx[i]]) {
            L = min(L, idx[j]);
            R = max(R, idx[j]);
            j++;
        }
        ans = max(ans, R - L - 1);
        i = j;
    }

    cout << ans << endl;

    return 0;
}
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
31
32
33
34
35
36
37
38

Final Thoughts

Here I would like to recommend to you the check-in room for the autumn recruitment organized by my senior. It will guide you through solving common Internet written test questions step by step in 31 days, and every day is full of useful information.

🎧 秋招陪伴刷题打卡

Preview:

[Autumn Recruitment Question Punch Card] Day01-Custom Sorting-CSDN Blog

[Autumn Recruitment Question Punch Card] Day 02-The Strongest Binary Search Series-Binary Search-CSDN Blog

[Autumn Recruitment Question Punch Card] Day03-The Strongest Two-Point Series-Two-Point Answers-CSDN Blog

We provide online evaluation of past factory real questions. Interested friends can send a private message to Qinglong for details.

insert image description here

And more! And more! And more!

✈️ A comprehensive collection of written test questions

insert image description here

Technology Sharing