最近忙着面试,很意外接到百度的面试电话,在经过电话面试之后(招聘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]
分享到:
相关推荐
校招的时候,百度云部门的相关经历,百度云的面试经历,面试题目,相关解答,经验分享。包括数据库的相关知识点,网络编程的相关知识点,相关语言的知识点,linux,c++,java
《前端面试宝典》是一本由前端工程师创作的书籍,主要内容是关于前端面试相关的知识点和经验...前端面试经验分享,包括如何准备面试、如何回答面试问题等。 前端行业动态,包括前端行业的发展趋势、新技术新应用等。
面试题包含了不同技术层面的面试问题,同时也能对一些没有面试开发经验的小白给予不可估量的包装, 让你的薪水绝对翻倍, 本人亲试有效.Java面试题84集、java面试专属及面试必问课程,所有的面试题有视屏讲解, 解答方案....
一、百度简介 二、百度文化 三、老板介绍 四、产品介绍 五、框计算 六、员工发展/薪酬 七、百度部门的奇诡名字解析 面经大放送!!!...一、关于招聘类型: ...四、百度面试指导及经验 非技术类 五、面试经历
百度历年笔试面试150题.docx 笔试1.doc 答案1.doc 细品这杯香浓的咖啡——阿里中间件高级专家沈询的Java之旅.docx 给你一次机会面试架构师 你会问什么问题?.docx 超全面:程序员跳槽神级攻略.docx 跳还是不跳,是一...
java面试笔试资料java笔试题大集合及答案题库java笔试题汇总资料188个合集 100家大公司java笔试题汇总.doc 125条常见的java 面试笔试题大汇总.pdf 2011最新整理java经典代码.doc 25个经典的Spring面试问答.docx ...
java面试笔试题库java软件设计java笔试题大集合及答案文档资料合集300MB“ 100家大公司java笔试题汇总.doc 125条常见的java 面试笔试题大汇总.pdf 2011最新整理java经典代码.doc 25个经典的Spring面试问答.docx 8张...
都是本人亲身面试经历,有详细的面试题目及解答。 另外本人还总结了 常见的面试题,尤其是对算法相关问题的整理 对于应届生 及即将找工作的朋友 都有很好的指导作用。 面经方向: 后台开发, linux 系统,算法设计...
感觉天津前端的技术要求相对偏低,这里有很多问题是在面试过程中遇到的,应该比较适应天津公司的技术问题,如果是前端新人没什么面试经验的话,看看我总结的这些东西,如果能背会的话,估计月薪也能到10k左右了 ...
引言 金三银四,特地整理一份面试题,现介绍本文特色: 1、适合前端,需要面试找工作 2、即将毕业面临实习,积累经验 ...【金三银四】一个问题就知道你会不会JS了 阿里、头条真题解析 【金三银四】一个
课程内容涵盖了排序算法、查找算法、图算法等多个领域,以及面试常见算法题的解析与实现。通过实践项目和练习,你将提升自己的编程能力和解决问题的能力。无论你是初学者还是有一定编程经验的人,本课程都能帮助你更...