第四范式不好吃的凉面

应聘的第四范式的SP专场,岗位是计算机视觉岗,然后昨晚熬夜了(熬到两点),早上起来头很晕,昏昏沉沉的,
面试官一上来就说面试时间有限,我们跳过自我介绍,直接coding吧(那就直接coding吧,不coding还能怎么办),
然后看到题目大脑一片空白(明明剑指offer刷到过,但由于熬夜导致啥都没想起来),好了说多了都是借口,在这立个flag,早睡早起,正式说题
(就两道编程题,其他啥也没问,反正是凉了,放出来造福大家,万一是同一个面试官呢)
第一题:乱序数组,使奇数值排在偶数值之前(要求O(n)时间复杂度,O(1)空间复杂度)
第二题:乱序链表,使奇数值排在偶数值之前(要求O(n)时间复杂度,O(1)空间复杂度)
刚午睡了一下,几分钟就写完了,面试的时候各种卡顿紧张(牛客的视频面,面试官可以看到你在编辑框中的整个coding过程,当然还能看到你)
上代码(有错的话,大家指出哈)
第一题:
#include<iostream>
#include<vector>

using namespace std;

//乱序数组,使奇数值排在偶数值之前(要求O(n)时间复杂度,O(1)空间复杂度)
void func(vector<int> &array)
{
	if (array.size() < 2)
		return;
	int start = 0, end = array.size() - 1;
	while (start < end)
	{
		while (array[start] & 0x0001)
		{
			if (start == end)
				break;
			++start;
		}
		while ((array[end] & 0x0001) == 0)
		{
			if (end == start)
				break;
			--end;
		}
		if (start == end)
			break;
		int temp = array[start];
		array[start] = array[end];
		array[end] = temp;
		++start;
		--end;
	}
}

int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> input;
		int temp;
		for (int i = 0; i < n; ++i)
		{
			cin >> temp;
			input.push_back(temp);
		}
		func(input);
		for (auto it : input)
			cout << it << ' ';
		cout << endl;
	}
	return 0;
}
第二题:
#include<iostream>
#include<vector>

using namespace std;

//乱序链表,使奇数值排在偶数值之前(要求O(n)时间复杂度,O(1)空间复杂度)
struct ListNode{
	int val;
	ListNode* next;
	ListNode(int x) :val(x), next(NULL){}
};

void func(ListNode** root)
{
	if (root == NULL)
		return;
	ListNode* pNode = *root;
	ListNode* preNode = *root;

	pNode = pNode->next;
	while (pNode)
	{
		if (pNode->val & 0x0001)
		{
			preNode->next = pNode->next;
			pNode->next = *root;
			*root = pNode;
			pNode = preNode->next;
		}
		else
		{
			preNode = pNode;
			pNode = pNode->next;
		}
	}
}
ListNode* constructList(const vector<int> &array)
{
	if (array.size() == 0)
		return NULL;
	ListNode* root = new ListNode(array[0]);
	ListNode* pNode = root;
	for (int i = 1; i < array.size(); ++i)
	{
		pNode->next = new ListNode(array[i]);
		pNode = pNode->next;
	}
	return root;
}

void printList(ListNode* root)
{
	ListNode* pNode = root;
	while (pNode)
	{
		cout << pNode->val << ' ';
		pNode = pNode->next;
	}
	cout << endl;
}
int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> input;
		int temp;
		for (int i = 0; i < n; ++i)
		{
			cin >> temp;
			input.push_back(temp);
		}
		ListNode* root = constructList(input);
		func(&root);
		printList(root);
	}
	return 0;
}
忽然想到,如果要求保持奇数/偶数相对顺序不变呢?
对于数组,个人只想到O(n^2)复杂度的冒泡法
对于链表,可以把偶数尾插(O(n)时间复杂度,O(1)空间复杂度)

#第四范式##面经##计算机视觉岗##校招#
全部评论
奇偶只能想到归并nlogn思想
点赞 回复
分享
发布于 2019-08-17 16:57
联想
校招火热招聘中
官网直投
我想问一下,coding需要自己写测试用例么
点赞 回复
分享
发布于 2019-08-17 20:13
良心!!!感谢!!!
点赞 回复
分享
发布于 2019-09-25 17:17

相关推荐

面经:第四范式数据科学面经一面:组leader面1.自我介绍+实习经历询问2.统计考察:假设检验原理与举例3.p值是什么?怎么解释给没学过统计的人4.机器学习原理问题5.现场写python:数组倒序排列问题6.反问二面:部门leader面1.主要针对某大厂数分实习详细询问,会关注你背后业务逻辑以及你对业务逻辑是否有思考2.动态规划怎么考虑优化空间复杂度3.基于历史数据如何预测90天后的数据4.为什么想做这个方向以及以后的职业规划5.反问三面:CTO面1.很轻松(感觉都在针对你的背景以及经历)2.有详细介绍业务团队职业发展等3.注重你对业务的思考四面:hr面公司介绍以及内推#第四范式2024届春季校园招聘火热开启✨【企业介绍】第四范式于2023年H股上市,是中国智能决策市场的领导者。🔥【热招岗位】后端研发工程师/NLP算法工程师/语音算法工程师/机器学习算法工程师/物理仿真算法工程师/决策优化算法工程师/计算机视觉算法工程师🏫【工作地点】北京、上海、深圳、武汉💰【薪资待遇】业内顶级福利体系:我们承诺让优秀的人获得应有的年薪待遇:配套每日餐补、带薪年假、六险一金等健全的福利体系,此外优秀的学生也能落户北京/上海等一线城市。&nbsp;【招聘岗位】机器学习算法、架构,语音算法,计算机视觉,后端开发,大数据处理,产品经理,人力资源等!🔥&nbsp;【岗位城市】北京、上海、无锡、武汉、深圳、新加坡。💞&nbsp;【福利待遇】薪资待遇=基础薪资+绩效奖金+多种福利补贴,除此之外公司还有健身房、兴趣社团活动,电竞椅,升降办公桌等众多福利等你来解锁🌹【内推链接】https://app.mokahr.com/m/campus_apply/4paradigm/58145?recommendCode=DScrkMCy#/jobs【内推码】DScrkMCy #春招# #实习# #内推# #内推码# #秋招#
点赞 评论 收藏
转发
4 33 评论
分享
牛客网
牛客企业服务