算法面试场景题

‘壹’ 两道分类算法的面试题，数据挖掘/机器学习相关，诚心求教！

1. 两个最重要的属性应该是数据的维数和数据的相关性，因为一般来讲，数据的维数越多越好，数据的相关性越小越好。

2. 应该选择第二个，因为测试耗时增加很小(从耗时单位可以看出)，同时训练花费的时间减少了很多(缩小到1/10)

   个人愚见，希望对你有帮助~~

‘贰’ 算法面试

我在《再谈“我是怎么招程序员”》中比较保守地说过，“问难的算法题并没有错，错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”，今天，我想加强一下这个观点——我反对纯算法题面试！（注意，我说的是纯算法题）图片源Wikipedia（点击图片查看词条）我再次引用我以前的一个观点——能解算法题并不意味着这个人就有能力就能在工作中解决问题，你可以想想，小学奥数题可能比这些题更难，但并不意味着那些奥数能手就能解决实际问题。好了，让我们来看一个示例（这个示例是昨天在微博上的一个讨论），这个题是——“找出无序数组中第2大的数”，几乎所有的人都用了O(n)的算法，我相信对于我们这些应试教育出来的人来说，不用排序用O(n)算法是很正常的事，连我都不由自主地认为O(n)算法是这个题的标准答案。我们太习惯于标准答案了，这是我国教育最悲哀的地方。（广义的洗脑就是让你的意识依赖于某个标准答案，然后通过给你标准答案让你不会思考而控制你）功能性需求分析试想，如果我们在实际工作中得到这样一个题 我们会怎么做？我一定会分析这个需求，因为我害怕需求未来会改变，今天你叫我找一个第2大的数，明天你找我找一个第4大的数，后天叫我找一个第100大的数，我不搞死了。需求变化是很正常的事。分析完这个需求后，我会很自然地去写找第K大数的算法——难度一下子就增大了。很多人会以为找第K大的需求是一种“过早扩展”的思路，不是这样的，我相信我们在实际编码中写过太多这样的程序了，你一定不会设计出这样的函数接口 —— Find2ndMaxNum(int* array, int len)，就好像你不会设计出 DestroyBaghdad(); 这样的接口，而是设计一个DestoryCity( City& ); 的接口，而把Baghdad当成参数传进去！所以，你应该是声明一个叫FindKthMaxNum(int* array, int len, int kth)，把2当成参数传进去。这是最基本的编程方法，用数学的话来说，叫代数！最简单的需求分析方法就是把需求翻译成函数名，然后看看是这个接口不是很二？！（注：不要纠结于FindMaxNum()或FindMinNum()，因为这两个函数名的业务意义很清楚了，不像Find2ndMaxNum()那么二）非功能性需求分析性能之类的东西从来都是非功能性需求，对于算法题，我们太喜欢研究算法题的空间和时间复杂度了。我们希望做到空间和时间双丰收，这是算法学术界的风格。所以，习惯于标准答案的我们已经失去思考的能力，只会机械地思考算法之内的性能，而忽略了算法之外的性能。如果题目是——“从无序数组中找到第K个最大的数”，那么，我们一定会去思考用O(n)的线性算法找出第K个数。事实上，也有线性算法——STL中可以用nth_element求得类似的第n大的数，其利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：1）Sa中元素的个数小于k，则Sb中的第 k-|Sa|个元素即为第k大数；2） Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)。搞学术的nuts们到了这一步一定会欢呼胜利！但是他们哪里能想得到性能的需求分析也是来源自业务的！我们一说性能，基本上是个人都会问，请求量有多大？如果我们的FindKthMaxNum()的请求量是m次，那么你的这个每次都要O(n)复杂度的算法得到的效果就是O(n*m)，这一点，是书呆子式的学院派人永远想不到的。因为应试教育让我们不会从实际思考了。工程式的解法根据上面的需求分析，有软件工程经验的人的解法通常会这样：1）把数组排序，从大到小。2）于是你要第k大的数，就直接访问 array[k]。排序只需要一次，O(n*log(n))，然后，接下来的m次对FindKthMaxNum()的调用全是O(1)的，整体复杂度反而成了线性的。其实，上述的还不是工程式的最好的解法，因为，在业务中，那数组中的数据可能会是会变化的，所以，如果是用数组排序的话，有数据的改动会让我重新排序，这个太耗性能了，如果实际情况中会有很多的插入或删除操作，那么可以考虑使用B+树。工程式的解法有以下特点：1）很方便扩展，因为数据排好序了，你还可以方便地支持各种需求，如从第k1大到k2大的数据（那些学院派写出来的代码在拿到这个需求时又开始挠头苦想了）2）规整的数据会简化整体的算法复杂度，从而整体性能会更好。（公欲善其事，必先利其器）3）代码变得清晰，易懂，易维护！（学院派的和STL一样的近似O(n)复杂度的算法没人敢动）争论你可能会和我有以下争论，如果程序员做这个算法题用排序的方式，他一定不会像你想那么多。是的，你说得对。但是我想说，很多时候，我们直觉地思考，恰恰是正确的路。因为“排序”这个思路符合人类大脑处理问题的方式，而使用学院派的方式是反大脑直觉的。反大脑直觉的，通常意味着晦涩难懂，维护成本上升。就是一道面试题，我就是想测试一下你的算法技能，这也扯太多了。没问题，不过，我们要清楚我们是在招什么人？是一个只会写算法的人，还是一个会做软件的人？这个只有你自己最清楚。这个算法题太容易诱导到学院派的思路了。是的这道“找出第K大的数”，其实可以变换为更为业务一点的题目——“我要和别的商户竞价，我想排在所有竞争对手报价的第K名，请写一个程序，我输入K，和一个商品名，系统告诉我应该订多少价？（商家的所有商品的报价在一数组中）”——业务分析，整体性能，算法，数据结构，增加需求让应聘者重构，这一个问题就全考了。你是不是在说算法不重要，不用学？千万别这样理解我，搞得好像如果面试不面，我就可以不学。算法很重要，算法题能锻炼我们的思维，而且也有很多实际用处。我这篇文章不是让大家不要去学算法，这是完全错误的，我是让大家带着业务问题去使用算法。问你业务问题，一样会问到算法题上来。小结看过这上面的分析，我相信你明白我为什么反对纯算法面试题了。原因就是纯算法的面试题根本不能反应一个程序的综合素质！那么，在面试中，我们应该要考量程序员的那些综合素质呢？我以为有下面这些东西：会不会做需求分析？怎么理解问题的？解决问题的思路是什么？想法如何？会不会对基础的算法和数据结构灵活运用？另外，我们知道，对于软件开发来说，在工程上，难是的下面是这些挑战：软件的维护成本远远大于软件的开发成本。软件的质量变得越来越重要，所以，测试工作也变得越来越重要。软件的需求总是在变的，软件的需求总是一点一点往上加的。程序中大量的代码都是在处理一些错误的或是不正常的流程。所以，对于编程能力上，我们应该主要考量程序员的如下能力：设计是否满足对需求的理解，并可以应对可能出现的需求变化。

