字节跳动 提前批 推荐
一面
一个循环有序数组，没有重复元素，给一个整数，查询整数在数组中的位置，不在返回-1.
#include <iostream> #include<vector> #include<sstream> #include<string> using namespace std; int myLowerBound(vector<int> &nums, int i, int j, int x){ while(i<=j){ int mid = (j-i)/2+i; if(nums[mid]==x) return mid; else if(nums[mid]<x) i = mid+1; else j = mid-1; } return -1; } int getAns(vector<int> &nums, int x){ if(nums.size()==0) return -1; // step1 寻找最小元素的下标 int n = nums.size(); int i=0, j=nums.size(); while(i<j){ int mid = (j-i)/2+i; if(nums[mid]>nums[n-1]){ i = mid+1; }else{ j = mid; } } // 此时最小元素下标为i if(i==0){ return myLowerBound(nums, i, n-1, x); }else{ if(x>=nums[0]) return myLowerBound(nums, 0, i-1, x); else return myLowerBound(nums, i, n-1, x); } }对一个有序的整型数组，有n个数据，找一个索引的位置k，使前k个数的方差var(k)与后面n-k个数的方差var(n-k)之和最小。要求时间复杂度为O(n),空间复杂度为O(1)
#include <iostream> #include<vector> using namespace std; int getAns(vector<int> &nums){ int n = nums.size(); vector<double> left(nums.size(), 0); vector<double> right(nums.size(),0); pair<double, double> tmpL(0, 0); for(int i=0; i<nums.size(); i++){ // left[i]表示[0,i]的均值之差 tmpL.first += nums[i]*nums[i]; tmpL.second += nums[i]; left[i] = tmpL.first/(i+1)-tmpL.second/(i+1); } pair<double, double> tmpR(0,0); for(int i=nums.size()-1; i>=0; i--){ // right[i]表示[i, n-1] tmpL.first += nums[i]*nums[i]; tmpL.second += nums[i]; right[i] = tmpR.first/(n-i)-tmpR.second/(n-i); } int ans = 0x7fffffff; for(int i=1; i<n-1; i++){ ans = min(ans, left[i]+right[i+1]); } return ans; } int main() { cout << "Hello World!" << endl; }二面
机器学习
1. Dropout是什么？如何避免过拟合？
集成角度理解
避免特征依赖于特定的少数权重，使得其它权重不起作用
数据含噪的时候，可以降低噪点的影响
2. L1为什么容易得到稀疏的特征？尽可能多种理解
从梯度更新步长角度
从二阶近似角度
贝叶斯
lagrange
3. 交叉熵损失的优点，多分类为什么使用交叉熵损失？
参数的最大似然估计的角度
信息论的角度 KL三度
优化的角度，交叉熵是凸函数，便于凸优化，最优解唯一
softmax+交叉熵损失，梯度更新快
4. 10维特征的数据集，将第一维特征增加到第11维上会有什么后果？
第一维的特征受到过分关注
最优解不唯一，假设最优解下w1=0.1, 现在w1+w2=0.1,那么可能w1=100000, w2=-w1+0.1，导致梯度权重上溢、浮点误差抵消真实权重（0.1）等危害
浮点误差抵消真实权重-->导致震荡无法收敛对于线性回归模型，解析解不存在
编程题
给定一个有序数组nums以及数字x, 从数组中找两个数，使得他们的和为x，问这样的pairs有多少对？要求时间复杂度为O(n)
如果数组无序呢？同样要求时间复杂度为O(n)#include <iostream> #include<vector> #include<algorithm> using namespace std; int myPartition(vector<int> &nums, int s, int e){ int next = s; for(int i=s; i<e; i++){ if(nums[i]>nums[e]){ if(i!=next){ swap(nums[i], nums[next]); } next++; } } if(next!=e){ swap(nums[e], nums[next]); } return next; } int getK(vector<int> &nums, int k){ // k>=1 k--; int n = nums.size(); if(k<0 || k>=n) return -1; int i=0, j=n-1; while(i<=j){ int pivot = myPartition(nums, i, j); cout<<pivot<<','; if(pivot==k) return nums[pivot]; else if(pivot<k){ i = pivot+1; }else{ j = pivot-1; } } return -1; } int main() { vector<int> nums{3,1,4,2,5}; cout<<getK(nums, 0)<<endl; }三面
概率题
1. 任意一个市民选A做市长的概率为51%，选B做市长的概率为49%。那么，这个城市一个1亿个市民，全部投票，问A获胜的概率是多少？
分析：考察二项分布的中心极限定理
2.
范数如何书写，是否具有稀疏性，为什么？
分析:
. 具有稀疏性。因为他可以通过泰勒展开式中包含
范数
编程题
一个有序数组 n个元素，包括重复元素。给定t，求满足a[i]+a[j]=t (i < j)的 pari有多少。 返回pari数目。
#include <iostream> #include<vector> using namespace std; int getAns(vector<int> &nums, int k){ int n = nums.size(); if(n<2) return 0; long long ans = 0; int i=0, j=n-1; while(i<j){ // i应该小于j if(nums[i]+nums[j]<k){ // 跳过重复nums[i] while(i+1<j && nums[i+1]==nums[i]) i++; i++; }else if(nums[i]+nums[j]>k){ // 跳过重复nums[j] while(i<j-1 && nums[j-1]==nums[j]) j--; j--; }else { if(nums[i]==nums[j]){ int tmp = (j-i+1); ans += (tmp*(tmp-1)/2); break; }else{ int old_i = i; while(i+1<j && nums[i+1]==nums[i]) i++; i++; int old_j = j; while(i<j-1 && nums[j-1]==nums[j]) j--; j--; ans += (i-old_i)*(old_j-j); } } } return ans; } int main() { vector<int> nums{-3, -2, 0, 1, 1, 2, 5, 6}; int x = 11; cout<<getAns(nums, x)<<endl; cout << "Hello World!" << endl; }
投递大华股份等公司10个岗位