51Testing软件测试论坛

标题: 有人对大公司的面试题感兴趣吗？ [打印本页]

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

作者: 千里 时间: 2010-9-26 09:16
顶顶，如果你分享肯定还是有很多人感兴趣的。

作者: cleverman 时间: 2010-9-26 10:37
一个很大的数组，长度可以是100000或者更大，里面的数字可以从0到2的32次方，找出
出现频率最高
的数字

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

作者: 青溪漾漾 时间: 2010-10-3 19:38
不大懂，纯粹帮顶。。。

作者: 愚人 时间: 2010-10-3 19:55
算法题目啊

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

作者: wwwyhx 时间: 2010-10-5 17:03
cleverman 发了个邮件给你注意查收哈~~

作者: cleverman 时间: 2010-10-6 02:04

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

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

作者: msnshow 时间: 2010-10-6 13:24
完全没概念

作者: wwwyhx 时间: 2010-10-7 20:53
本帖最后由 wwwyhx 于 2010-10-7 21:31 编辑

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

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

作者: lyscser 时间: 2010-10-7 21:10
不好意思，咱就是出题的人……

作者: wwwyhx 时间: 2010-10-7 22:12
我来给几个微软的面试题：
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
回复 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
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

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

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

作者: wwwyhx 时间: 2010-10-8 22:57
是没啥意思，赛门的终端安全部，刁难人啊～～～～

作者: cleverman 时间: 2010-10-9 00:16

是没啥意思，赛门的终端安全部，刁难人啊～～～～
wwwyhx 发表于 2010-10-8 22:57

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

作者: south_man 时间: 2010-10-9 09:01
太变态了~

作者: cleverman 时间: 2010-10-9 16:07
有两个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)

