`
alucardggg
  • 浏览: 8950 次
  • 性别: 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]
    
分享到:
评论

相关推荐

    百度面试题

    【标题】:“百度面试题”通常指的是百度公司在招聘过程中可能会问到的问题集合,这些题目涵盖了技术、产品、设计、运营等多个领域,旨在测试应聘者的专业技能、思维逻辑以及问题解决能力。百度作为中国互联网巨头之...

    百度面试经验

    ### 百度面试经验分享及解析 #### 一、面试流程概述 本次分享主要围绕一次在百度公司的面试经历。面试者通过在线平台投递简历后迅速收到笔试邀请,并前往位于北京盈科中心的百度办公室参加笔试。笔试内容包括四道...

    百度面试题第三题及答案.doc

    《百度面试题第三题及答案解析》 面试是求职过程中至关重要的一环,尤其对于IT行业的面试,往往涉及到具体的技术问题和解决方案。本题主要关注的是数据库设计与优化,以及系统设计策略,这些问题在实际工作中具有很...

    B端产品经理必问面试问题及答案(一).pdf

    【B端产品经理面试问题及答案】是针对求职者在应聘B端产品经理角色时可能会遇到的常见面试问题及其解答策略的汇总。B端产品经理是负责为企业客户提供软件产品和服务的专业人士,通常涉及SaaS(Software as a Service...

    百度面试题汇总(java)

    ### 百度面试题汇总(Java) #### 一、Java基础知识 1. **自我介绍**:面试官希望从自我介绍中获取应聘者的基本背景信息,包括但不限于教育经历、工作经验等,以便于后续针对这些背景提出具体问题。 2. **项目...

    百度Android工程师面试题.zip

    "百度Android工程师面试题.zip" 这个标题表明这是一份与百度公司面试Android工程师相关的资料集合,通常包含常见的面试问题、技术要点以及可能的解答。这份资料可能涵盖了Android开发的基础到高级知识,旨在帮助应聘...

    互联网企业面试经验大全

    本资源"互联网企业面试经验大全"汇集了中国互联网巨头,如百度、腾讯、阿里巴巴、京东以及360公司的面试经验分享,旨在帮助求职者更好地准备和理解这些公司的面试流程及要求。 一、面试流程 1. 网申:大多数互联网...

    百度面试总结

    ### 百度面试总结 #### 一、百度面试概述 百度作为中国领先的互联网公司之一,在技术领域的面试过程中,考察应聘者的综合素质与专业知识是至关重要的环节。本文将从百度面试的一般流程、常见面试题目以及面试过程...

    百度云的面试经验的相关分享

    百度云的面试经验分享 本文主要分享了百度云部门的面试经验,涵盖了数据库、网络编程、Linux、C++、Java 等多个方面的知识点。以下是详细的知识点解析: 数据库相关知识点 * 数据库范式:数据库范式是指数据库的...

    百度android开发面试题

    ### 百度Android开发面试题解析 #### 1. Android DVM、Linux 进程与应用程序进程的关系 在Android环境中,DVM(Dalvik虚拟机)是为Android平台设计的虚拟机,每个Android应用都在其自己的进程中运行,并拥有独立的...

    百度校招笔试面试题

    本文将深入解析“百度校招笔试面试题”中可能涉及的知识点,帮助求职者更好地准备。 首先,笔试部分通常包含以下几个核心领域: 1. **算法与数据结构**:这是计算机科学的基础,百度笔试中可能会出现经典的排序...

    google百度北电华为腾讯试题及面试

    2. **百度面试题**:百度的面试同样注重算法和编程能力,特别是在搜索引擎优化、自然语言处理、人工智能等领域。面试者可能会被要求设计和优化复杂的搜索算法,或者解决与大数据处理相关的问题。 3. **北电面试题**...

    【互联网一线大厂面试+学习指南】 涵盖大部分Java程序员所需要的面试知识点和面试技巧,分享真实面试经历。.zip

    同时,真实的面试经历分享可以帮助求职者了解面试官的提问方式、问题的深度以及如何有效地展示自己的能力。通过"JavaInterview-master"这个资源,你可以获取具体的问题解析、答案示例,以及应对面试的策略和技巧,...

    java-面试指北PDF版本(最新)

    了解如何阐述项目经历,包括项目的目标、角色、技术栈、遇到的问题及解决方案,将有助于展示自己的专业技能。 5. **如何提高个人编程硬实力?** 提升编程硬实力包括深入理解数据结构与算法,熟悉设计模式,掌握多...

    baidu.rar_baidu_百度_面试

    【标签】"baidu 百度 面试" 进一步强调了主题,即文件的内容与百度公司及其面试环节紧密相关,可能涉及到技术问题、逻辑思维、算法理解、项目经验等多个面试环节的考察点。 【压缩包子文件的文件名称列表】中的文件...

    iOS开发大厂面试经历

    以下将结合标题“iOS开发大厂面试经历”及描述中的公司(百度、掌赢、去哪儿、阿里巴巴)来探讨这些知识点。 首先,对于百度这样的互联网巨头,面试通常会考察开发者的基础扎实程度。Objective-C或Swift是iOS开发的...

    最新Java面试题视频网盘,Java面试题84集、java面试专属及面试必问课程

    面试题包含了不同技术层面的面试问题,同时也能对一些没有面试开发经验的小白给予不可估量的包装, 让你的薪水绝对翻倍, 本人亲试有效.Java面试题84集、java面试专属及面试必问课程,所有的面试题有视屏讲解, 解答方案....

    世界五百强面试题目及应答评点(全套50题).doc

    - 解析:回答此问题时,求职者应强调自己的相关经验和技能,并表达对该职位的热情。错误回答过于笼统,缺乏具体实例;正确回答则通过个人经历和故事展现自己与职位的契合度,同时展示自信和进取心。 2. **自我认知...

Global site tag (gtag.js) - Google Analytics