cleverman 发表于 2010-9-25 19:15:51

有人对大公司的面试题感兴趣吗？

通常顶级软件/互联网公司开发和测试的面试题是类似的，只是开发对答案要求更高一些，但是从题目上来讲区别不大。而且现在，面试开发也会让你设计test cases,因为开发承担一定的测试职责，比如Unit test。面试测试当然要考coding, 因为需要编写自动化。所以，无论面试开发，还是测试准备工作都是雷同的。
如果有人对他们的面试题感兴趣，我可以发一些上来大家一起讨论。

千里 发表于 2010-9-26 09:16:37

顶顶，如果你分享肯定还是有很多人感兴趣的。

cleverman 发表于 2010-9-26 10:37:22

一个很大的数组，长度可以是100000或者更大，里面的数字可以从0到2的32次方，找出
出现频率最高
的数字

我给的答案是hashtable, 小印女很不满，觉得太占内存，红黑树，好像也不满意，哪
位大牛给指点
下，她到底期待一个什么样的数据结构啊

青溪漾漾 发表于 2010-10-3 19:38:46

不大懂，纯粹帮顶。。。

愚人 发表于 2010-10-3 19:55:47

算法题目啊

wwwyhx 发表于 2010-10-5 17:03:14

基数排序，排好了再看
如果最大的位数是m,一共n个数,则需要比较(M*n + n)次 O(M*n) 一般M不超过6 时间复杂度为O(n)，因为已经有数组装了，不需要什么额外的空间。

wwwyhx 发表于 2010-10-5 17:03:47

cleverman 发了个邮件给你 注意查收哈~~

cleverman 发表于 2010-10-6 02:04:24

基数排序，排好了再看
如果最大的位数是m,一共n个数,则需要比较(M*n + n)次 O(M*n) 一般M不超过6 时间复杂 ...
wwwyhx 发表于 2010-10-5 17:03 http://bbs.51testing.com/images/common/back.gif

按10进制的位来分组？分组需要M*n次，但是每个分组还需要处理呀？而且为什么不需要额外的空间呀？

msnshow 发表于 2010-10-6 13:24:04

完全没概念

wwwyhx 发表于 2010-10-7 20:53:17

本帖最后由 wwwyhx 于 2010-10-7 21:31 编辑

哈哈 搞错了，如果这些数是链表存储的话用基数排序还凑合，是数组的话移动不方便。

这样吧，做个折衷的方案
快速排序，不需要额外存储空间，O(nlogn)，然后遍历一次O(n),结果是需要额外存储空间O(logn)（递归函数堆栈），时间复杂度是O(nlogn),谁有更好的办法？？？

lyscser 发表于 2010-10-7 21:10:57

不好意思，咱就是出题的人……

wwwyhx 发表于 2010-10-7 22:12:36

我来给几个微软的面试题：
1.二叉搜索树找给定两个节点的最近公共父节点
2.只知道一个指针指向某链表的一个节点，把这个节点删掉(不知道头节点)

赛门铁克的：
1.c++虚函数表的指针-1指向的是什么东西
2.一台电脑的最大内存数由什么来决定
3.windows内存每个页面有哪几种状态?
4.trace route原理....

google的：
you are given 2 arrays sorted in decreasing order of size m and n
respectively.

Input: a number k <= n*m and >= 1

Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)

两个数组A,B 求第k个sum(a+b)。

cleverman 发表于 2010-10-8 10:21:29

回复 12# wwwyhx

MS, Google的比较常规。赛门的比较变态，是考开发的还是测试的？这种题考的是经验不是水平。

1.c++虚函数表的指针-1指向的是什么东西
没概念。parent的虚函数表？
2.一台电脑的最大内存数由什么来决定
这是从hardware角度，还是OS角度来说呢？hardware角度就是内存插槽的个数，和每个支持的内存最大值了。OS角度，OS的位数？
3.windows内存每个页面有哪几种状态?
指的已经paged-in的页面？read-only, executable, read-write etc?
4.trace route原理....
No much experience on networking.

cleverman 发表于 2010-10-8 10:21:37

回复 12# wwwyhx

MS, Google的比较常规。赛门的比较变态，是考开发的还是测试的？这种题考的是经验不是水平。

1.c++虚函数表的指针-1指向的是什么东西
没概念。parent的虚函数表？
2.一台电脑的最大内存数由什么来决定
这是从hardware角度，还是OS角度来说呢？hardware角度就是内存插槽的个数，和每个支持的内存最大值了。OS角度，OS的位数？
3.windows内存每个页面有哪几种状态?
指的已经paged-in的页面？read-only, executable, read-write etc?
4.trace route原理....
No much experience on networking.

wwwyhx 发表于 2010-10-8 18:34:57

1.c++虚函数表的指针-1指向的是什么东西
是一个指针，这个指针指向typeinfo结构体，typeinfo是在编译时生成的，作用是实现RTTI

2.一台电脑的最大内存数由什么来决定
cpu的地址总线

3.windows内存每个页面有哪几种状态?
reserved, commited, free

4.trace route原理....
ip包的TTL字段，规定了它最多能转几次路由

面的是开发，本来笔试和一面都不错的，结果来了个变态的二面，fuck

cleverman 发表于 2010-10-8 21:18:13

1.c++虚函数表的指针-1指向的是什么东西
是一个指针，这个指针指向typeinfo结构体，typeinfo是在编译时生成 ...
wwwyhx 发表于 2010-10-8 18:34 http://bbs.51testing.com/images/common/back.gif

是赛门铁克还是Veritas呀？你知道是哪个产品招聘吗？我不知道做什么样的工作会用到这些知识。这种出题没啥大意义。

wwwyhx 发表于 2010-10-8 22:57:13

是没啥意思，赛门的终端安全部，刁难人啊～～～～

cleverman 发表于 2010-10-9 00:16:50

是没啥意思，赛门的终端安全部，刁难人啊～～～～
wwwyhx 发表于 2010-10-8 22:57 http://bbs.51testing.com/images/common/back.gif

Sygate呀？是一个人出的题的个别现象，还是整体现象呀？

south_man 发表于 2010-10-9 09:01:55

太变态了~

cleverman 发表于 2010-10-9 16:07:40

有两个string, stringA and stringB。我们要从stringA 转变到 stringB, 但是每一个step, 我们只能操作一个字符。操作的方法有insert, delete and replace三种方式。问题是，从stringA到stringB的转化，最少需要多少个steps?
比如：Sunday -> Saturday
1. Sanday (replace)
2. Satday (replace)
3. Satuday (insert)
4. Saturday (insert)
页: [1] 2 3
查看完整版本: 有人对大公司的面试题感兴趣吗？