`
alucardggg
  • 浏览: 8927 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

百度面试经历及面试问题解答

 
阅读更多
最近忙着面试,很意外接到百度的面试电话,在经过电话面试之后(招聘HR好好玩好NICE啊),百度邀请我去上海研发中心进一步面试,于是在昨天就花了一天跑去上海百度面试了。
    因为之前面过阿里和京东,两家都通过了,说实话去百度还是被问了个措手不及,因为当时觉的问题应该和阿里京东差不多,所以一点都没准备,结果去了之后才知道百度看重的是什么,是编程能力和算法能力,基本每问一个问题,都会让你现场编写代码,问题都非常细节(都到代码层了会不细吗)Java会问到某某生僻关键字是干嘛用的,然后写段代码。。。而且现场时间很紧,面试官又会催着你,总之就是面出一身汗,第一轮是面Java,完了之后会来一个Level更高的面其他方面。让我觉的NB的是,第二轮那个面试官一开口就是“你最擅长什么”。。让我想到倚天屠龙记里面金毛狮王谢逊和张翠山那段。。。
    由于之前被Java那家伙问慌了,所以就选了数据库,当时心态是这样的:数据库SQL,哼哼,我可是无论什么都能搞定的那种,结果面试官问你非常奇葩的问题:三维以上的结果集查询混合把列名当成结果集一起查询,外加一条SQL搞定。。好吧,我承认我用的两种方法他都不认可,我说做出来就好了你用得着管这么多,我不知道你心理价位是什么。。。
    二轮过了就没了,我想应该是没戏,不然就会有后续的项目经验面试,好歹我大老远跑趟上海不容易。。。
    现在说个Java里面问到的算法题目吧:
    给定一个字符序列"abcd",要求在一个超长的字符数组中(比如几百万),以最快速度找出包含这4个字符的最短子串
    最快速度,当然就是O(n)时间内了。
    说实话,我当时做出50%,为什么这么说呢,因为我当时想到的是时间(O(n2))级的算法,我当时想到的算法是这样的:给定一个字符串"abcd"然后用indexOf判断包含关系,另外给定一个判别数组比如{0,0,0,0}分别对应这4个字符,如果找到一个,则把字符数组中的位置记录在判别数组中,每次循环判断数组相乘是否为0,如果为0,证明全部找到了。那么就记录下子串长度和位置,然后把判别数组清零重新开始,比较再次找到的子串长度,一直到最短为止。。
    那么这样会有什么问题呢?问题就在于比如给定
    eroapycinbsldfbnsdfikqiytfewkgbkfahgasdasfqwwerq这么一串时候,如果找到了第一个子串apycinbsld,那么事实上第二个子串的开始位置,不是从子串apycinbsld之后开始,应该从apycinbsld里面的c开始,因此如果用这个算法,会导致重复多次判别,时间复杂度是n2.
    当时特别紧张,因为他一直等着我给答案,这种算法,越急越想不出,所以我就给了个50%。。
    后来开车时回杭州路上,把这个问题给想通了,时间复杂度为O(n)级别,解法为这样:

    用4个游标来标记即可
    首先先找到第一个子串,找法是利用一个游标数组,比如int[] c = {0,0,0,0}这样,分别对应a,b,c,d 4个字符,然后开始循环查找大字符串,找到a,则修改第一个游标值为a当前位置,找到b则第二个以此类推,如果找到重复的,则用重复的位置替换前面位置,判别方法仍然可以用游标相乘是否为0,如果不为0,则认为4个位置都找到了,因此就找到一个子串,接下来就把最小的游标标记为0,把第二大的标记为头,重新往后找,如果找到字符不为新的头字符,则把相应的游标位置更新,每次找到新的都比较是否最短,如果是最短,就存起来,最后输出,这样就能达到O(n)级别的时间复杂度

    今天抽空把代码实现了下,测试结果为:10,000,000规模下,用我的PC机,找出一个最短子串大概在350毫秒左右
    因为我里面找到最小和第二小游标,都用了循环,可以把数据结构变成队列,速度能进一步提升
    时间关系,我懒得写队列了,有兴趣的同学可以自行实现下
    运行结果如下:
    用时:369毫秒
    找到最短子串:
    adbac


    代码如下,代码说真的也很短,但是当时就是没想出来,哎。。。
public class FindChar {
	public static void main(String[] args) {

		
		
		String x = "abcd";
		int[] c = new int[] { 0, 0, 0, 0 };		
		char[] y = createCharSequence();		
		char s = 0;
		
		boolean find = false, first = false;
		int rs = 0, re = 0, rl = Integer.MAX_VALUE;

		long a = System.currentTimeMillis();
		for (int i = 1; i < y.length + 1; i++) {
			int p = x.indexOf(y[i - 1]);

			if (p != -1) {
				if (!first) {
					s = y[i - 1];
					first = true;					
				}
				
				if (c[0] * c[1] * c[2] * c[3] == 0) {
//					if (!find) {
						int k = 0;
						for (int j = 0; j < c.length; j++) {
							if (c[j] != 0)
								++k;
						}
						if (k > 1) {
							if (s != x.charAt(p)) {
								c[p] = i;
							}
						} else {
							c[p] = i;
						}
//					} else {
//						c[p] = i;
//					}
				} else {
					if (!find)
						find = true;
					int _rs = Math.min(Math.min(c[0], c[1]),
							Math.min(c[2], c[3]));
					int _re = Math.max(Math.max(c[0], c[1]),
							Math.max(c[2], c[3]));
					if (_re - _rs < rl) {
						re = _re - 1;
						rs = _rs - 1;
						rl = re - rs;						
					}
					s = x.charAt(find2ndStartPos(c));
					c[findStartPos(c)] = 0;
				}
			}
		}

		System.out.println("用时:" +(System.currentTimeMillis()-a)+"毫秒");
		// print
		for (int i = rs; i < y.length; i++) {
			if (i > re) {
				break;
			}
			System.out.print(y[i]);
		}

	}

	private static int findStartPos(int[] s) {
		int p = Integer.MAX_VALUE;
		int pos = 0;
		for (int i = 0; i < s.length; i++) {
			if (s[i] < p) {
				p = s[i];
				pos = i;
			}
		}
		return pos;
	}
	
	private static int find2ndStartPos(int[] s) {		
		int pp = findStartPos(s);
		
		int p = Integer.MAX_VALUE;
		int pos = 0;
		for (int i = 0; i < s.length; i++) {
			if(i == pp) continue;
			if (s[i] < p) {
				p = s[i];
				pos = i;
			}
		}
		return pos;
	}

	private static char[] createCharSequence() {
		char[] d = new char[] { 'a', 'a', 'a', 'b', 'c', 'd', 'e', 'f', 'g',
				'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
				't', 'u', 'v', 'w', 'x', 'y', 'z' };
		char[] e = new char[10000000];
		for (int i = 0; i < 10000000; i++) {
			int x = (int) ((Math.round(Math.random() * 10000000)) % 28);
			e[i] = d[x];
		}
		return e;
	}
[size=medium][/size]
    
分享到:
评论

相关推荐

    动态加载概述与原理.docx

    动态加载概述与原理.docx

    LOL_params_0900000.pt

    LOL_params_0900000.pt

    分群用户详情_7_2024-09-06 09_49_58.xlsx

    分群用户详情_7_2024-09-06 09_49_58

    动态加载的高级主题:懒加载与按需加载.docx

    动态加载的高级主题:懒加载与按需加载.docx

    【超强组合】基于VMD-开普勒优化算法KOA-Transformer-LSTM的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    Minecraft 1.20.1 Paper Plugin-基于Towny Flagwar 为其实现中立国家

    为Towny Flagwar实现中立国家 /nasetnu 设置自己的国家为中立(仅king可用)

    resnet模型-基于图像分类算法对度假胜地识别-不含数据集图片-含逐行注释和说明文档.zip

    本代码是基于python pytorch环境安装的。 下载本代码后,有个环境安装的requirement.txt文本 首先是代码的整体介绍 总共是3个py文件,十分的简便 本代码是不含数据集图片的,下载本代码后需要自行搜集图片放到对应的文件夹下即可 需要我们往每个文件夹下搜集来图片放到对应文件夹下,每个对应的文件夹里面也有一张提示图,提示图片放的位置 然后我们需要将搜集来的图片,直接放到对应的文件夹下,就可以对代码进行训练了。 运行01生成txt.py,是将数据集文件夹下的图片路径和对应的标签生成txt格式,划分了训练集和验证集 运行02CNN训练数据集.py,会自动读取txt文本内的内容进行训练,这里是适配了数据集的分类文件夹个数,即使增加了分类文件夹,也不需要修改代码即可训练 训练过程中会有训练进度条,可以查看大概训练的时长,每个epoch训练完后会显示准确率和损失值 训练结束后,会保存log日志,记录每个epoch的准确率和损失值 最后训练的模型会保存在本地名称为model.ckpt 运行03pyqt界面.py,就可以实现自己训练好的模型去识别图片了

    基于Java的订餐系统设计与实现:涵盖系统架构、前端交互与数据库管理

    内容概要:本文详细介绍了一款基于Java的订餐系统的设计与实现。文章首先介绍了互联网时代背景下,订餐系统作为一种新型生活方式的便捷性与必要性。接着阐述了系统的设计背景、目的及其所采用的技术框架(如JSP、MySQL、MyEclipse)。系统分为前台和后台两大部分,前台主要负责用户的界面展示和互动,包括食品展示、查询、购物车等功能;后台则是管理员进行餐品管理和用户信息维护的平台。文中还详细解析了各主要功能模块的设计思路和技术实现细节,以及数据库表结构的设计。 适合人群:具备一定的Java开发基础,对Web应用开发有兴趣的初学者或工程师。 使用场景及目标:用于学习基于B/S架构的订餐系统的开发全过程,理解前后端分离、JSP动态页面生成、MySQL数据库操作等核心技术的应用。适合希望深入了解餐饮管理系统内部运作机制的学生或从业者。 其他说明:此系统设计符合现代互联网发展趋势,通过引入JSP、JavaScript、MySQL等主流技术,旨在提高餐饮行业的管理效率和服务水平,增强用户体验。此外,本项目也包含了系统测试的内容,确保各项功能的正常运转。

    【java毕业设计】家用电器销售网站源码(ssm+jsp+mysql+说明文档+LW).zip

    功能说明: 管理员:个人中心、用户管理、商品分类管理、品牌管理、商品信息管理、订单评价管理、留言板管理、系统管理、订单管理。用户:个人中心、订单评价管理、我的收藏管理、订单管理。前台首页:首页、商品信息、商品资讯、留言反馈、我的、跳转到后台、购物车等功能的家用电器销售网站。 环境说明: 开发语言:java 框架:ssm jdk版本:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse 部署容器:tomcat7+

    联想电脑的bios设置

    联想电脑的bios设置、图文都有

    基于springboot+vue+redis+mysql实现的大学生宿舍管理系统【源码+数据库】

    技术:ssm+mysql+redis vue+element 功能:宿舍管理、学生管理、班级管理、宿舍楼管理、维修记录、晚归记录、请假记录、用户管理、角色管理、菜单管理、日志管理

    【超强组合】基于VMD-飞蛾扑火优化算法MFO-Transformer-GRU的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    跨浏览器兼容性测试.docx

    跨浏览器兼容性测试.docx

    编译供c语言使用的Vosk库,可以直接使用省去编译的麻烦过程

    Vosk是一个开源的语音识别工具,支持中英文及多种语言,具备离线识别能力,且不依赖互联网。优势 Vosk 是一个离线开源语音识别工具包,它的优点在于: 轻量:Vosk 提供轻量级的模型(小于 50MB 大小),可以用于低功耗平台(例如 Android、树莓派之类) 多编程语言、多平台支持:Python、Java、Node.js、C#、C++、Rust、Go 等 多语种支持:支持二十多种语言的识别(包括中文) 实时性:实时性语音识别场景下,vosk 的延迟非常低 简单来讲,你电脑中有 Python 环境,再下载一个 50 MB 的模型,就可以用 Vosk 实现一个正确率还可以接受的语言识别相关的项目。而像 Whisper 虽然识别效果好,但是对硬件要求很高,同时部署起来麻烦(例如需要配置 CUDA 环境),另外也不是很适用于实时性场景。 此包为编译好的c调用的运行库,有需要的可以直接下载使用。

    影视源码自动对接资源站开源源码

    影视源码自动对接资源站开源源码

    【超强组合】基于VMD-多元宇宙优化算法MVO-Transformer-GRU的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    大学生社团管理系统 SSM毕业设计 附带论文.zip

    大学生社团管理系统 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B

    网络安全 - 图片文件黑客攻击

    网络安全 - 图片文件黑客攻击

    【活字格插件】文件复制

    服务器可运行。实现文件复制。

    【超强组合】基于VMD-淘金优化算法GRO-Transformer-GRU的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

Global site tag (gtag.js) - Google Analytics