蔚来 数字化业务 大数据开发工程师

投nlp挂，转岗大数据开发

一面

算法题1：一个只包含1，2，3的数组，排序使得3在最前，2在中间，1在最后。要求时间复杂度O(n)，空间复杂度O(1)。

#include<bits/stdc++.h>
using namespace std;

vector<int> num = {1,2,3};
// 排成：3 ... 3 2 ... 2 1 ... 1 

int main()
{
	int l = 0, r = num.size()-1;
	for (int i=0; i<num.size(); i++) {
		if (num[i] == 3) {
			swap(num[l++] , num[i]);
		}
	}
	for (int i=num.size()-1; i>=0; i--) {
		if (num[i] == 1) {
			swap(num[r--], num[i]);
		}
	}
	for (int i=0; i<num.size(); i++) cout << num[i] << " "; 

	return 0;
}

二面

算法题2：数组中，第一个非0的数位置索引，时间复杂度O(log n)。

二分查找

#include<bits/stdc++.h>
using namespace std;

vector<int> num = {0,0,0,0,0,0,0,1,2,3,2,3,1};

int main()
{
	int l = 0, r = num.size()-1;
	// 找左边第一个非零的位置
	while (l<r) {
		int mid = l + (r-l)/2;
		if (num[mid] == 0) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
	}
	cout << l << endl;


	return 0;
}

两个面试官都很nice，没有因为岗位不匹配为难。