最近忙着面试,很意外接到百度的面试电话,在经过电话面试之后(招聘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
LOL_params_0900000.pt
分群用户详情_7_2024-09-06 09_49_58
动态加载的高级主题:懒加载与按需加载.docx
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
为Towny Flagwar实现中立国家 /nasetnu 设置自己的国家为中立(仅king可用)
本代码是基于python pytorch环境安装的。 下载本代码后,有个环境安装的requirement.txt文本 首先是代码的整体介绍 总共是3个py文件,十分的简便 本代码是不含数据集图片的,下载本代码后需要自行搜集图片放到对应的文件夹下即可 需要我们往每个文件夹下搜集来图片放到对应文件夹下,每个对应的文件夹里面也有一张提示图,提示图片放的位置 然后我们需要将搜集来的图片,直接放到对应的文件夹下,就可以对代码进行训练了。 运行01生成txt.py,是将数据集文件夹下的图片路径和对应的标签生成txt格式,划分了训练集和验证集 运行02CNN训练数据集.py,会自动读取txt文本内的内容进行训练,这里是适配了数据集的分类文件夹个数,即使增加了分类文件夹,也不需要修改代码即可训练 训练过程中会有训练进度条,可以查看大概训练的时长,每个epoch训练完后会显示准确率和损失值 训练结束后,会保存log日志,记录每个epoch的准确率和损失值 最后训练的模型会保存在本地名称为model.ckpt 运行03pyqt界面.py,就可以实现自己训练好的模型去识别图片了
内容概要:本文详细介绍了一款基于Java的订餐系统的设计与实现。文章首先介绍了互联网时代背景下,订餐系统作为一种新型生活方式的便捷性与必要性。接着阐述了系统的设计背景、目的及其所采用的技术框架(如JSP、MySQL、MyEclipse)。系统分为前台和后台两大部分,前台主要负责用户的界面展示和互动,包括食品展示、查询、购物车等功能;后台则是管理员进行餐品管理和用户信息维护的平台。文中还详细解析了各主要功能模块的设计思路和技术实现细节,以及数据库表结构的设计。 适合人群:具备一定的Java开发基础,对Web应用开发有兴趣的初学者或工程师。 使用场景及目标:用于学习基于B/S架构的订餐系统的开发全过程,理解前后端分离、JSP动态页面生成、MySQL数据库操作等核心技术的应用。适合希望深入了解餐饮管理系统内部运作机制的学生或从业者。 其他说明:此系统设计符合现代互联网发展趋势,通过引入JSP、JavaScript、MySQL等主流技术,旨在提高餐饮行业的管理效率和服务水平,增强用户体验。此外,本项目也包含了系统测试的内容,确保各项功能的正常运转。
功能说明: 管理员:个人中心、用户管理、商品分类管理、品牌管理、商品信息管理、订单评价管理、留言板管理、系统管理、订单管理。用户:个人中心、订单评价管理、我的收藏管理、订单管理。前台首页:首页、商品信息、商品资讯、留言反馈、我的、跳转到后台、购物车等功能的家用电器销售网站。 环境说明: 开发语言:java 框架:ssm jdk版本:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse 部署容器:tomcat7+
联想电脑的bios设置、图文都有
技术:ssm+mysql+redis vue+element 功能:宿舍管理、学生管理、班级管理、宿舍楼管理、维修记录、晚归记录、请假记录、用户管理、角色管理、菜单管理、日志管理
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
跨浏览器兼容性测试.docx
Vosk是一个开源的语音识别工具,支持中英文及多种语言,具备离线识别能力,且不依赖互联网。优势 Vosk 是一个离线开源语音识别工具包,它的优点在于: 轻量:Vosk 提供轻量级的模型(小于 50MB 大小),可以用于低功耗平台(例如 Android、树莓派之类) 多编程语言、多平台支持:Python、Java、Node.js、C#、C++、Rust、Go 等 多语种支持:支持二十多种语言的识别(包括中文) 实时性:实时性语音识别场景下,vosk 的延迟非常低 简单来讲,你电脑中有 Python 环境,再下载一个 50 MB 的模型,就可以用 Vosk 实现一个正确率还可以接受的语言识别相关的项目。而像 Whisper 虽然识别效果好,但是对硬件要求很高,同时部署起来麻烦(例如需要配置 CUDA 环境),另外也不是很适用于实时性场景。 此包为编译好的c调用的运行库,有需要的可以直接下载使用。
影视源码自动对接资源站开源源码
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
大学生社团管理系统 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B
网络安全 - 图片文件黑客攻击
服务器可运行。实现文件复制。
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手