最近忙着面试,很意外接到百度的面试电话,在经过电话面试之后(招聘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]
分享到:
相关推荐
【标题】:“百度面试题”通常指的是百度公司在招聘过程中可能会问到的问题集合,这些题目涵盖了技术、产品、设计、运营等多个领域,旨在测试应聘者的专业技能、思维逻辑以及问题解决能力。百度作为中国互联网巨头之...
### 百度面试经验分享及解析 #### 一、面试流程概述 本次分享主要围绕一次在百度公司的面试经历。面试者通过在线平台投递简历后迅速收到笔试邀请,并前往位于北京盈科中心的百度办公室参加笔试。笔试内容包括四道...
《百度面试题第三题及答案解析》 面试是求职过程中至关重要的一环,尤其对于IT行业的面试,往往涉及到具体的技术问题和解决方案。本题主要关注的是数据库设计与优化,以及系统设计策略,这些问题在实际工作中具有很...
【B端产品经理面试问题及答案】是针对求职者在应聘B端产品经理角色时可能会遇到的常见面试问题及其解答策略的汇总。B端产品经理是负责为企业客户提供软件产品和服务的专业人士,通常涉及SaaS(Software as a Service...
### 百度面试题汇总(Java) #### 一、Java基础知识 1. **自我介绍**:面试官希望从自我介绍中获取应聘者的基本背景信息,包括但不限于教育经历、工作经验等,以便于后续针对这些背景提出具体问题。 2. **项目...
"百度Android工程师面试题.zip" 这个标题表明这是一份与百度公司面试Android工程师相关的资料集合,通常包含常见的面试问题、技术要点以及可能的解答。这份资料可能涵盖了Android开发的基础到高级知识,旨在帮助应聘...
本资源"互联网企业面试经验大全"汇集了中国互联网巨头,如百度、腾讯、阿里巴巴、京东以及360公司的面试经验分享,旨在帮助求职者更好地准备和理解这些公司的面试流程及要求。 一、面试流程 1. 网申:大多数互联网...
### 百度面试总结 #### 一、百度面试概述 百度作为中国领先的互联网公司之一,在技术领域的面试过程中,考察应聘者的综合素质与专业知识是至关重要的环节。本文将从百度面试的一般流程、常见面试题目以及面试过程...
百度云的面试经验分享 本文主要分享了百度云部门的面试经验,涵盖了数据库、网络编程、Linux、C++、Java 等多个方面的知识点。以下是详细的知识点解析: 数据库相关知识点 * 数据库范式:数据库范式是指数据库的...
### 百度Android开发面试题解析 #### 1. Android DVM、Linux 进程与应用程序进程的关系 在Android环境中,DVM(Dalvik虚拟机)是为Android平台设计的虚拟机,每个Android应用都在其自己的进程中运行,并拥有独立的...
本文将深入解析“百度校招笔试面试题”中可能涉及的知识点,帮助求职者更好地准备。 首先,笔试部分通常包含以下几个核心领域: 1. **算法与数据结构**:这是计算机科学的基础,百度笔试中可能会出现经典的排序...
2. **百度面试题**:百度的面试同样注重算法和编程能力,特别是在搜索引擎优化、自然语言处理、人工智能等领域。面试者可能会被要求设计和优化复杂的搜索算法,或者解决与大数据处理相关的问题。 3. **北电面试题**...
同时,真实的面试经历分享可以帮助求职者了解面试官的提问方式、问题的深度以及如何有效地展示自己的能力。通过"JavaInterview-master"这个资源,你可以获取具体的问题解析、答案示例,以及应对面试的策略和技巧,...
了解如何阐述项目经历,包括项目的目标、角色、技术栈、遇到的问题及解决方案,将有助于展示自己的专业技能。 5. **如何提高个人编程硬实力?** 提升编程硬实力包括深入理解数据结构与算法,熟悉设计模式,掌握多...
【标签】"baidu 百度 面试" 进一步强调了主题,即文件的内容与百度公司及其面试环节紧密相关,可能涉及到技术问题、逻辑思维、算法理解、项目经验等多个面试环节的考察点。 【压缩包子文件的文件名称列表】中的文件...
以下将结合标题“iOS开发大厂面试经历”及描述中的公司(百度、掌赢、去哪儿、阿里巴巴)来探讨这些知识点。 首先,对于百度这样的互联网巨头,面试通常会考察开发者的基础扎实程度。Objective-C或Swift是iOS开发的...
面试题包含了不同技术层面的面试问题,同时也能对一些没有面试开发经验的小白给予不可估量的包装, 让你的薪水绝对翻倍, 本人亲试有效.Java面试题84集、java面试专属及面试必问课程,所有的面试题有视屏讲解, 解答方案....
- 解析:回答此问题时,求职者应强调自己的相关经验和技能,并表达对该职位的热情。错误回答过于笼统,缺乏具体实例;正确回答则通过个人经历和故事展现自己与职位的契合度,同时展示自信和进取心。 2. **自我认知...