百度面试试题

只看该作者 · 2012-5-13 11:16

1、设计一个对乘法是封闭的操作，就是例如输入一个n（比如8），那么在1---8中间的8个数字，任意两个相乘的结果始终都是位于8个数字之间的任意一个数字。举例如下，比如2*3还是6，2*4还是8，但是3*4 、3*4、 4*4 这样的乘积必须始终还是在1---8中间的一个数字。
偶的想法是：如果只定义乘法的话，可以将乘积的结果除以8取余再加1，刚好可以映射到1到8，不知道这样算不算一个思路~~~
偶一开始是这样回答的，但是面试官说，这样做是无法满足消去律的，就是 a*b=a*c 那么b=c
因为按照我说的那个方法的话， 4*2=4*6 但是2 ！= 6，于是就导致无法满足消去律。
2、是如何统计代码行数以及注释的行数，并写出具体的实现代码。
3、要求用最快的速度求两个数组的交集，提示数组中的元素是无序的。写出具体的实现代码。
4、写程序，将一个浮点数转化为字符串。。

各位大神看到的，给个解法吧，偶当时都回答的很不好

1万 · 2012-5-13 11:24

1,*当做C里的&,+当做|,-当做&~，你懂的,就是集合运算是闭的.
2,代码行数是按照\n数的，行注释//需要注意//...\n算一个注释，但注意//...\n之间的//与/**/不算注释。
/**/要注意/* /* */ 等于一个注释, 也就是一旦遇见/*之后就要记下来，一直匹配到*/才算一个完整的注释，中间的内容随便它是什么，包括//可能也嵌套在其中。
3，要多快。。。如果哈希真的是O(1)的，那么可以达到O(n+m)，否则就是nlogn + mlogm。
4，sprintf。。。

只看该作者 · 2012-5-13 11:34

第3题的思路：假设这两个无序数组是数组A，元素个数为m 数组B，元素个数为n
1. 遍历数组A，取每一个元素A[i]，再遍历数组B，看A[i]是否在数组B中。这样的时间复杂度为m*n
2. 进一步优化时间，将数组B进行排序，所用时间的最短为nlgn，取数组A的每一个元素A[i]，在数组B中做二分查找，看A[i]是否在数组B中。这样的时间复杂度为mlgn+nlgn
3. 将两个数组都排好序，时间最短为mlgm+nlgn。两个数组齐头并进，判断是否有相同元素，判断时间为m+n。总的时间为mlgm+nlgn+m+n
4. 使用hashtable，将数组A中的元素进行hash，存入hash表，然后对数组B的元素进行hash后查看hash表，是否有数组A中的元素出现。这样的时间复杂度为m+n
5. 如果两个数组都是正整数，那么可以使用位图的方法，获得两个数组的最大值MAX，申请MAX个大小的int数组，c[max]={-INF};将A数组中的数据填入c中，查找B中的元素，看是否有在c中，时间为m+n
6. 使用map将A数组中每一个元素作为键映射到一个map中，值为1，将B数组也映射到同样地map中，如果两个值相同则其值+1，寻找map中个数为2的元素即可

只看该作者 · 2012-5-13 13:10

作为面试试题难度还不小

只看该作者 · 2012-5-13 19:03

3楼的思路值得借鉴

只看该作者 · 2012-5-13 20:53

有点难度

百度面试试题

相关下载

相关帖子