拼多多2019实习算法岗招聘笔试记录

笔试记录"/>

拼多多2019实习算法岗招聘笔试记录

在经过了腾讯的洗礼后，这次拼多多的笔试做的还不错。2个小时4道编程题，都做对了。在此凭记忆写下题目并给出解答。

第一题：给一组数，数的个数是偶数，两两配对求和，使得和的最大值减去和的最小值最小。求这个差值。

题目看上去挺难的，当时想了一下感觉就是排序后第一个和最后一个组合，第二个和倒数第二个组合……记录一下最大值和最小值就行了。后来提交上去AC了。改天用数学证明一下这种配对方式是使得最小差值的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main()
{int n;cin>>n;vector<int> nums(n);for (int i=0;i<n;i++){cin>>nums[i];}sort(nums.begin(),nums.end());int max_record=0,min_record=300;for (int i=0;i<n/2;i++){max_record=max(max_record,nums[i]+nums[n-i-1]);min_record=min(min_record,nums[i]+nums[n-i-1]);}cout << max_record-min_record;return 0;
}

第二题：给定0到9十个数字的每个数字的可使用次数，以及A和B两个数的位数，让A和B选择可使用的数字进行组合，使得A*B最小，求这个最小值。

比如 给定0到9的数字各一个: 1 1 1 1 1 1 1 1 1 1 A和B的位数都是2。那么A=01，B=23，可以使得结果最小（A和B都可以有前导0）。

首先有一个点可以肯定的是，A或B拿到数字后，数字肯定是按从小到大的顺序排列的。所以我第一想法是A和B依次拿走剩下数字中最小的那一个。事实上这样不行，上面的例子就是一个反例，按照这种拿法，A=03，B=12，乘积是36，比01*23=23要大。这种方法得了25分。后来又想着说是不是A先拿最小的，A拿完了B再拿，交上去后也不对，只有15分。

把3 4题都做完后再回来做这道题，发现既然A和B都只拿最小的数字，那么其实有很多冗余的给出的数字，这些数字是没有用的。先把这些数字去掉，再进行组合，然后穷举就可以算出A*B的最小值了。这里要用到求组合的算法。

#include <iostream>
#include <vector>
using namespace std;// 求0，1，2，…… ,n-1这n个数字中取k个数字的所有组合方式，结果储存在res中
void DFS(int n,int k,vector<vector<int>> &res,vector<int>& combination,int step)
{if(combination.size()>k){return;}if(step==k-1){res.push_back(combination);return;}int start;if(combination.empty())start=-1;else start=combination.back();for(int i=start+1;i<n;i++){combination.push_back(i);DFS(n,k,res,combination,step+1);combination.pop_back();}
}int main()
{vector<int> counts(10);for(int i=0;i<10;i++){cin>>counts[i];}int A_len,B_len;cin>>A_len;cin>>B_len;if(counts[0]>=min(A_len,B_len)){cout<<0;return 0;}vector<int> record;for(int i=0;i<A_len+B_len;i++){for(int j=0;j<counts.size();j++)if(counts[j]!=0){counts[j]--;record.push_back(j);break;}}vector<vector<int>> index;vector<int> combination;DFS(A_len+B_len,A_len,index,combination,-1);long long res,A,B;for(int i=0;i<index.size();i++){vector<bool> choose_A(A_len+B_len,false);for(int j=0;j<index[i].size();j++){choose_A[index[i][j]]=true;}A=0;B=0;for(int j=0;j<A_len+B_len;j++){if(choose_A[j])A=10*A+record[j];elseB=10*B+record[j];}if(i==0) res=A*B;else res=min(A*B,res);}cout<<res;return 0;
}

第三题：给定一个数组，和一个数字d，求数组中两个数之差大于等于d的概率。数组长度1<=L<=100,数字大小1<=s[i]<=50,1<=d<=50。结果保留6位小数。

例如输入：

{1，2，3}

2

输出：0.333333

这个题当时看到就觉得很简单，估计是想考我们会不会输出小数以及解析输入（输入是包括大括号{ }和逗号，的）。我是先用字符串读输入，再转化成数组。

#include <iostream>
#include <vector>
#include <string>
using namespace std;int main()
{vector<int> S;string input;cin>>input;int len=input.length();if(len==4)S.push_back((input[1]-'0')*10+input[2]-'0');elseS.push_back(input[1]-'0');while(true){cin>>input;len=input.length();if(len==3)S.push_back((input[0]-'0')*10+input[1]-'0');elseS.push_back(input[0]-'0');if(input.back()=='}')break;}int d;cin>>d;int right=0,sum=S.size()*(S.size()-1)/2;for(int i=0;i<S.size();i++){for(int j=i+1;j<S.size();j++){if(abs(S[i]-S[j])<=d){right++;}}}printf("%0.6f",double(right)/sum);return 0;}

第四题：求一个单词word1到word2的最少操作次数。操作包括增加、删除和修改。

这道题在上次腾讯面试中遇见过，当时没有做出来（并且面试前我还在leetcode中看到过这道题）我的博客：腾讯面试经历

这一次很快的就做出来了，基本思路就是动态规划，其实很简单。

#include <iostream>
#include <string>
#include <vector>
using namespace std;int main()
{string w1,w2;cin>>w1;cin>>w2;int len1=w1.length(),len2=w2.length();vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));dp[0][0]=0;int tmp;for(int i=0;i<=len1;i++){for(int j=0;j<=len2;j++){tmp=5000;if(i==0&&j==0) continue;if(i>0){tmp=dp[i-1][j]+1;}if(j>0){tmp=min(tmp,dp[i][j-1]+1);}if(i>0&&j>0){if(w1[i-1]==w2[j-1])tmp=min(tmp,dp[i-1][j-1]);elsetmp=min(tmp,dp[i-1][j-1]+1);}dp[i][j]=tmp;}}cout<<dp[len1][len2];
}

接下来应该有面试机会，加油吧！