‘叁’ java面试算法题

自己算吧

‘肆’ 一道面试算法题

这是典型的桶排序算法，
假设有9个桶，每个桶里存放N个数字。桶应该是唯一的。
所以推出结论：
1。桶是唯一的（我们因此可以利用Hashtable的唯一性来做到）；
2。桶内成员可以不排序，因此可以利用数组或者Vector来做到；
3。Hashtable需要主键key来唯一标识，正好数字1~9是不重复的，是唯一的；
3。把每个数值的第一位取出来，以第一位值做为key找到hashtable中的相应vector，再将vector.addElements(该数值);
4。完成;

具体做法：
1.生成桶，9个桶，每个桶以数字1~9做为主键命名
Hashtable table=new Hashtable();
for(int i=1;i<10;i++){
Vector vector=new Vector();
table.put(new String(i), vector);
}
2. 遍历每个数字，将当前数字的第一位分解出来，办法有很多种，比如除十法，这里介绍直接转字符串再取第一位法：
假设你的要处理的数字们放在数组里面int[] tmp;
for(int i=0;i<tmp.length;i++){
int num=tmp[i];
String str=new String(num);
char ch=str.charAt(0);
//压入到桶里，先把想要的桶找到，利用主键
Vector vect=(Vector)table.get(""+ch);
//找到桶后再把数值压到桶里
vect.addElements(new Integer(num));
}

