Meituan machine test in 2022

evaluation

Overall speaking , Less difficult than other companies , Multiple choice questions only 3 topic , It's all machine learning , And there is a problem , Semi supervision is taken from textbooks .

Programming problems 4 The overall difficulty of Tao is not high , I don't know what to do ,AC 了 72%, Everything else passed .

Programming questions

subject 1

n Number , find [k-1,k+1] The number of digits contained in the interval with the largest number of digits in the range .

Input n, Second line input n Number , Each number range is 1-100.

Example

6
1 2 2 3 5 5
Output

4

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){
	int n;
	cin >> n;
	//vector<int> arr;
	map<int, int> counts;
int minVal = 100, maxVal = 0;
	for(int i = 0; i < n; i++){
		int value;
		cin >> value;
		counts[value]++;
		if(value > maxVal) maxVal = value;
		if(value < minVal) minVal = value;
	}
	int res = 0;// minVal = arr[0], maxVal = arr[n - 1]
	for(int cur = minVal; cur < maxVal; cur++){
		int tempcount = counts[cur-1] + counts[cur] + counts[cur+1];
		res = max(tempcount, res);
	}
	cout << res;
} 

subject 2

from （0,0） To （n,m), Try to walk 'o' Way , Can only move down and right , The calculation needs to go through at least a few 'x'. The essence is 《 The finger of the sword offer》13 be similar .

Example

5 5
oxxxx
xxoox
oooxo
xxxxo
ooooo
Output

2

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main(){
	int m,n;
	cin >> n >> m;
	vector<vector<int>> weight(n, vector<int>(m, 0));
	char c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m;j++){
			cin >> c;
			if(c == 'x') weight[i][j] = 1; 
		}
	}
	vector<vector<int>> sum(n, vector<int>(m, 50000));
	sum[0][0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m;j++){
			if(i > 0) sum[i][j] = min(sum[i][j], sum[i-1][j] + weight[i-1][j]);
			if(j > 0) sum[i][j] = min(sum[i][j], sum[i][j-1] + weight[i][j-1]);
		}
	}
	cout << sum[n-1][m-1]; 

}

subject 3

The essence is to replace letters to maximize the length of consecutive characters leetcode 424, Similar problems have appeared in other companies .

Example

10 2

--++--+++-
Output

7

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main(){
	int n,k;
	cin >> n >> k;
	string str;
	cin >> str;
	int i = 0, ans = 0;
	while(i <= n-k){
		int x = k, j = i + 1;
		while(j < n){
			if(str[i] != str[j]){
				if(x == 0) break;
				x--;
			}
			j++;
		}
		ans = min(n, max(ans, j-i+x));
		i++;
		while(i<n && str[i-1]==str[i]) i++;
	}
	cout << ans;
}

subject 4

Two positive integers in the first line n and q,n Indicates the number of brands of milk tea ,q Represents the number of operations . The second line n Positive integers separated by spaces , Represents the unit price profit of each milk tea brand . Next q Operations , Each operation is one of the following ：Add x y ： brand x Increased sales of milk tea y.Query BestSales ： Query the milk tea brands with the largest sales so far in the current operation , If not unique, output the smallest .Query BestProfit ： Query the milk tea brands with the most profits so far , If not unique, output the smallest .1 <= n <= 100000, 1 <= q <= 500 Guarantee the brand x The scope of [1, n] within , Guaranteed sales y The added value is [1, 100] The answer to internal sales and profits is guaranteed to be [1, 1e9] Within the scope of

Example

2 6
1 2
Add 1 3
Add 2 2
Query BestSales
Query BestProfit
Add 1 1
Query BestProfit
Output

1

2

1

Code

AC 72%

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main(){
	int n, q;
	cin >> n >> q;
	vector<int> profit(n);
	for(int i = 0;i < n;i++)
		cin >> profit[i];// The output brand number needs to be added 1
	vector<int> totalSale(n), totalPro(n);
	for(int i = 0; i < q; i++){
		string query;
		cin >> query;
		if(query[0] == 'A'){
			int brand, num;
			cin >> brand >> num;// need -1 
			totalSale[brand - 1] += num;
			totalPro[brand-1] += num * profit[brand-1];
		}
		else{
			cin >> query;
			if(query=="BestSales"){
				int resSale = 0, resbrand = -1;
				for(int i = 0;i <n;i++){
					if(resSale< totalSale[i]){
						resSale = totalSale[i];
						resbrand = i;
					}
					
				}
				cout<<resbrand + 1 << '\n';
			}
			else{
				int resPro = 0, resbrand = -1;
				for(int i = 0;i <n;i++){
					if(resPro< totalPro[i]){
						resPro = totalPro[i];
						resbrand = i;
					}
					
				}
				cout<<resbrand + 1 << '\n';
			}
		}
	} 
	return 0;
}