Indeed Tokyo 笔试题一道

Indeed的笔试一次一共4道,鄙人第一次做,前三题1hr就搞定了,唯独最后一题百思不得其解,后来看了大神的思路后幡然醒悟,确实脑子没转过来啊! 题目大致如下: 输入字符串 str=a[0] a[1] ... a[N] ,其中0<N<=10^5。字符串的每一位是0-9或?,需要用0-9填充各个问号的值,使得整个字符串成为一个数(允许前导0),并且满足任意连续10位上的字符(或理解成数字) a[i] a[i+1] ... a[i+9] 不重复,输出解的个数。 例如,输入”04??2?7″,输出应当为120.   最简单的思路当然是回溯,回溯用递归的话容易爆栈,可以自己定义栈结构。但实现完了我发现效率太低了。这种解法的时间复杂度是O(N!). 网上给了一个十分简单的思路:只计算str前10个字符有多少可能性。 这样做可行否?不妨试试看。 假设已经知道了前10个字符a[0]…a[9]能得到解的数目(定作M),那么根据规则,在a[10]的时候要考虑a[1]…a[9]的情况,对于每一种a[1]到a[9]的情况而言,由于已经决定了9个数字了,那么第10个数字显然已经确定了。从这我们可以知道,解的个数肯定是不大于M的,因为假设a[10]不是个”?”并且a[10]又不等于缺的那个数字的话,那这个case是要被毙掉的。然后以此类推,检测a[11], a[12], .. a[N]. 按照这种算法,整个问题的时间复杂度是O(10! * N)=O(N). ==更新== 还有一个更高效的解法,主要思路是利用后面“循环数”得到的确定信息来填充前面的?,然后直接计算组合数即可。具体可以看http://gaomf.cn/2016/10/26/String_Fill/ ======== 伪代码如下:

换个说法就是,后面的数字肯定是前面10个数字的循环,因为新加的a[i]肯定是得顶替上a[i-10]的位置的。  

16年网易数据挖掘实习生笔试小记

恩,不透题,只写个大概~   形式:在线笔试,两个小时。 题量:10个单选,10个不定项选择,5个大题(2个编程题+3个其他题) 期间网页不能切出去(据说有切出去5次被禁止作答的),实时摄像头监控。   客观题里有印象的考点: 树的遍历(前序、中序、后序) linux基本指令 Hadoop/Spark基础 数据库基础 C++指针、数组、常用算法的概念(KMP) 聚类方法、降维方法(主要是概念) 主观题: 编程题1:小数的四舍五入 编程题2:给定树的BFS序列和目标target,输出某路径上的节点值相加等于target的 主观题1:机器学习(神经网络)的概念 主观题2:概率图模型推导 主观题3:loss function相关,梯度算子推导(似乎是这个) 整体感觉难度很有区分性,选择题考概念基础,编程题难度不是很大,三个主观题倒是不大会,自己估计是要当大分母了!