//取出来的时候，有多种方法，一种是利用key取出Vector,再遍历Vector，得到其中元素，元素的key为String, 内容为Integer

另一种方法是先遍历hashtable再遍历vector

同样的应用还有给一幅被洗过的扑克牌进行升或降排弃，因此可以建13个桶(A~K)，每个桶内的牌再按花色排序（相当于对Vector排序，也可以不用Vector而直接用数组或者ArrayList等等）

我看了你的修改提问，现回答如下：
即使不能使用java己经封装好的Hashtable类，自己也可以很轻易地利用代码编写出类似于Hashtable的集合类，用来包容其它对象，并以主键key来唯一标识.

如果你不想这样思考，那么直接用数组来实现桶排序也很方便，外层数组长度是固定的，即1~9共9个数组元素 Elements e=new Elements[9]。
这九个数组元素不是数字，必须是你自定义的类。并用这个类形成链表结构
比如：
public class Element{
int data;//存数字
Element next=null;//下一个元素是谁
}
比如有数字 51,52,53 这三个数都是以5打头，那么他们应该放在一个桶里面，即第五号桶，也就是外层数组的第个元素中。

if( 判断该数字，是否应该放在5号桶){
Elements tmp=new Elements();
tmp.data=该数字;
Elements current=e[4];
if(current==null){current=tmp;}//如果该桶以前从未放过数字，则放进去的就是头部，直接引用就行了，比如51应该放在头部
else{//如果该桶以前己经放过数字，如51,己经放了，现在放52。52就应该做为51的next元素，而53就是52的next就行了
while(current!=null){current=current.next;}//遍历，从而取到最后一个元素的引用
//取到最后一个元素后，current=tmp;即可,这样就形成了链表结构
}
}

通过上述代表形成的结果是， 外层结构是9个元素组成的数组
每个数组元素是Elements类对象形成的链表结构,有头有层通过next字段串连起来。
如果要排序，只需要对每个链表内部进行排序就可以了

‘伍’ 大公司笔试面试有哪些经典算法题目

1、二维数组中的查找

具体例题：如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。现在给出一个数字序列，允许使用一种转换操作：选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列？

‘陆’ Java面试算法题求解

看了两行看不下去了，吐槽一下。
现在某些小公司的面试官，面试题花式秀智商，一副全世界都求着他赐予工作的样子。

‘柒’ 互联网公司最常见的算法面试题有哪些

很多人都搞不清辞职的流程方法，所以才会遇到这种尴尬的局面。

提出离职之前，应当先提出加薪申请。如果加薪通过，你继续安心干活，如果加薪申请被驳回，直接辞职信奉上，再也不要相信任何挽留的条件。

当然，你提出加薪申请的时候，千万不要流露出老子早找好下家了，不给加薪老子就炒你鱿鱼这样的表情，这对于谈判没什么帮助。多谈谈自己对公司的贡献，不要说公司之外的事情。 来自职Q用户：萝卜三人行
几乎必问排序，排序算法不下十种，不一定非要用快排，这种问题答的越多越好。 来自职Q用户：兔小灰

‘捌’ java算法面试题

三个for循环，第一个和第二个有啥区别?去掉一个吧
可以用迭代器remove方法，在移除的同时添加。

不知道是你记错了还是题本身就这样，我只想说：
写这代码的是二货么？
1、每个循环的索引都是从0开始，这是什么遍历方式？
2、看这题的目的是想把用户添加到相应的组里，这我就不明白了，新建一个用户的时候就没分配组么？那用户的GroupId哪来的？

3、这是一个操作，难道就不会根据GroupId直接查出用户或者组么？

这哪是优化代码？分明是挖坑。