This article describes the online written test questions of the Pinduoduo algorithm based on C++. Share it for your reference, as follows:
I have been internship in Wolf Factory recently and haven't done any questions for a long time. The first shot of autumn recruitment is Pinduoduo. . . Four simple questions, what do you think is difficult when you see some people? I'll give my own RP. This question is difficult. If you get a better offer than me, I'm not convinced. .
Four questions. . . Actually, I only wrote for 40 minutes. . But there was no full mark in the end, 390/400. I don’t know why I can’t pass the third question with 10 points. .
After all, I just found the third question. . . This > number, I wrote >= ......? But I think the title seems to be >=. . .
Question 1:
The time complexity O(n) and the space complexity O(1) are required.
So there are actually two situations for the answer: multiplying the three largest numbers || The two smallest numbers * The largest number. Time complexity O(n), I instantly thought of the classic algorithm that finds k to find the time complexity O(n), and divide and treat!
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
long long a[N];
int k;
int partition(int l,int r) {
while(l != r)
{
while(a[r] >= a[l] && r > l)
r--;
if(l == r)
break;
swap(a[r],a[l]);
while(a[l] < a[r] && r > l)
l++;
if(l < r)
swap(a[r],a[l]);
}
return l;
}
long long solve(int l,int r) {
int now = partition(l,r);
if(k < now)
return solve(l,now-1);
else if(k > now)
return solve(now+1,r);
else
return a[now];
}
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
}
k = n - 1;
long long x1 = solve(0, n-1);
k = n - 2;
long long x2 = solve(0, n-2);
k = n - 3;
long long x3 = solve(0, n-3);
long long Ans = x1 * x2 * x3;
if(n > 3) {
k = 0;
long long y1 = solve(0, n-1);
k = 1;
long long y2 = solve(0, n-2);
Ans = max(Ans, y1*y2*x1);
}
printf("%lld\n", Ans);
}
return 0;
}
Question 2:
Multiplying large numbers, template questions, I found a template. . .
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
string c1, c2;
int a[N], b[N], r[N];
void solve(int a[], int b[], int la, int lb) {
int i, j;
for(i = 0; i != N; i++) r[i] = 0;
for(i = 0; i != la; i++)
{
for(j = 0; j != lb; j++)
{
int k = i + j;
r[k] += a[i] * b[j];
while(r[k] > 9)
{
r[k + 1] += r[k] / 10;
r[k] %= 10;
k++;
}
}
}
int l = la + lb - 1;
while(r[l] == 0 && l > 0) l--;
for(int i = l; i >= 0; i--) cout << r[i];
cout << endl;
}
int main() {
while(cin >> c1 >> c2)
{
int la = (), lb = ();
for(int i = 0; i != la; i++)
a[i] = (int)(c1[la - i - 1] - '0');
for(int i = 0; i != lb; i++)
b[i] = (int)(c2[lb - i - 1] - '0');
solve(a, b, la, lb);
}
return 0;
}
Question 3:
Greedy, I am greedy as I try to meet the needs of the least person. . . Always 90%? Some people use the largest chocolate to greed, 100%. Is it better to have a counterexample?
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 3e6 + 10;
long long w[N], h[N];
int main() {
int n, m;
while(~scanf("%d", &n)) {
for(int i = 0; i < n; ++i) {
scanf("%lld", &h[i]);
}
scanf("%d", &m);
for(int i = 0; i < m; ++i) {
scanf("%lld", &w[i]);
}
sort(h, h + n);
sort(w, w + m);
int Ans = 0;
for(int i = 0, j = 0; i < n && j < m; ) {
if(w[j] >= h[i]) {
++Ans;
++i, ++j;
}
else {
++j;
}
}
printf("%d\n", Ans);
}
return 0;
}
Question 4:
The maze problem, interestingly, there is an extra key. . . There are no more than 10 doors to see. . . M, N <=100...Think about the number of states. . . Direct state compression. . Then there is a very violent and shameful state compressing bfs. . . Then there was an AC. .
#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const int N = 110;
char mz[N][N];
bool vis[N][N][N*10];
int fx[4] = {0, 0, 1, -1};
int fy[4] = {1, -1, 0, 0};
int m, n;
map<char, int> key;
struct node {
int x, y, cnt, sta;
node():cnt(0), sta(0) {}
};
queue<node> que;
int bfs(int sx, int sy, int ex, int ey) {
while(!()) ();
node tmp;
= sx, = sy;
(tmp);
while(!()) {
node p = ();
if( == ex && == ey) {
return ;
}
();
for(int i = 0; i < 4; ++i) {
int newx = + fx[i];
int newy = + fy[i];
if(newx < 0 || newx >= m || newy < 0 || newy >= n) continue;
if(mz[newx][newy] == '0') continue;
int sta = ;
if(mz[][] >= 'a' && mz[][] <= 'z') {
sta |= (1<<key[mz[][]]);
}
if(vis[newx][newy][sta]) continue;
if(mz[newx][newy] >= 'A' && mz[newx][newy] <= 'Z') {
if((sta & (1<<(key[mz[newx][newy] - 'A' + 'a'])))== 0) {
continue;
}
}
vis[newx][newy][sta] = true;
= newx, = newy, = + 1, = sta;
(tmp);
}
}
return -1;
}
int main() {
while(~scanf("%d %d", &m, &n)) {
int sx, sy, ex, ey;
int cnt = 0;
for(int i = 0; i < m; ++i) {
scanf("%s", mz[i]);
for(int j = 0; j < n; ++j) {
if(mz[i][j] == '2') {
sx = i, sy = j;
}
if(mz[i][j] == '3') {
ex = i, ey = j;
}
if(mz[i][j] >= 'a' && mz[i][j] <= 'z') {
key[mz[i][j]] = cnt++;
}
}
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
for(int s = 0; s < (1<<cnt); ++s) {
vis[i][j][s] = false;
}
}
}
int Ans = bfs(sx, sy, ex, ey);
printf("%d\n", Ans);
}
return 0;
}
I hope this article will be helpful to everyone's C++ programming.