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]的位置的。

 

M$ 2016 题目3 : Demo Day

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.

The maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.

Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can’t and keep moving to the bottom until it can’t. At the beginning, the robot keeps moving to the right.

While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?

输入

Line 1: N, M.

Line 2-N+1: the N * M maze.

For 20% of the data, N * M <= 16.

For 50% of the data, 1 <= N, M <= 8.

For 100% of the data, 1<= N, M <= 100.

输出

The minimum number of grids to be changed.

注记:

动态规划的一道题,后悔当时没有看通过率先做了第二道,第二题没有熟练掌握Trie结果处理超时了!

这题就是状态麻烦点,我的处理方式是在当前位置就判断右侧及下侧的通行情况,必要时做出改变,然后继续。因此注意点是一开始就被[0][0]位置blocked的情况。

以(x位置,y位置,当前方向)为一个三元组,可以保存唯一的状态结果,避免重复递归。

代码:

未经详细测试,待测试!感觉自己的编码能力还是有限,欢迎过客提出意见。

 

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

恩,不透题,只写个大概~

 

形式:在线笔试,两个小时。

题量:10个单选,10个不定项选择,5个大题(2个编程题+3个其他题)

期间网页不能切出去(据说有切出去5次被禁止作答的),实时摄像头监控。

 

客观题里有印象的考点:

  • 树的遍历(前序、中序、后序)
  • linux基本指令
  • Hadoop/Spark基础
  • 数据库基础
  • C++指针、数组、常用算法的概念(KMP)
  • 聚类方法、降维方法(主要是概念)

主观题:

  • 编程题1:小数的四舍五入
  • 编程题2:给定树的BFS序列和目标target,输出某路径上的节点值相加等于target的
  • 主观题1:机器学习(神经网络)的概念
  • 主观题2:概率图模型推导
  • 主观题3:loss function相关,梯度算子推导(似乎是这个)

整体感觉难度很有区分性,选择题考概念基础,编程题难度不是很大,三个主观题倒是不大会,自己估计是要当大分母了!