面经--Naturali算法实习生
笔试三道题
- Combine two strings a and b.
string Combine(string str1,string str2)
{
if (str1 == "") { cout << "str2:"; return str2; }
if (str2 == "") { cout << "str1:"; return str1; }
int i = str1.length()-1; //第一个字符串从末尾遍历
int j = 0; //第二个字符串从开头遍历
while (i >= 0 && j < str2.length()){
if (str1[i] == str2[j]){ i--; j++; }
else{ break; }
}
string str(str1, 0, i+1 ); //str初始化取第一个字符串前部分
str += str2.substr(j); //加上第二个字符串后部分
return str;
} 2.n个整数的数组[a1,a2,…,an]，List L=[]. 对于每两个数ai 和 aj (i < j),
min(ai, aj)放入 L. 所以L共有 n×(n-1)/2个整数 . 请找出L中
第 k-th 大的数. (O(n) time)（剑指offer）
//功能实现总函数，由三个子函数完成
//子函数1：计算List的第k-th 大的数是数组a的第rank 小的数
int find_Kth_ina_Rank(int n, int k){
int i = 1;
while (k > 0){ k -= i; i++; }
int rank = n+1-i ;
return rank;
}
//子函数2：使用快速排序为模型,处理划分一边时平均时间为0(n)
int partition(int a, int low, int high)
{
int pivotkey;
pivotkey = a[low];
while (low < high)
{
while(low < high && pivotkey <= a[high])
high--;
a[low] = a[high];
while(low = a[low])
low++;
a[high] = a[low];
}
a[low] = pivotkey;
return low;
}
//子函数3：判断处理哪一边，并在找到后返回目标值
int sort(int a, int low, int high, int tofindRank)
{
int p;
if (low == high)
return a[low];
if (low < high)
{
p = partition(a, low, high);
if ( p+1 == tofindRank) //当为第tofindRank小时，返回a[p]
return a[p];
else if (p+1 > tofindRank)
return sort(a, low, p - 1, tofindRank);
else
return sort(a, p + 1, high, tofindRank );
}
}
//总函数
int find_Kth_in_List(int *a, int n, int k)
{
int rank = find_Kth_ina_Rank(n, k);
int find = sort(a, 0, n - 1, rank);
return find;
} 3. 买卖苹果最大收益给出含n个非负整数的数组，表示每天苹果价格，最多只能拥有一个苹果。不限买卖次数，每次买入手续费固定为p，求最大利润。（时间O(n)）
Example:
Input: price = [0, 2, 1, 8, 4, 9], p = 2
Output: 9
buy at price[0], sell at price[3], buy at price[4], sell at price[5]
int MaxProfit(vector prices){
int buy=INT_MIN,sell=0;
for(int i=0;i<prices.size();i++){
buy = max(buy, -prices[i]);
sell = max(sell, buy + prices[i]);
}
return sell;
} 多次买卖 int MaxProfit(vector prices){
int buy=INT_MIN,sell=0;
for(int i=0;i<prices.size();i++){
buy = max(buy, sell - prices[i]);
sell = max(sell, buy + prices[i]);
}
return sell;
} 每次买卖手续费pint MaxProfit(vector prices,int p){
int buy = INT_MIN, sell = 0;
for(int i = 0;i < prices.size();i++){
buy = max(buy, sell - prices[i] - p);
sell = max(sell, buy + prices[i]);
}
return sell;
}
``` 一面：
1.求数组中一个落单的数字，别的都是成对数字。时间O（n），空间O（1）
2.二维数组，a [i] [j] < a [i+1] [j] && a [i] [j]< a [i] [j+1],查找给定数字 （剑指offer）
3.动态规划：末日传送 vt [i，j]=v0[I,j] 1.1^(t-1) 任意两个节点间花费随时间增长
求A.-B的最小花费
状态转移方程：cost[j][t] = min ( cost[k][t-1] + v[k][j] pow(1.1, t-1) , cost[j][t-1] )
double min_cost_AtoB(vector<vector<double>>& v,int n,int A,int B) {
vector<vector<double>> cost (n, vector<double>(n) );
// t=0时，A到每个节点的花费 for(int i = 0; i < n; i++){
cost[i][0] = v[A][i];
}
for (int t = 1; t < n; t++){
for (int j = 0; j < n; j++){
cost[j][t]=cost[j][t-1];
for (int k = 0; k < n; k++){
double temp = cost[k][t - 1] + v[k][j] pow(1.1, t);
cost [j] [t] = temp < cost [j] [t] ? temp : cost [j] [t];
}
}
}
return cost[B][n-1];
} 二面：
**
1.三次握手
2.SQL语句，索引原理
3.Linux 命令 ：netstat,awd,cut,sort
4.B树和红黑树
5.算法题
**
1.两个单链表长度为m,n，在某个节点之后重合，找这个节点。（剑指offer）
指向长的链表的指针先走m-n步，再一起遍历，直到节点相同。时间O（m+n）
2.高维DP： n个数字 1 4 2 2 2 4……，每次取x个相邻相同数字，得分为x^2
取 2 2 2 得分3^2=9
取 4 4 得分 2^2=4
取 1 得分 1^2=1
总分 14
给一串数字，求 能取得的最高分
3.找出现次数超过一半的数字。时间O（n） （剑指offer）这个数字一定在数组排序的中间位置，故用partition函数直到枢纽为中间位置
6. 六级过了吗？？？ 多少分？？？
三面：
1.自我介绍
2.问项目，怎么做的，tf-idf、word2vec，处理计算方法。。
3.数据结构。红黑树
4.C++11 特性
5.二叉查找树，找中序遍历时的下个节点。（剑指offer）
1>有右子树时，下个节点为右子树的最左子树
2>无右子树，为父节点的左子树，下个节点为父节点
3>无右子树，为父节点的右子树，向上遍历直到该节点为父节点的左子树
6.sigmod函数、softMax函数、贝叶斯、svr与svm
7.概率论
n个相同的球放到m个盒子里，多少种放法：
1> 每个盒子至少一个球 ：C(n-1)^(m-1) 相当于n个球中间插入m-1个挡板
2> 盒子可以为空： C(n+m-1)^(m-1) 每个盒子为-1个球，多出m个球，转化为每个盒子至少一个球。故相当于n+m个球中间插入m-1个挡板
8.就聊到这儿？说好的Deep Learning呢？不行，我得和你说说，CNN卷积过程
N'=(N-F+2*padding)/step+1
大疆公司氛围 166人发布