作者: cleverman 时间: 2010-10-9 16:11
有一个输入的字符串，和一组substring,每一个substring 包括
1. start (开始位置）
2. end (结束位置）
3. score (得分）
substring有可能有overlap,并且score 和substring的位置，长度，内容完全没有关系。
问题是，返回所有的没有overlap的substrings, 使的他们的sum最大。

作者: cleverman 时间: 2010-10-9 16:13
回复 10# wwwyhx

有人说用bucket sort, 根据int 32位分为32个bucket。然后在分组sort。

作者: cleverman 时间: 2010-10-9 16:24

我来给几个微软的面试题：
1.二叉搜索树找给定两个节点的最近公共父节点
2.只知道一个指针指向某链表的一 ...
wwwyhx 发表于 2010-10-7 22:12

知不知道如果指向的是最后一个节点怎么办？

作者: jerry_sky 时间: 2010-10-9 17:40
看了挺惭愧的，这些题目很多都不懂

作者: wwwyhx 时间: 2010-10-9 18:00
我晕，桶排序在这和hashtable没什么区别吧，不也要重新分配空间

作者: wwwyhx 时间: 2010-10-9 18:28
最笨的方法就是穷举

聪明一点的办法就是贪婪算法吧，对每个字符串做权值计算wi = score/length, 先选择权值最大的，然后按权值递减的往下选，重叠的跳过。NP复杂问题？？

作者: wwwyhx 时间: 2010-10-9 18:31
哦，那个面试官给了个前提条件是节点非头尾.要不就无解了。

作者: 欺负人 时间: 2010-10-9 21:17
2010年27号晚,Google的2011年校园招聘宣讲会分别在北大和清华举行，其中北大本来是350
人的会场，结果去了大约600多人，爆满，那场面绝对是人山人海，彩旗飘飘。

经过了大约一个小时多的宣讲和问答，开始现场笔试环节，一共10个选择题和三个算法题，只有选
择题答对了8个以上的人才有机会让面试官看你后面的算法题。然后第2天下午会通知笔
试通过的人进行面试，Google的效率就像其搜索引擎一样迅速，效率可见一斑。

其中前10个选择题中有一个特别雷人的，题如下：

现在北京有一套房子，价格200万，假设房价每年上涨10%，一个软件工程师每年固定能
赚40万。如果他想买这套房子，不贷款，不涨工资，没有其他收入，每年不吃不喝不消
费，那么他需要几年才能攒够钱买这套房子？
A, 7年
B, 8年
C, 9年
D, 10年
E, 永远买不起

作者: cleverman 时间: 2010-10-9 23:02
回复 26# wwwyhx
brute force不让用，
greedy, 考官明确说了不work。权值最大的未必会在结果列表里吧？
比如 1-10 10
10-11 4
11-20 10

应该返回1-10, 11-20 sum=20
按权值的话是10-11 4最大

作者: KingRight 时间: 2010-10-9 23:35
回复 3# cleverman

将数值考虑成2进制！

作者: goopy 时间: 2010-10-9 23:37
回复 28# 欺负人

应该要10年的时间，相当于花了400W买了这套房子

作者: KingRight 时间: 2010-10-9 23:48

2010年27号晚,Google的2011年校园招聘宣讲会分别在北大和清华举行，其中北大本来是350
人的会场，结果去了 ...
欺负人发表于 2010-10-9 21:17

40 * n = 200 * (1+10%)的n次方

求n,无解. 所以是永远买不起

作者: KingRight 时间: 2010-10-9 23:51

回复欺负人

应该要10年的时间，相当于花了400W买了这套房子
goopy 发表于 2010-10-9 23:37

10年之后这个房子涨到了518.74849202万！

作者: wwwyhx 时间: 2010-10-10 18:41
楼主几道题没给标准答案啊

作者: cleverman 时间: 2010-10-10 22:29
回复 34# wwwyhx

很多题是没有标准答案的，或者标准答案是错的。变string的那道，是DP题，这个答案我知道了。substring的，别人给我link了，我还没怎么看太明白，只是知道个大概的意思。感觉很多时候你去面试一个公司会碰到这么一道变态的题（至少对我来说做出来的可能性基本为零，如果不事先知道题）
可能只能靠多看题才能慢慢量变到质变。
这两道题都可以brute force。不过有些变态的面试官直接就断掉你的想法了。其实就算brute force代码也不是太容易。第一道题你想知道最优解可以search "edit distance"。第二道题要用到二分法

作者: wwwyhx 时间: 2010-10-12 00:22
edit distance解法

动态规划经常被用来作为这个问题的解决手段之一。
　　整数 Levenshtein距离(字符串 str1[1..m], 字符串 str2[1..n])
　　//声明变量， d[i , j]用于记录str1[1...i]与str2[1..j]的Levenshtein距离
　　int d[0..m, 0..n]
　　//初始化
　　for i from 0 to m
　　d[i, 0] := i
　　for j from 0 to n
　　d[0, j] := j
　　//用动态规划方法计算Levenshtein距离
　　for i from 1 to m
　　for j from 1 to n
　　{
　　//计算替换操作的代价，如果两个字符相同，则替换操作代价为0，否则为1
　　if s= t[j] then cost := 0
　　else cost := 1
　　//d[i,j]的Levenshtein距离，可以有
　　d[i, j] := minimum(
　　d[i-1, j] + 1, //在str2上j位置删除字符（或者在str1上i-1位置插入字符）
　　d[i, j-1] + 1, //在str2上j-1位置插入字符（或者在str1上i位置删除字符）
　　d[i-1, j-1] + cost // 替换操作
　　)
　　}

作者: wwwyhx 时间: 2010-10-12 08:42
(转贴)
思路：

开一个二维数组d[j]来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求

具体算法：

首先给定第一行和第一列，然后，每个值d[i,j]这样计算：d[j] = min(d[i-1][j]+1,d[j-1]+1,d[i-1][j-1]+(s1  ==  s2[j]?0:1));
最后一行，最后一列的那个值就是最小编辑距离

poj3356类似题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=3356

c++代码：

#include <iostream>
using namespace std;

int len1,len2;//分别代表原string与目标string的长度
char s[1005],d[1005];//分别存储原string与目标string
int dp[1001][1001];

inline int Max(int a,int b)
{
return a>b?a:b;
}
inline int Min(int a,int b)
{
return a<b?a:b;
}
void Dp()
{
int i,j;
for (i = 0; i <= Max(len1,len2); i++)
{
  dp[0] = i;
  dp[0] = i;
}
for (i=1; i<=len1; i++)
  for (j=1; j<=len2; j++)
  {
if (s[i-1]==d[j-1])
dp[j]=dp[i-1][j-1];//不需操作
else
dp[j]=Min(dp[j-1]+1,Min(dp[i-1][j]+1,dp[i-1][j-1]+1));
  }
cout<<dp[len1][len2]<<endl;
}
int main(void)
{
//freopen("in.txt","r",stdin);
while (cin>>len1>>s)
{
  cin>>len2>>d;
  Dp();
}
return 0;
}

作者: 474241558 时间: 2010-10-13 09:45
题目涉及的即广又精·····需要懂得东西还有很多，大公司就喜欢搞一些比较拐的题目。哎········
做不出来也不能完全决定什么啊。

作者: weiwei911909 时间: 2010-11-19 23:37

各种豆要学啊学嘛先学嘛啊 ~~

作者: wwwyhx 时间: 2010-11-22 13:08
回复 21# cleverman

设最大可能的得分是 maxScore (可通过最高单位权值乘以长度计算)
给输入字符串编号：st0,st1,st2....stn
字符串对应的分数编号:sc0,sc2...scn
我现在从st0一个个读到stn，每遇到一个字符串无非就是选与不选两种可能
设 f(i)为i .... n的最大score，目的是求f(0)
则有公式：f(x) = max{f(x+1), f(x) + sc(x+1)} (str(x+1)不和现有的重叠) 或 f(x+1)(str(x+1)和现有的重叠)

用动态规划实现以上函数

作者: fuwu527751246 时间: 2010-11-22 14:45

作者: 丢了朵朵 时间: 2011-1-12 11:08
天~看到这些发现差距好大啊~一点概念都没有~

作者: 丢了朵朵 时间: 2011-1-12 11:11
回复 41# fuwu527751246

最近老发现你的踪迹~嘿嘿

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)